Distributed event-triggered path construction in wireless sensor networks

作     者：Lee, Chunseok Choi, Sunghee 

作者机构：Korea Adv Inst Sci & Technol Dept Comp Sci Taejon 305701 South Korea 

出 版 物：《WIRELESS NETWORKS》 (无线网络)

年 卷 期：2013年第19卷第1期

页      面：1-16页

核心收录：

学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Research Foundation of Korea (NRF) Korea government (MEST) [2010-0024092] 

主　　题：Wireless sensor networks Distributed algorithm Traveling salesman path Navigation 

摘      要：We consider the problem of guiding mobile agents to visit a subset of sensor nodes called event nodes in wireless sensor networks without location information, where the set of event nodes is not known in advance. As the set of event nodes changes over time, a path needs to be updated on-line. We propose a novel distributed algorithm to construct and update such a dynamic path to visit a set of event nodes. To the best of our knowledge, this is the first work to solve this problem using a distributed algorithm without any location information. Our approach is to maintain the Voronoi diagram of the dynamic set of event nodes implicitly in sensor networks. Doing so, we overcome the lack of location information and implement scalable distributed dynamic navigation. For computing an optimal path is NP-Hard, we prove that the ratio of the length of the constructed path by our algorithm to that of the optimal path is bounded by O(log k), where k is the number of event nodes, under a reasonable assumption. Our approach can be used to compute both an event visiting tour which requires to return to a starting point and an event visiting path which does not return to a starting point. We also extend our method to navigate multiple agents so that they collectively visit a set of event nodes.