Connected Sensor Cover Self-Organization of Sensor Networks for Efficient Query Execution(9)

Spatial query execution is an essential functionality of a sensor network, where a query gathers sensor data within a specific geographic region. Redundancy within a sensor network can be exploited to reduce the communication cost incurred in execution of

1 2 34Associated Candidate Paths: P 1, P 2, P 3, P 4

P 1 = < C 1, I 1> P 2 = < C 2, I 2, C 1, I 1>

R Q (a)

Figure 3:Working of The bene?t of a candidate path P is the total number of uncovered valid subelements covered by the sensors in P divided by the number of sensors that are in P but not in M .The most bene?cial candidate path is the candidate path that has the most bene?t among the given set of candidate paths.2EXAMPLE 2.Figure 3shows a set sensors M (solid cir-cular dots),the region covered by M ,query region R Q ,and sensing disks corresponding to some of the sensors not in M (hollow circular dots).Figure 3(a)and (b)depict two consecutive stages of the algorithm.

Let us consider the stage of the algorithm shown in Fig-ure 3(a).At this stage,there are at least four candidate sensors viz.C 1,C 2,C 3,C 4,as shown in the ?gure.The can-didate paths associated with the candidate sensors are re-spectively P 1,P 2,P 3,P 4as shown.For sake of clarity,we have not shown the set of sensors involved in the candidate paths P 3and P 4,but the ?gure shows the actual communi-cation edges and sensors involved in the candidate paths P 1and P 2.Let us assume that the most bene?cial candidate path at this stage is P 2.The algorithm then chooses P 2as P and adds the sensors C 1,I 2,and C 2to the set M .

The addition of sensors C 1,I 2,C 2to M yields the next stage of the algorithm shown in Figure 3(b).At this stage,the sensor I 5becomes a candidate sensor,while C 1no longer remains a candidate sensor.Also,the ?gure shows the re-calculated and new candidate paths connecting each of the candidate sensors C 3,C 4,I 5to some sensor in M .Here,we have assumed that the candidate path P 4doesn’t change from the previous stage,while the candidate path P 3changes to the communication edge (C 3,C 2).Now,at this stage,if P 3is the most bene?cial path at this stage,the algorithm would add the sensor C 3to M ,which yields the next stage (now shown in the ?gure).Finally,if the algorithm adds to M a candidate path P 4connecting C 4to some sensor in M ,the set of sensors M would now cover the entire query region and the algorithm returns the new M (obtained by adding C 3,C 4,and other sensors in P 4to the M shown in

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科Connected Sensor Cover Self-Organization of Sensor Networks for Efficient Query Execution(9)全文阅读和word下载服务。