EEBASS:Energy-Efficient BAlanced Storage Scheme for Sensor Networks Lei Xie,Lijun Chen,Daoxu Chen,Li Xie State Key Laboratory of Novel Software Technology Nanjing University,Nanjing,China Email:xielei@dislab.nju.edu.cn.chenli.cdx.xieli@nju.edu.cn Abstract-Data-centric storage is an effective and important We organize this paper as follows.Section 2 reviews the technique in sensor networks,however,most data-centric storage related work.And Section 3 defines problems for storage node schemes may not be energy efficient and load balanced due to placement in the aforementioned scenario.In Section 4,we non-uniform event and query distributions.This paper proposes EEBASS,it utilizes an approximation algorithm to solve the present an approximation algorithm for optimal solution to optimal storage placement problem according to the variance minimize the overall energy consumption.In Section 5,we of event and query distributions,aiming to minimize the total illustrate the load balance scheme for storage.In Section 6, energy consumption for data-centric storage scheme.And it we present our simulation results,which confirm the energy further leverages a ring based replication structure to achieve efficiency and load balance effect of our schemes.Finally, the load balance goal.Simulation results show that EEBASS is more energy efficient and balanced than traditional data-centric Section 7 concludes the paper. storage mechanisms in sensor network. II.RELATED WORK I.INTRODUCTION Research works for data-centric storage schemes mainly include structured storage scheme and unstructured storage Many sensor network applications generate a large amount scheme.Structured storage scheme mainly utilizes a mapping of sensor data,these data have to be stored somewhere for function such as geographic hash function to map event future retrieval and data analysis.Great efforts have been information to specified geographic points,and leverages addressed in the energy-efficient data gathering and query routing algorithms like GPSR [2]to route messages to coun- processing techniques in sensor networks,among which data terpart storage nodes,research works including GHT [2] centric storage is a very important technique.In data-centric DIMENTIONS [3]and DIM [4]belong to this scheme. scheme [1][2],data are stored at nodes within the network Unstructured storage scheme mainly utilizes the push-pull by name.Each reading will be hashed to a geographic point, scheme to disseminate and gather information,research works and then be routed to the node nearest to this point according including Double Ruling [5].Comb-Needles [6]belong to this to some protocols,such as the GPSR [2]routing algorithm. scheme.In [7]the authors propose a hybrid storage scheme Thus all data with the same general name are stored at the to implement the event storage and query.In [8]the authors same node. perform a fundamental analysis over the scalability of these In this paper,we consider an application scenario in which two kinds of data-centric storage schemes. sensor network provides data centric-storage scheme to users. Recent research works for data-centric storage scheme focus When some sensor node discovers relevant event Ei,it will on the storage placement problem to enhance energy efficiency forward the event information to specified storage node Si and load balance.In [9]the authors present optimal algorithms inside sensor network,and when user sends query Qi through based on dynamic programming to solve the deterministic a neighbor sensor node,the query Qi will be forwarded to placement problem of storage nodes and in [10]they propose counterpart storage node and query results will be replied.an approximation algorithm to solve the random placement Current data-centric storage schemes such as GHT [2]gen- problem.In [11]the authors propose a ring based index struc- erally distribute the storage nodes in a uniform approach ture to help reduce energy consumption of storage schemes. inside sensor network,leveraging a geographic hash mapping KDDCS [12]presents a load-balanced storage scheme for function.As events and queries may not be uniformly dis- sensor networks based on K-D tree. tributed over the sensor network,which is usually that case,the placement of those storage nodes may not achieve the energy- III.PROBLEM FORMULATION efficient goal to minimize the overall energy consumption of We formulate the problem as follows:assume sensor nodes sensor network.And note that the variance of different event are uniformly deployed over the monitoring area,given the and query workloads may incur load balance problem among prior knowledge of event frequency distribution fe(r,y)for storage nodes,we need to devise a replicated storage structure event Ei and query frequency distribution fa(,y)for query to balance the energy consumption for storage nodes,thus Qi inside sensor network deployment area,our goal is to further extend sensor network's lifetime decide the optimal storage placement set S=[S1,S2,...,S 978-1-4244-2324-8/08/S25.00©2008EEE. This full text paper乐B59 ensed asteiet4vafF毛feY8i98sfyA形79s0Teli7eE型头6rEsl8Py”2008 proceedings
EEBASS: Energy-Efficient BAlanced Storage Scheme for Sensor Networks Lei Xie, Lijun Chen, Daoxu Chen, Li Xie State Key Laboratory of Novel Software Technology Nanjing University, Nanjing, China Email: xielei@dislab.nju.edu.cn, {chenlj,cdx,xieli}@nju.edu.cn Abstract—Data-centric storage is an effective and important technique in sensor networks, however, most data-centric storage schemes may not be energy efficient and load balanced due to non-uniform event and query distributions. This paper proposes EEBASS, it utilizes an approximation algorithm to solve the optimal storage placement problem according to the variance of event and query distributions, aiming to minimize the total energy consumption for data-centric storage scheme. And it further leverages a ring based replication structure to achieve the load balance goal. Simulation results show that EEBASS is more energy efficient and balanced than traditional data-centric storage mechanisms in sensor network. I. INTRODUCTION Many sensor network applications generate a large amount of sensor data, these data have to be stored somewhere for future retrieval and data analysis. Great efforts have been addressed in the energy-efficient data gathering and query processing techniques in sensor networks, among which data centric storage is a very important technique. In data-centric scheme [1][2], data are stored at nodes within the network by name. Each reading will be hashed to a geographic point, and then be routed to the node nearest to this point according to some protocols, such as the GPSR [2] routing algorithm. Thus all data with the same general name are stored at the same node. In this paper, we consider an application scenario in which sensor network provides data centric-storage scheme to users. When some sensor node discovers relevant event Ei, it will forward the event information to specified storage node Si inside sensor network, and when user sends query Qi through a neighbor sensor node, the query Qi will be forwarded to counterpart storage node and query results will be replied. Current data-centric storage schemes such as GHT [2] generally distribute the storage nodes in a uniform approach inside sensor network, leveraging a geographic hash mapping function. As events and queries may not be uniformly distributed over the sensor network, which is usually that case, the placement of those storage nodes may not achieve the energyefficient goal to minimize the overall energy consumption of sensor network. And note that the variance of different event and query workloads may incur load balance problem among storage nodes, we need to devise a replicated storage structure to balance the energy consumption for storage nodes, thus further extend sensor network’s lifetime. We organize this paper as follows. Section 2 reviews the related work. And Section 3 defines problems for storage node placement in the aforementioned scenario. In Section 4, we present an approximation algorithm for optimal solution to minimize the overall energy consumption. In Section 5, we illustrate the load balance scheme for storage. In Section 6, we present our simulation results, which confirm the energy efficiency and load balance effect of our schemes. Finally, Section 7 concludes the paper. II. RELATED WORK Research works for data-centric storage schemes mainly include structured storage scheme and unstructured storage scheme. Structured storage scheme mainly utilizes a mapping function such as geographic hash function to map event information to specified geographic points, and leverages routing algorithms like GPSR [2] to route messages to counterpart storage nodes, research works including GHT [2], DIMENTIONS [3] and DIM [4] belong to this scheme. Unstructured storage scheme mainly utilizes the push-pull scheme to disseminate and gather information, research works including Double Ruling [5], Comb-Needles [6] belong to this scheme. In [7] the authors propose a hybrid storage scheme to implement the event storage and query. In [8] the authors perform a fundamental analysis over the scalability of these two kinds of data-centric storage schemes. Recent research works for data-centric storage scheme focus on the storage placement problem to enhance energy efficiency and load balance. In [9] the authors present optimal algorithms based on dynamic programming to solve the deterministic placement problem of storage nodes and in [10] they propose an approximation algorithm to solve the random placement problem. In [11] the authors propose a ring based index structure to help reduce energy consumption of storage schemes. KDDCS [12] presents a load-balanced storage scheme for sensor networks based on K-D tree. III. PROBLEM FORMULATION We formulate the problem as follows: assume sensor nodes are uniformly deployed over the monitoring area, given the prior knowledge of event frequency distribution fei (x, y) for event Ei and query frequency distribution fqi (x, y) for query Qi inside sensor network deployment area, our goal is to decide the optimal storage placement set S = {S1, S2, ..., Sk} This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE "GLOBECOM" 2008 proceedings. 978-1-4244-2324-8/08/$25.00 © 2008 IEEE. 1 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:40:16 UTC from IEEE Xplore. Restrictions apply
for event set E [E1,E2,...,Ek}and query set Q= (01,Q2,...,Q},so as to minimize the overall energy con- sumption for sensor network.And being aware of fe(r,y) and fa(,y)for storage node Si,we need to consider how to utilize the storage replication scheme to balance energy consumption among storage nodes. Before we start to analyze this problem,we first describe 04 the energy consumption model in this paper.The energy cost model is simplified by the assumption that the transmission cost is proportional to the data size and the hop distance between the sender and the receiver.In a densely deployed Fig.1.Storage Placement among the Object Points sensor network,the hop distance between two sensors is proportional to the Euclidean distance,and without loss of the optimal solution (,y).To reduce the complexity of the generality,we assume the data sizes are all equal in our model, calculation,we can select some representative points as an therefore,in this paper,we use Euclidean distance to measure object set to depict the distribution function.We partition the the energy consumption. monitoring area into m equal-sized grids,then we compute the For any storage and query process of event Ei,the energy distribution frequency fi(G;)for storage and query of event consumption is mainly composed of two parts:event storage Ei inside every grid Gj: energy cost and query energy cost,thus according to the above energy consumption model,the storage energy cost can be f(G)=fe(G)+2f4:(G) measured as the Euclidean distance between storage node S =()ec,fe.(,y)+2fa(,y)drdy (4) and the event node,and for the query energy cost,since As long as the grids are small enough,we may assume the query procedure contains the query forwarding process the frequency density function is uniform inside each grid, and query replying process,it can be measured as twice the thus we may approximate the frequency fi(Gi)for each grid Euclidean distance between storage node Si and the query Gi.And we set a threshold y(0d(S:,0).W; (5) above analysis: 03E0 f(x,）=fe,(x,y）+2fg(x,y) (2) In the above formula d(Si,O;)represents the distance from Therefore according to formula 1,we are able to get storage node Si(,y)to object O;(j,y).and we have: the optimal solution (y)by calculating the following equations: d(S,0)=V(x-x)2+(g-功)2 (6) And the approximate overall energy consumption is: aE =0 4=0 =0 X Y (-小f(x,） 3) Eoveralt=∑E=∑∑d(S,O,)-W (7) J0J01 V(红4-x2+(-)2 dxdy =0 SIES SIESO,EO Formula 3 depicts a methodology in common sense to solve Thus based on the above methodology we can approximate the optimization problem,however,note that the frequency the optimal solution S(z*,y*)by calculating the following density function fi(r,y)sometimes may be too complicated equations: for us to get its integral formation,thus it's difficult to utilize analytical method to get the optimal solution for the a它 (-)Wi V√工-工2+(-)2 =0 above cases,therefore we have to figure out an effective (y-v)W (8) approximation algorithm for the optimal solution. j=1 V-P+g-=0 IV.APPROXIMATION ALGORITHM FOR OPTIMAL Now we consider the calculation steps for (x*,y),first SOLUTION take the calculation steps of z*into consideration,according to formula 8.we have: A.Principle Due to the complexity of the frequency density function (x-x)·W fi(,y),this integral formation is difficult for us to calculate 1V(x-防)2+(g-严 0 978-1-4244-2324-8/08/S25.00©2008EEE. This full text paper3舐B9 ened esieti4g碍BFR8ia8sfi6件Hs0 e RUsPIE型头6rE琵slt88y"2008 proceedings
for event set E = {E1, E2, ..., Ek} and query set Q = {Q1, Q2, ..., Qk}, so as to minimize the overall energy consumption for sensor network. And being aware of fei (x, y) and fqi (x, y) for storage node Si, we need to consider how to utilize the storage replication scheme to balance energy consumption among storage nodes. Before we start to analyze this problem, we first describe the energy consumption model in this paper. The energy cost model is simplified by the assumption that the transmission cost is proportional to the data size and the hop distance between the sender and the receiver. In a densely deployed sensor network, the hop distance between two sensors is proportional to the Euclidean distance, and without loss of generality, we assume the data sizes are all equal in our model, therefore, in this paper, we use Euclidean distance to measure the energy consumption. For any storage and query process of event Ei, the energy consumption is mainly composed of two parts: event storage energy cost and query energy cost, thus according to the above energy consumption model, the storage energy cost can be measured as the Euclidean distance between storage node Si and the event node, and for the query energy cost, since the query procedure contains the query forwarding process and query replying process, it can be measured as twice the Euclidean distance between storage node Si and the query node. Thus the overall energy consumption for event storage and query of event Ei can be illustrated as : Ei = X 0 Y 0 (xi − x)2 + (yi − y)2 · fi(x, y)dxdy (1) In formula 1, (xi, yi) is the coordinate of storage node Si, fi(x, y) is the frequency density function, which means the number of events and queries at coordinate (x, y) over a square X × Y field. It has the following definition according to the above analysis: fi(x, y) = fei (x, y)+2fqi (x, y) (2) Therefore according to formula 1, we are able to get the optimal solution (x∗ i , y∗ i ) by calculating the following equations: ∂Ei ∂xi = 0 ∂Ei ∂yi = 0 ⇒ ⎧ ⎨ ⎩ X 0 Y 0 √ (xi−x)·fi(x,y) (xi−x)2+(yi−y)2 dxdy = 0 X 0 Y 0 √ (yi−y)·fi(x,y) (xi−x)2+(yi−y)2 dxdy = 0 (3) Formula 3 depicts a methodology in common sense to solve the optimization problem, however, note that the frequency density function fi(x, y) sometimes may be too complicated for us to get its integral formation, thus it’s difficult to utilize analytical method to get the optimal solution for the above cases, therefore we have to figure out an effective approximation algorithm for the optimal solution. IV. APPROXIMATION ALGORITHM FOR OPTIMAL SOLUTION A. Principle Due to the complexity of the frequency density function fi(x, y), this integral formation is difficult for us to calculate Fig. 1. Storage Placement among the Object Points the optimal solution (x∗ i , y∗ i ). To reduce the complexity of the calculation, we can select some representative points as an object set to depict the distribution function. We partition the monitoring area into m equal-sized grids, then we compute the distribution frequency fi(Gj ) for storage and query of event Ei inside every grid Gj : fi(Gj ) = fei (Gj )+2fqi (Gj ) = (x,y)∈Gj fei (x, y)+2fqi (x, y)dxdy (4) As long as the grids are small enough, we may assume the frequency density function is uniform inside each grid, thus we may approximate the frequency fi(Gj ) for each grid Gj . And we set a threshold γ (0 γ, we set the center of this grid Gj as an object point Oj , and we tag it with a weight Wj equal to fi(Gj ). Therefore, after this procedure, we can have several objects scattered over the deployment area, we denote them as an object set O with cardinality equal to n, as Fig. 1 shows. Thus the approximate energy consumption for event storage and query is: E i = Oj∈O d(Si, Oj ) · Wj (5) In the above formula d(Si, Oj ) represents the distance from storage node Si(x, y) to object Oj (xj , yj ), and we have: d(Si, Oj ) = (x − xj )2 + (y − yj )2 (6) And the approximate overall energy consumption is: Eoverall = Si∈S E i = Si∈S Oj∈O d(Si, Oj ) · Wj (7) Thus based on the above methodology we can approximate the optimal solution S∗ i (x∗, y∗) by calculating the following equations: ∂E i ∂x = 0 ∂E i ∂y = 0 ⇒ ⎧ ⎨ ⎩ n j=1 √ (x−xj )·Wj (x−xj )2+(y−yj )2 = 0 n j=1 √ (y−yj )·Wj (x−xj )2+(y−yj )2 = 0 (8) Now we consider the calculation steps for (x∗, y∗), first take the calculation steps of x∗ into consideration, according to formula 8, we have: n j=1 (x − xj ) · Wj (x − xj )2 + (y − yj )2 = 0 This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE "GLOBECOM" 2008 proceedings. 978-1-4244-2324-8/08/$25.00 © 2008 IEEE. 2 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:40:16 UTC from IEEE Xplore. Restrictions apply.
Hence from the above formula we obtain: And from steps of Algorithm 1,we can deduce the recursive x·W formation of calculating aj.k,there exists: =P+-市 i·W 台V-2+(y- ai.k W∑1.k-1 (9) /”11.k-1(1-工P+∑-1a4,k-1-(1-】严 (15) Therefore according to formula 9,we define aj(,y)as 0j,0= dj.o follows: Based on the above recursive relationship between aj.and a(x,y）= W jk+1 it is sufficient to prove limk=1.due (10) 1, V(工-x2+(y-P to space constraints of this paper,we omit the detail proof procedure here. ■ Through replacing the counterpart in formula 9 with j(,y). we have: B.Algorithm Algorithm I Iterative Approximation of the Optimal Solu- ∑a(c,)=∑·a,) tion i=1 j=1 Step 1.First calculate the gravity point (G,yG)of the object set O,which is actually the optimal solution for the We extract z from the left part of the equation,then we get: problem of E=oo(si,Oj).Wj,thus we have: aj(r,y) E=4色功 W =∑=1（元 w小·x防 =∑=1(w) (16) And we further define Bi(r,y)as follows: We set it as the initial solution,so we have T0=TG ai(x,y) 6(x,）= ∑1a(c,刃 (11) o=yG Step 2.Execute the iteration procedure: Hence we have: k+1=86,职：西 (17) 1k+1=∑5=1k,)·劝 月（） Siep3.Check that if|k+-s|≤eand|+-业|≤e(e j=1 is a constant and 0<<1).if so,we will stop the iteration Similarly,we have the following equation to calculate y: and go to Step 4,else k =k+1,go to Step 2. 2 Step 4.Set k+1as the final approximate solu- y=∑，)·劝 y*=张+1 tion. j=1 Here in Step I we utilize the gravity point(xG,UG)as the Thus we finally have the following recursive equations: initial solution,the motivation is to make the convergence x=n procedure have fewer iteration rounds compared with the {苏张副 (12)random selection strategy for initial solution,it is actually not a necessary premise for the iterative algorithm. Therefore we can calculate the optimal solution (,y) V.LOAD BALANCE SCHEME FOR STORAGE PLACEMENT through iteration based on equations 12.We will illustrate the iteration steps in detail with Algorithm 1,but before that,we A.Principle prove the convergence of this iteration procedure. Theorem linThe iteration result of Storage xk+1=】 will converge to the optimal solution (,) Proof:We define the Euclidean distance from storage point S to object O;after the kth iteration as di.k,thus to prove the theorem,we just need to prove: Node Node lim dj.k+1=1 (13) k-∞di.k Fig.2.Communication Paradigm of Storage Nodes From formula 10,we getthus we only have to prove: Analyzing on the model proposed in Section 3,note that each storage node will receive event messages from event lim a1,k+1=1 (14) k→0∞0j,k nodes and query messages from query nodes,and will send 978-1-4244-2324-8/08/S25.00©2008EEE. 3 This full text paper,B9dise4vgfE毛rfei98sO6P9件形69s代hlim艳E头6r裙sfl8P”2008 proceedings
Hence from the above formula we obtain: n j=1 x · Wj (x − xj )2 + (y − yj )2 = n j=1 xj · Wj (x − xj )2 + (y − yj )2 (9) Therefore according to formula 9, we define αj (x, y) as follows: αj (x, y) = Wj (x − xj )2 + (y − yj )2 (10) Through replacing the counterpart in formula 9 with αj (x, y), we have: n j=1 x · αj (x, y) = n j=1 xj · αj (x, y) We extract x from the left part of the equation, then we get: x = n j=1 αj (x, y) n j=1 αj (x, y) · xj And we further define βi(x, y) as follows: βj (x, y) = αj (x, y) n j=1 αj (x, y) (11) Hence we have: x = n j=1 βj (x, y) · xj Similarly, we have the following equation to calculate y: y = n j=1 βj (x, y) · yj Thus we finally have the following recursive equations: x = n j=1 βj (x, y) · xj y = n j=1 βj (x, y) · yj (12) Therefore we can calculate the optimal solution (x∗ i , y∗ i ) through iteration based on equations 12. We will illustrate the iteration steps in detail with Algorithm 1, but before that, we prove the convergence of this iteration procedure. Theorem 1: The iteration result of xk+1 = n j=1 β(xk, yk) · xj yk+1 = n j=1 β(xk, yk) · yj will converge to the optimal solution (x∗ i , y∗ i ). Proof: We define the Euclidean distance from storage point S to object Oj after the kth iteration as dj,k, thus to prove the theorem, we just need to prove: lim k→∞ dj,k+1 dj,k = 1 (13) From formula 10, we get αj,k(x, y) = Wj dj,k , thus we only have to prove: lim k→∞ αj,k+1 αj,k = 1 (14) And from steps of Algorithm 1, we can deduce the recursive formation of calculating αj,k, there exists: ⎧ ⎨ ⎩ αj,k = Wj · n √ l=1 αl,k−1 [ n l=1 αl,k−1·(xl−xj )]2+[ n l=1 αl,k−1·(yl−yj )]2 αj,0 = Wj dj,0 (15) Based on the above recursive relationship between αj,k and αj,k+1, it is sufficient to prove limk→∞ αj,k+1 αj,k = 1, due to space constraints of this paper, we omit the detail proof procedure here. B. Algorithm Algorithm 1 Iterative Approximation of the Optimal Solution Step 1. First calculate the gravity point (xG, yG) of the object set O, which is actually the optimal solution for the problem of Ei = Oj∈O d2(si, Oj ) · Wj , thus we have: xG = n j=1 ( Wj n j=1 Wj ) · xj yG = n j=1 ( Wj n j=1 Wj ) · yj (16) We set it as the initial solution, so we have x0 = xG y0 = yG . Step 2. Execute the iteration procedure: xk+1 = n j=1 β(xk, yk) · xj yk+1 = n j=1 β(xk, yk) · yj (17) Step 3. Check that if | xk+1−xk xk | ≤ ε and | yk+1−yk yk | ≤ ε (ε is a constant and 0 <ε< 1), if so, we will stop the iteration and go to Step 4, else k = k + 1, go to Step 2. Step 4. Set x∗ = xk+1 y∗ = yk+1 as the final approximate solution. Here in Step 1 we utilize the gravity point (xG, yG) as the initial solution, the motivation is to make the convergence procedure have fewer iteration rounds compared with the random selection strategy for initial solution, it is actually not a necessary premise for the iterative algorithm. V. LOAD BALANCE SCHEME FOR STORAGE PLACEMENT A. Principle Fig. 2. Communication Paradigm of Storage Nodes Analyzing on the model proposed in Section 3, note that each storage node will receive event messages from event nodes and query messages from query nodes, and will send This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE "GLOBECOM" 2008 proceedings. 978-1-4244-2324-8/08/$25.00 © 2008 IEEE. 3 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:40:16 UTC from IEEE Xplore. Restrictions apply.
out reply messages on receiving the query messages,as Figure 2 shows.In a typical application scenario with so many event and query messages,the storage nodes may become hot spots of the sensor network,thus causing single point of failure of the data-centric storage scheme.Therefore after we have decided the optimal placement of storage nodes,we need to further utilize the storage replication scheme to remove these hot spots. We assume the energy consumption for receiving a message as E,and the energy consumption for sending a message as Es,thus we calculate the burden factor Bi for each storage Fig.3.Ring based Storage Replication Scheme node S;as follows: Bi [fe(x,y）·Er+f4(x,y)·(Er+E)drdy (18) The burden factor represents the overall energy consumption of storage node Si. Considering the structure of storage replication scheme,we Original Storage Peint propose a ring based redundancy mechanism to balance the Splited Storage Points load according to each storage node Si's burden,as Figure 3 shows,the ring based replication storages are deployed around the optimal storage point.Here we set a threshold B,then for Fig.4.Handle the coincident storage placement problem with"phantom" each storage node Si.if there exists Bi>B,the ring based storage nodes replication structure will be applied for this storage point, otherwise only one storage node is selected according to the Ring Structure Construction:The base station first utilizes optimal storage point.Assume ro is the unit length for radius according to the burden factor Bi,thus we get the radius Ri Algorithm 1 to calculate the optimal storage placement set S= for each storage node Si: [S1,S2,...,Sk}according to the prior knowledge of event and query distribution,then it broadcasts this information to the 了(B-B)0st.B sensor network,and leverages GPSR routing protocol to notify s.t.B≤B (19) the nearest sensor nodes to the storage points as the storage nodes.After this procedure,all sensor nodes will be aware Here we leverage the ring based structure around the storage of the storage point Si for each event Ei,and each of those point instead of a solid round replicated storage area with the nodes which are selected as the storage nodes will decide its storage point set as the center,the reason is that considering ring size according to its pre-computed burden factor Bi,if the existence of sensor network's regional failures,we should the ring structure is needed,the storage node will broadcast a deploy those replicated storage nodes as scattered as possible, message which contains the hop-count for ring construction, and meanwhile the replication structure's energy efficiency each sensor nodes which receives the message will increase the should also be considered,thus the ring based structure is hop-count and forward the message,thus those sensor nodes much more appropriate for this consideration.Assume the whose hop-counts are equal to [Ri/d]will be selected as average distance between sensor nodes is d.therefore we can storage nodes on the ring structure. get n,the number of replicated storage nodes in the ring Routing Mechanism:The routing mechanism mainly in- structure:n=2.Therefore we can conclude that the larger cludes two routing methods:the centripetal routing and round- the original burden for the storage is,the more number of ring routing.As Figure 3 shows,the black nodes represent replicated storages it will get. the event or query nodes,the white nodes represent the Note that there may exist such situations that several event storage points.If the event or query node is outside the storage placements may point to exactly one storage node,thus ring,the centripetal routing method routes messages towards the burden for this storage may be so heavy,for this case,our the storage point which is the center of the ring,otherwise strategy is to split each of them into corresponding neighbor if the event or query node is inside the ring,which gets nodes around the storage point,which we may call "phantom" the position information during the ring construction phase, nodes,and construct different ring structures around those it routes messages in the direction right against the storage phantasm storage points,just as Figure 4 shows. point,which is actually in the anti-centripetal direction.The round-ring routing method routes messages clockwise or anti- B.Ring Structure Construction and Routing Mechanism clockwise around the ring structure.Both methods leverages In this section we will illustrate the distributed approach for the GPSR routing mechanisms,and for the round-ring routing ring structure construction and routing mechanism. method it further leverages the"routing on the curve"method 978-1-4244-2324-8/08/S25.00©2008EEE. A This full text paper乐B59 ensed asteiet4vafF毛feY8i98sfyA形67s0Teli7eE型头6rEsl8P”2008 proceedings
out reply messages on receiving the query messages, as Figure 2 shows. In a typical application scenario with so many event and query messages, the storage nodes may become hot spots of the sensor network, thus causing single point of failure of the data-centric storage scheme. Therefore after we have decided the optimal placement of storage nodes, we need to further utilize the storage replication scheme to remove these hot spots. We assume the energy consumption for receiving a message as Er, and the energy consumption for sending a message as Es, thus we calculate the burden factor Bi for each storage node Si as follows: Bi = X 0 Y 0 [fei (x, y) · Er + fqi (x, y) · (Er + Es)]dxdy (18) The burden factor represents the overall energy consumption of storage node Si. Considering the structure of storage replication scheme, we propose a ring based redundancy mechanism to balance the load according to each storage node Si’s burden, as Figure 3 shows, the ring based replication storages are deployed around the optimal storage point. Here we set a threshold B, then for each storage node Si, if there exists Bi > B, the ring based replication structure will be applied for this storage point, otherwise only one storage node is selected according to the optimal storage point. Assume r0 is the unit length for radius according to the burden factor Bi, thus we get the radius Ri for each storage node Si: Ri = (Bi − B) · r0 s.t. Bi > B 0 s.t. Bi ≤ B (19) Here we leverage the ring based structure around the storage point instead of a solid round replicated storage area with the storage point set as the center, the reason is that considering the existence of sensor network’s regional failures, we should deploy those replicated storage nodes as scattered as possible, and meanwhile the replication structure’s energy efficiency should also be considered, thus the ring based structure is much more appropriate for this consideration. Assume the average distance between sensor nodes is d, therefore we can get n, the number of replicated storage nodes in the ring structure: n = 2πRi d . Therefore we can conclude that the larger the original burden for the storage is, the more number of replicated storages it will get. Note that there may exist such situations that several event storage placements may point to exactly one storage node, thus the burden for this storage may be so heavy, for this case, our strategy is to split each of them into corresponding neighbor nodes around the storage point, which we may call “phantom” nodes, and construct different ring structures around those phantasm storage points, just as Figure 4 shows. B. Ring Structure Construction and Routing Mechanism In this section we will illustrate the distributed approach for ring structure construction and routing mechanism. Fig. 3. Ring based Storage Replication Scheme Fig. 4. Handle the coincident storage placement problem with “phantom” storage nodes Ring Structure Construction: The base station first utilizes Algorithm 1 to calculate the optimal storage placement set S = {S1, S2, ..., Sk} according to the prior knowledge of event and query distribution, then it broadcasts this information to the sensor network, and leverages GPSR routing protocol to notify the nearest sensor nodes to the storage points as the storage nodes. After this procedure, all sensor nodes will be aware of the storage point Si for each event Ei, and each of those nodes which are selected as the storage nodes will decide its ring size according to its pre-computed burden factor Bi, if the ring structure is needed, the storage node will broadcast a message which contains the hop-count for ring construction, each sensor nodes which receives the message will increase the hop-count and forward the message, thus those sensor nodes whose hop-counts are equal to Ri/d will be selected as storage nodes on the ring structure. Routing Mechanism: The routing mechanism mainly includes two routing methods: the centripetal routing and roundring routing. As Figure 3 shows, the black nodes represent the event or query nodes, the white nodes represent the storage points. If the event or query node is outside the ring, the centripetal routing method routes messages towards the storage point which is the center of the ring, otherwise if the event or query node is inside the ring, which gets the position information during the ring construction phase, it routes messages in the direction right against the storage point, which is actually in the anti-centripetal direction. The round-ring routing method routes messages clockwise or anticlockwise around the ring structure. Both methods leverages the GPSR routing mechanisms, and for the round-ring routing method it further leverages the ”routing on the curve” method This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE "GLOBECOM" 2008 proceedings. 978-1-4244-2324-8/08/$25.00 © 2008 IEEE. 4 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:40:16 UTC from IEEE Xplore. Restrictions apply.
which is proposed by [13]. Therefore we compare the energy consumption for the two Therefore,when an event E;is discovered inside the sensor approaches,as we know that n=,thus we finally get: network,it first routes the event message towards the ring E。+Eg-E structure,utilizing the centripetal routing,when it hits the ring structure,it will leverage the round-ring routing to store Ei =∫JD2R(2m-1)R-)·fe(z)dd to each of the storage nodes over the ring structure.Similarly, +∫JD≥R(d-2R)·f.(c,y)dzdy when a query Q;is issued inside the sensor network,it first +∫JD<R(2m+1)R:-是-2D(z,)·fe.(c,y)drdw routes the query message towards the ring structure through +∫∫D<(d+2R-4D(x)f(c,)dd the centripetal routing,when it hits the ring structure,it will From the above formula we note that in some situation the leverage the round-ring routing to find the first storage node ring based replication storage scheme may be less energy- it meets,then the reply message will be routed to the query efficient than the original approach,it all depends on the ring node along the former routing trace. size and the event and query distributions.Anyway,the load balance goal is always achieved. C.Performance Analysis 2)Load Balance:As we have learned from Section 5.1,the energy consumption per storage node for original approach is: In this section we will analyze on the energy efficiency and load balance performance for our ring based replication B,=无c,E,ddy (23) storage. fa()(Er+E.).dzdy 1)Energy Efficiency:Based on the routing mechanism And the energy consumption per storage node for ring based described above,we can calculate E,the energy consumption replication storage scheme is: for event storage: B=6fe,E,:会d 2n (24) E,天6IDeg)-Rdrd +oo fa()(E +E).drdy +6乃2mR·2=)fc,0dd (20) Comparing the two energy consumption expressions we learn that when n is large enough,while the event storage Here D(r,y)is the the distance from the event/query position energy cost keeps nearly the same,the event query energy cost (y)to the center of the ring (i,),and we have D(,y)= will be greatly reduced totherefore,the event storage and V(x-i)2 +(y-i)2,then D(,y)-Ril is the energy query load is effectively balanced via the ring structure. consumption for centripetal routing,its value depends on the sensor node's position to the ring,that is whether it is inside or VI.EXPERIMENTAL EVALUATION outside the ring.And is the energy consumption We have implemented a simulator to simulate the event for round-ring routing in average case.Thus we further have: and query distributions over the deployed sensor networks, thus to evaluate the performance of EEBASS.We consider a E。=∫JD2r(D(a,)-R):fe:(z,)ddy network composed of 10000 sensor nodes randomly deployed +Jp≥R2xR:.2n品）·fe,(e,0drd in a 100 x 100 square field,and we randomly generate the +∫JD<R(B:-D(z,)·fe.(e,)drdy event and query distributions.Here we set the average distance +∫JD<R(2mR·22n)fe,(z,y)drdy d=1,and we calculate the length of routing paths as the energy consumption metric. Similarly the energy consumption E for event query is: A.Convergence of Our Approximate Algorithm ED(,)-Ral-2fa()drdy Figure 5(a)shows the iterative convergence of our approx- +06(2mR·六）2f.(a,)dzd 21) imate algorithm.We vary the convergence threshold e from 10-2 to 10-8,testing how many iterative steps in average are necessary to satisfy the specified convergence threshold. And we can further have: We note that as the threshold grows from 10-2 to 10-8, Eg=∫JD≥R,(D(,）-R)·2f(z,)drdy the necessary number of iterative steps grows linearly from 6 to 29,which means our approximate algorithm has fast +∫JD≥2R,2mB:·品)2fa(e,)ddy convergence rate,even in the situation of e=10-8,our +p<R (Ri-D(,)).2fa(,y)dady approximate algorithm only needs 29 steps to reach that merit. +∫JD<R,(2xR·)·2f(c,)dd B.Energy Efficiency of Our Approximate Optimal Solution As we have learned from Section 4,the energy consumption In Figure 5(b),we compare the energy consumption for var- without ring based replication storage is: ious storage placements with our approximate optimal storage placement.To evaluate the energy efficiency,we generate a E=060 D(x,·(fe.(x,y）+2fg(x,)dzdy(22) sample distribution from which we extract 5 representative points with coordinates and weights.And we have:O1(0,0). 978-1-4244-2324-8/08/S25.00©2008EEE. 5 This full text paper,B9dise4vgfE毛rfei98sO6P9件形69s代hlim艳E头6r裙sfl8P”2008 proceedings
which is proposed by [13]. Therefore, when an event Ei is discovered inside the sensor network, it first routes the event message towards the ring structure, utilizing the centripetal routing, when it hits the ring structure, it will leverage the round-ring routing to store Ei to each of the storage nodes over the ring structure. Similarly, when a query Qi is issued inside the sensor network, it first routes the query message towards the ring structure through the centripetal routing, when it hits the ring structure, it will leverage the round-ring routing to find the first storage node it meets, then the reply message will be routed to the query node along the former routing trace. C. Performance Analysis In this section we will analyze on the energy efficiency and load balance performance for our ring based replication storage. 1) Energy Efficiency: Based on the routing mechanism described above, we can calculate Es, the energy consumption for event storage: Es = X 0 Y 0 |D(x, y) − Ri|dxdy + X 0 Y 0 (2πRi · 2n−1 2n ) · fei (x, y)dxdy (20) Here D(x, y) is the the distance from the event/query position (x, y) to the center of the ring (xi , yi), and we have D(x, y) = (x − xi)2 + (y − yi)2, then |D(x, y) − Ri| is the energy consumption for centripetal routing, its value depends on the sensor node’s position to the ring, that is whether it is inside or outside the ring. And 2πRi · 2n−1 2n is the energy consumption for round-ring routing in average case. Thus we further have: Es = D≥Ri (D(x, y) − Ri) · fei (x, y)dxdy + D≥Ri (2πRi · 2n−1 2n ) · fei (x, y)dxdy + D<Ri (Ri − D(x, y)) · fei (x, y)dxdy + D<Ri (2πRi · 2n−1 2n ) · fei (x, y)dxdy Similarly the energy consumption Eq for event query is: Eq = X 0 Y 0 |D(x, y) − Ri| · 2fqi (x, y)dxdy + X 0 Y 0 (2πRi · 1 2n ) · 2fqi (x, y)dxdy (21) And we can further have: Eq = D≥Ri (D(x, y) − Ri) · 2fqi (x, y)dxdy + D≥Ri (2πRi · 1 2n ) · 2fqi (x, y)dxdy + D<Ri (Ri − D(x, y)) · 2fqi (x, y)dxdy + D<Ri (2πRi · 1 2n ) · 2fqi (x, y)dxdy As we have learned from Section 4, the energy consumption without ring based replication storage is: E = X 0 Y 0 D(x, y) · (fei (x, y)+2fqi (x, y))dxdy (22) Therefore we compare the energy consumption for the two approaches, as we know that n = 2πRi d , thus we finally get: Es + Eq − E = D≥Ri ((2π − 1)Ri − d 2 ) · fei (x, y)dxdy + D≥Ri (d − 2Ri) · fqi (x, y)dxdy + D<Ri ((2π + 1)Ri − d 2 − 2D(x, y)) · fei (x, y)dxdy + D<Ri (d + 2Ri − 4D(x, y)) · fqi (x, y)dxdy From the above formula we note that in some situation the ring based replication storage scheme may be less energyefficient than the original approach, it all depends on the ring size and the event and query distributions. Anyway, the load balance goal is always achieved. 2) Load Balance: As we have learned from Section 5.1, the energy consumption per storage node for original approach is: Bi = X 0 Y 0 fei (x, y) · Er · dxdy + X 0 Y 0 fqi (x, y) · (Er + Es) · dxdy (23) And the energy consumption per storage node for ring based replication storage scheme is: B i = X 0 Y 0 fei (x, y) · Er · 2n−1 2n dxdy + X 0 Y 0 fqi (x, y) · (Er + Es) · 1 2n dxdy (24) Comparing the two energy consumption expressions we learn that when n is large enough, while the event storage energy cost keeps nearly the same, the event query energy cost will be greatly reduced to 1 2n , therefore, the event storage and query load is effectively balanced via the ring structure. VI. EXPERIMENTAL EVALUATION We have implemented a simulator to simulate the event and query distributions over the deployed sensor networks, thus to evaluate the performance of EEBASS. We consider a network composed of 10000 sensor nodes randomly deployed in a 100 × 100 square field, and we randomly generate the event and query distributions. Here we set the average distance d = 1, and we calculate the length of routing paths as the energy consumption metric. A. Convergence of Our Approximate Algorithm Figure 5(a) shows the iterative convergence of our approximate algorithm. We vary the convergence threshold ε from 10−2 to 10−8, testing how many iterative steps in average are necessary to satisfy the specified convergence threshold. We note that as the threshold grows from 10−2 to 10−8, the necessary number of iterative steps grows linearly from 6 to 29, which means our approximate algorithm has fast convergence rate, even in the situation of ε = 10−8, our approximate algorithm only needs 29 steps to reach that merit. B. Energy Efficiency of Our Approximate Optimal Solution In Figure 5(b), we compare the energy consumption for various storage placements with our approximate optimal storage placement. To evaluate the energy efficiency, we generate a sample distribution from which we extract 5 representative points with coordinates and weights. And we have: O1(0, 0), This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE "GLOBECOM" 2008 proceedings. 978-1-4244-2324-8/08/$25.00 © 2008 IEEE. 5 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:40:16 UTC from IEEE Xplore. Restrictions apply.
010 10 (a)Convergence Rate of Approximate Algorithm (b)Energy Cost for Various Storage Placements (c)Energy Cost for Various Storage Placements Fig.5.Experimental Evaluation for Effectiveness of EEBASS W1=3:O2(1,2),W2=4:O3(2,0),W3=5;O4(3,2), [2]R.Sylvia,K.Brad,S.Scott,E.Deborah,G.Ramesh,Y.Li,and Y.Fang, W =6;O5(4,1),W5 =7.We divide the area into equal "Data-centric storage in sensomets with ght,a geographic hash table." grids,and calculate the energy consumption for each grid cen- Mobile Net-works and Applications,vol.8.no.4.pp.427-442.2003. [3]G.Deepak,E.Deborah,and H.John."Dimensions:Why do we need a ter as a candidate storage point,we note that the lowest point new data handling architecture for sensor networks,"ACM S/GCOMM of the energy consumption contour roughly lies in the area Computer Communication Review,vol.33,no.1,pp.143-148.2003. with x∈(2.5,3)andy∈(2.0,2.5)，and our approximated [4]X.Li,Y.J.Kim,R.Govindan,and W.Hong."Multi-dimensional range queries in sensor networks,"in Sensys,2003. optimal solution S*(2.83,2.25)right falls into this area,which [5]R.Sarkar,X.J.Zhu,and J.Gao."Double rulings for information sufficiently proves the accuracy of our approximate solution. brokerage in sensor networks,"in MOB/COM,2006. [6]X.Liu,Q.Huang,and Y.Zhang."Combs,needles,haystacks:balancing C.Load Balance Effect of Ring based Replication Scheme push and pull for discovery in large-scale sensor networks,"in Sensys, 2004. Figure 5(c)depicts the load balance comparison between [7]Q.Fang,J.Gao,and L.J.Guibas,"Landmark-based information storage and retrieval in sensor networks,"in INFOCOM,2006. original storage scheme and ring based replication scheme. [8]J.Ahn and B.Krishnamachari,"Fundamental scaling laws for energy- Here for one specified storage node we set fe =10,fa= efficient storage and querying in wireless sensor networks,"in MobiHoc. 20,Er =Es=1.We note that the energy consumption for 2006. original storage scheme is 50,and with the aid of ring based [9]B.Sheng,Q.Li,and W.Mao."Data storage placement in sensor networks,"in MobiHoc,2006. replication structure,the energy consumption is significantly [10]-"An approximation algorithm for data storage placement in sensor reduced,when the replication number n=20,the energy networks."in WASA.2007. consumption is only 10.75,79%of the energy consumption is [11]G.C.W.S.Zhang and T.L.Porta,"Data dissemination with ring-based index for wireless sensor networks,"in /CNP,2003. saved compared to the original scheme [12]M.Aly,K.Pruhs,and P.K.Chrysanthis,"Kddcs:a load-balanced in- network data-centric storage scheme for sensor networks,"in C/KM, VII.CONCLUSION 2006. [13]B.Nath and D.Niculescu,"Routing on a curve,"ACM S/GCOMM This paper proposes an approximation algorithm to solve the Computer Communication Review,vol.33,no.1,pp.155-160,2003. optimal storage placement problem according to the variance of event and query distribution,aiming to minimize the total energy consumption for data-centric storage scheme.And it further leverages the ring based replication structure to achieve the load balance goal.Simulation results show that EEBASS is more balanced and energy efficient than the traditional data- centric storage mechanism in sensor network. VIII.ACKNOWLEDGEMENT This work is supported by the China NSF grant(60573132, 60673154),the China 973 project(2006CB303000),the China 863 project (2006AA01Z199)and the Jiangsu Provincial High-Tech Research Program (BK2006029). The authors would like to thank Yingpei Zeng,Zhuo Li for giving comments and feedbacks for this paper. REFERENCES [1]S.Scott,R.Sylvia,K.Brad,G.Ramesh,and E.Deborah,"Data-centric storage in sensornets,"ACM SIGCOMM Computer Communication Review,vol.33,no.1,Pp.137-142,2003. 978-1-4244-2324-8/08/S25.00©2008EEE. 6 This full text paper乐B59 ed asediertiNan5毛rfey8a8sf6件H6ef0ei艳E头6E裙sflt89y4”2008 proceedings
5 10 15 20 25 30 N um ber ofIteration Steps 10e-2 10e-3 10e-4 10e-5 10e-6 10e-7 10e-8 Threshold (a) Convergence Rate of Approximate Algorithm 0 1 2 3 4 5 6 7 0 1 2 3 4 5 40 50 60 70 80Z Axis Y Axis X Axis (b) Energy Cost for Various Storage Placements 0 10 20 30 40 50 O riginalStructure n=2 n=10 n=20 Energy C onsum ption R eplication N um ber (c) Energy Cost for Various Storage Placements Fig. 5. Experimental Evaluation for Effectiveness of EEBASS W1 = 3; O2(1, 2), W2 = 4; O3(2, 0), W3 = 5; O4(3, 2), W4 = 6; O5(4, 1), W5 = 7. We divide the area into equal grids, and calculate the energy consumption for each grid center as a candidate storage point, we note that the lowest point of the energy consumption contour roughly lies in the area with x ∈ (2.5, 3) and y ∈ (2.0, 2.5), and our approximated optimal solution S∗(2.83, 2.25) right falls into this area, which sufficiently proves the accuracy of our approximate solution. C. Load Balance Effect of Ring based Replication Scheme Figure 5(c) depicts the load balance comparison between original storage scheme and ring based replication scheme. Here for one specified storage node we set fe = 10, fq = 20, Er = Es = 1. We note that the energy consumption for original storage scheme is 50, and with the aid of ring based replication structure, the energy consumption is significantly reduced, when the replication number n = 20, the energy consumption is only 10.75, 79% of the energy consumption is saved compared to the original scheme. VII. CONCLUSION This paper proposes an approximation algorithm to solve the optimal storage placement problem according to the variance of event and query distribution, aiming to minimize the total energy consumption for data-centric storage scheme. And it further leverages the ring based replication structure to achieve the load balance goal. Simulation results show that EEBASS is more balanced and energy efficient than the traditional datacentric storage mechanism in sensor network. VIII. ACKNOWLEDGEMENT This work is supported by the China NSF grant (60573132, 60673154), the China 973 project (2006CB303000), the China 863 project (2006AA01Z199) and the Jiangsu Provincial High-Tech Research Program (BK2006029). The authors would like to thank Yingpei Zeng, Zhuo Li for giving comments and feedbacks for this paper. REFERENCES [1] S. Scott, R. Sylvia, K. Brad, G. Ramesh, and E. Deborah, “Data-centric storage in sensornets,” ACM SIGCOMM Computer Communication Review, vol. 33, no. 1, pp. 137–142, 2003. [2] R. Sylvia, K. Brad, S. Scott, E. Deborah, G. Ramesh, Y. Li, and Y. Fang, “Data-centric storage in sensornets with ght, a geographic hash table,” Mobile Net-works and Applications, vol. 8, no. 4, pp. 427–442, 2003. [3] G. Deepak, E. Deborah, and H. John, “Dimensions: Why do we need a new data handling architecture for sensor networks,” ACM SIGCOMM Computer Communication Review, vol. 33, no. 1, pp. 143–148, 2003. [4] X. Li, Y. J. Kim, R. Govindan, and W. Hong, “Multi-dimensional range queries in sensor networks,” in Sensys, 2003. [5] R. Sarkar, X. J. Zhu, and J. Gao, “Double rulings for information brokerage in sensor networks,” in MOBICOM, 2006. [6] X. Liu, Q. Huang, and Y. Zhang, “Combs, needles,haystacks: balancing push and pull for discovery in large-scale sensor networks,” in Sensys, 2004. [7] Q. Fang, J. Gao, and L. J. Guibas, “Landmark-based information storage and retrieval in sensor networks,” in INFOCOM, 2006. [8] J. Ahn and B. Krishnamachari, “Fundamental scaling laws for energyefficient storage and querying in wireless sensor networks,” in MobiHoc, 2006. [9] B. Sheng, Q. Li, and W. Mao, “Data storage placement in sensor networks,” in MobiHoc, 2006. [10] ——, “An approximation algorithm for data storage placement in sensor networks,” in WASA, 2007. [11] G. C. W. S. Zhang and T. L. Porta, “Data dissemination with ring-based index for wireless sensor networks,” in ICNP, 2003. [12] M. Aly, K. Pruhs, and P. K. Chrysanthis, “Kddcs: a load-balanced innetwork data-centric storage scheme for sensor networks,” in CIKM, 2006. [13] B. Nath and D. Niculescu, “Routing on a curve,” ACM SIGCOMM Computer Communication Review, vol. 33, no. 1, pp. 155–160, 2003. This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE "GLOBECOM" 2008 proceedings. 978-1-4244-2324-8/08/$25.00 © 2008 IEEE. 6 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:40:16 UTC from IEEE Xplore. Restrictions apply
