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 in￾cludes two routing methods: the centripetal routing and round￾ring 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 anti￾clockwise 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.