一種分布式的1-柵欄覆蓋構(gòu)建算法
doi: 10.11999/JEIT150664 cstr: 32379.14.JEIT150664
基金項目:
浙江省自然科學基金(LY14F020020, LQ12F02015)，國家自然科學基金( 61379023, 61401397)
A Distributed Algorithm for Constructing 1-barrier Coverage
Funds:
The Natural Science Foundation of Zhejiang Province (LY14F020020, LQ12F02015), The National Natural Science Foundation of China (61379023, 61401397)
-
摘要: 在構(gòu)建柵欄覆蓋的過程中，需要考慮網(wǎng)絡構(gòu)建成本和生存時間這兩個核心問題。對于前者主要考慮節(jié)點數(shù)和信息傳輸量，而對于后者則應避免網(wǎng)絡因個別節(jié)點的死亡而陷入癱瘓。該文針對上述兩個問題，提出一種基于1-柵欄覆蓋的分布式柵欄覆蓋算法(Distributed Barrier Coverage Algorithm, DBCA)，算法通過聚類分簇和簇內(nèi)路徑選擇這兩個過程來實現(xiàn)覆蓋。理論分析和仿真結(jié)果表明，該文所提出的算法能夠有效減少網(wǎng)絡部署的節(jié)點數(shù)以及傳輸?shù)男畔⒘?。在部署?jié)點達到700時，該算法比最優(yōu)節(jié)點選擇算法(Optimal Node Selection Algorithm, ONSA)和本地柵欄覆蓋協(xié)議(Localized Barrier Coverage Protocol, LBCP)算法傳輸?shù)男畔⒘糠謩e減少25%和41.6%，生存時間分別多44%和30%。
-
關鍵詞:
- 無線傳感器網(wǎng)絡 /
- 柵欄覆蓋 /
- k-HOP分簇 /
- 最大流 /
- 路徑規(guī)劃
Abstract: The constructing cost and lifetime are two core problems when constructing a barrier coverage of Wireless Sensor Network (WSN). For the former, the amount of nodes and information transferred are considered very much. And the WSN shutdown Caused by just for some specific nodes died should be avoided. This paper proposes an algorithm named Distributed Barrier Coverage Algorithm (DBCA) to construct a distributed 1-barrier coverage by using k-HOP clustering and path planning. Theory analysis and simulation results show that the algorithm can reduce the number of nodes and information transferred effectively. When the deployed nodes reach the number of 700, it performs better than Optimal Node Selection Algorithm (ONSA) and Localized Barrier Coverage Protocol (LBCP) algorithm in reducing transferring information with 25% and 41.6%, and in prolonging lifetime with 44% and 30%.-
Key words:
- Wireless Sensor Network (WSN) /
- Barrier coverage /
- k-HOP clustering /
- Maximum flow /
- Path planning
-
杜曉玉, 孫力娟, 郭劍, 等. 異構(gòu)無線傳感器網(wǎng)絡覆蓋優(yōu)化算法[J]. 電子與信息學報, 2014, 36(3): 696702. doi: 10.3724/ SP.J.1146.2013.00730. DU Xiaoyu, SUN Lijuan, GUO Jian, et al. Coverage optimization algorithm for heterogeneous WSNs[J]. Journal of Electronics Information Technology, 2014, 36(3): 696702. doi: 10.3724/SP.J.1146.2013.00730. LI Mo, LI Zhenjiang, and ATHANASIOS V. A survey on topology control in wireless sensor networks: taxonomy, comparative study, and open issues[J]. Proceedings of the IEEE, 2013, 25(10): 23672380. doi: 10.1109/JPROC. 2013.2257631. AHMED N, KANHERE S S, and JHA S. Probabilistic coverage in wireless sensor networks[C]. IEEE Conference on Local Computer Networks, Sydney, 2005: 672681. doi: 10.1109/LCN.2005.109. SANTOSH Kumar, LAI T H, and ANISH Arora. Barrier coverage with wireless sensors[J]. Wireless Networks, 2007, 13(6): 817-834. TAO Dan and WU Tinyu. A survey on barrier coverage problem in directional sensor networks[J]. IEEE Sensors Journal, 2015, 15(2): 876885. doi: 10.1109/JSEN.2014. 2310180. YANG Guanqun and QIAO D. Barrier information coverage with wireless sensors[C]. INFOCOM 2009, Rio de Janeiro, 2009: 918-926. doi: 10.1109/INFCOM.2009.5062002. LAI Y L and JIANG J R. Sink-connected barrier coverage optimization for wireless sensor networks[C]. The Seventh International Conference on Wireless and Mobile Communications, Wuhan, 2011: 198203. FAN Haosheng, LI Minming, SUN Xianwei, et al. Barrier coverage by sensors with adjustable ranges[J]. ACM Transactions on Sensor Networks, 2014, 11(1): 14(1)14(20). CHEN Ai, SANTOSH Kumar, and LAI T H. Local barrier coverage in wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2010, 9(4): 491-504. doi: 10.1109/ TMC.2009.147. LIU B, DOUSSE O, NAIN P, et al. Dynamic coverage of mobile sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(2): 301311. doi: 10.1109/ TPDS.2012.141. 羅卿, 林亞平, 王雷, 等. 傳感器網(wǎng)絡中基于數(shù)據(jù)融合的柵欄覆蓋控制研究[J]. 電子與信息學報, 2012, 34(4): 826831. doi: 10.3724/SP.J.1146.2011.00446. LUO Qing, LIN Yaping, WANG Lei, et al. Barrier coverage control based on data fusion for wireless sensor network[J]. Journal of Electronics Information Technology, 2012, 34(4): 826831. doi: 10.3724/SP.J.1146.2011.00446. HOU T C and LI V O K. Transmission range control in multihop packet radio networks[J]. IEEE Transactions on Communications, 1986, 34(1): 3844. doi: 10.1109/TCOM. 1986.1096436. ZOU Y and CHAKRABARTY K. Sensor deployment and target localization in distributed sensor networks[J]. ACM Transactions on Embedded Computing Systems, 2004, 3(1): 6191. LI J, CHEN J, and LAI T H. Energy-efficient intrusion detection with a barrier of probabilistic sensors[C]. INFOCOM 2012, Orlando, 2012: 118126. doi: 10.1109/ INFCOM.2012.6195479. JING Yuan, BAE Egil, and TAI Xuecheng. A study on continuous max-flow and min-cut approaches[C]. IEEE Conference on Computer Vision and Pattern Recognition, San Francisco, 2010: 22172224. doi: 10.1109/CVPR.2010. 5539903. -
計量
- 文章訪問數(shù): 1524
- HTML全文瀏覽量: 117
- PDF下載量: 566
- 被引次數(shù): 0
下載:
