A Minimal Rigid Topology Control Algorithm Based on Voronoi Coverage and Delaunay Triangulation in Wireless Sensor Networks
-
摘要: 为同时满足覆盖与节能应用需求，本文提出了无线传感器网络中一种最小刚性拓扑控制算法MRTc（Minimal rigid topology control algorithm based on Voronoi coverage and Delaunay triangulation）.该算法基于Voronoi覆盖机制，准确控制节点工作状态，实现活动节点对目标区域的完全覆盖.在此基础上，MRTc利用Delaunay三角剖分图的特点，构建出适用于无线传感器网络的最小刚性拓扑结构.该结构有效约束了网络平均节点度，且同时具有容错性、覆盖性和稀疏性.此外，MRTc引入节点功率控制策略，在维持网络完全覆盖的基础上最小化节点能耗.仿真结果进一步验证了本文提出的MRTc算法的有效性.
-
关键词:
- 无线传感器网络 /
- 拓扑控制 /
- 最小刚性 /
- Voronoi覆盖 /
- Delaunay三角剖分图
Abstract: This paper proposes a minimal rigid network topology control algorithm called minimal rigid topology control (MRTc), which is based on Voronoi coverage and Delaunay triangulation, to meet application needs of good coverage and for energy saving. MRTc can accurately control node operative modes by which the target sensing area can be completely covered only with active nodes. On the basis of complete coverage, MRTc constructs a topology that is applicable to wireless sensor networks by exploiting the characteristics of Delaunay triangulation. The topology structure can effectively restrict the average node degree, and the structure is characterized by its fault-tolerance, spread ability, and sparsity. Furthermore, MRTc also introduces a power control strategy to minimize the energy consumption of sensor nodes without losing complete coverage in the sensing area. Simulation results are provided to validate this proposal. -
图 2 刚性拓扑和可变形拓扑((a)刚性拓扑; (b)可变形拓扑; (c)最小刚性拓扑)
Fig. 2 The rigid topology and flexible topology ((a) Rigid topology; (b) Flexible topology; (c) Minimal rigid topology
图 3 节点的Voronoi图以及Delaunay三角剖分图
Fig. 3 The Voronoi graph and Delaunay triangulation of nodes
图 4 Delaunay三角剖分图逐点插入法((a)插入点$Q$在△$IJN$的内部; (b)插入点$Q$在边$JN$上)
Fig. 4 Point by point insertion method of Delaunay triangulation ((a) Insertion node $Q$ in the interior of a triangle △$IJN$; (b) Insertion node $Q$ is on the $JN$)
图 5 均匀网络睡眠调度((a)睡眠调度前; (b)睡眠调度后)
Fig. 5 The sleep scheduling in uniform networks ((a) Before the sleep scheduling; (b) After the sleep scheduling
图 6 随机网络睡眠调度((a)睡眠调度前; (b)睡眠调度后)
Fig. 6 The sleep scheduling in random networks ((a) Before the sleep scheduling; (b) After the sleep scheduling
图 7 两种网络中冗余节点数目和所占节点比例的比较((a)冗余节点个数的比较; (b)冗余节点比例的比较)
Fig. 7 The comparison of the number of redundant nodes and the proportion of redundant nodes in the two networks ((a) The comparison of the number of redundant nodes; (b) The comparison of the proportion of the redundant nodes
图 8 睡眠调度前后区域覆盖情况((a)睡眠调度前区域覆盖情况; (b)睡眠调度后区域覆盖情况)
Fig. 8 The area coverage by using the sleep scheduling ((a) The area coverage before sleep scheduling; (b) The area coverage after sleep scheduling
图 9 MRTc拓扑结构的构建过程((a)构建局部Delaunay三角剖分图; (b)构建局部最小刚性拓扑; (c)构建全局最小刚性拓扑)
Fig. 9 The construction process of MRTc topology ((a) The construction of local Delaunay triangulation; (b) The construction of local minimum rigid topology; (c) The construction of global minimum rigid topology
图 10 不同算法生成的拓扑结构((a) GG; (b) RNG; (c) LMST; (d) Udel; (e) MRTc)
Fig. 10 The topological structures of different algorithms ((a) GG; (b) RNG; (c) LMST; (d) Udel; (e) MRTc
图 11 不同算法的性能比较((a)平均节点度的比较; (b)平均传输半径的比较; (c)最大节点度的比较; (d)最小节点度的比较)
Fig. 11 The performance comparison of different algorithms ((a) The comparison of average node degree; (b) The comparison of average transmission radius; (c) The comparison of maximum node degree; (d) The comparison of minimum node degree
图 12 睡眠调度前后最小刚性拓扑性能((a)睡眠调度前后最小刚性拓扑总能耗; (b)睡眠调度前后最小刚性拓扑存活节点)
Fig. 12 The performances of minimum rigid topology before and after sleep scheduling ((a) Total energy consumption of the minimum rigid topology before and after sleep scheduling; (b) The proportion of survival nodes before and after sleep scheduling in minimum rigid topology
本文用到的符号 符号的含义 ${G_u}({\mathcal {V}_u},{\mathcal {E}_u})$ 网络节点构成的无向图,${\mathcal{V}_u}$为网络中节点的集合,${\mathcal{E}_u}$为可相互通信的链路集合; ${\bar G_u}({\bar {\mathcal {V}_u}},{\bar {\mathcal {E}_u}})$ 冗余节点构成的无向图,${\bar {\mathcal {V}_u}}$为冗余节点的集合,${\bar {\mathcal {E}_u}}$为互为 Voronoi 邻居的冗余节点间的链路集; $G(\mathcal {V},\mathcal {E})$ 传感器节点构成的网络拓扑,${\mathcal{V}}$为构成拓扑的传感器节点的集合,${\mathcal{E}}$为拓扑中链路的集合; ${G_m}({\mathcal {V}_m},{\mathcal {E}_m})$ 传感器节点构成的最小刚性拓扑,${\mathcal {V}_m}$为最小刚性拓扑中节点的集合,${\mathcal{E}_m}$为最小刚性拓扑中链路的集合; ${G_C}({\mathcal {V}_C},{\mathcal {E}_C})$ 传感器节点形成的初始拓扑; ${G_D}({\mathcal {V}_D},{\mathcal {E}_D})$ 经算法 MRTc 优化后得到的拓扑结构; ${G_j}({\mathcal {V}_j},{\mathcal {E}_j})$ 节点$j$与其邻居节点构成的基于 Delaunay 三角剖分图的局部最小刚性拓扑,${\mathcal {V}_j}$为节点$j$与其邻居节点的集合,${\mathcal {E}_j}$为该最小刚性拓扑中链路的集合; ${\hat G_i}({{\mathcal {V}_i}},{\hat {\mathcal {E}_i}})$ 由拓扑 ${G_i}({\mathcal {V}_i},{\mathcal {E}_i})$改变圈内的链路生成的新拓扑,${\mathcal {V}_i}$为节点$i$与其邻居节点的集合,${\hat {\mathcal {E}_i}}$为生成新拓扑的链路的集合; ${G_{ij}}({\mathcal {V}_{ij}},{\mathcal {E}_{ij}})$ 由拓扑 ${\hat G_i}({{\mathcal {V}_i}},{\hat {\mathcal {E}_i}})$和拓扑${G}({\mathcal {V}_j},{\mathcal {E}_j})$的公共节点组成的拓扑,${\mathcal {V}_{ij}}$为两个拓扑的公共节点的集合,${\mathcal {E}_{ij}}$为两个拓扑的公共链路的集合; $G'$ 拓扑结构$G$的一个子拓扑; $G''$ 子拓扑$G'$有相同节点的另一个刚性拓扑; $\hat G$ 刚性拓扑$G''$代替子拓扑$G'$得到的拓扑; $({l_u})_i^j$ 无向图中可以相互通信的节点间的链路; $({\bar l_u})_i^j$ 互为 Voronoi 邻居的冗余节点间的链路; $l_i^j$ 网络拓扑中可以相互通信的节点间的链路; ${l'_q}(q=1,\cdots,m)$ 局部最小刚性拓扑$G_i$中的$m$条链路; ${l'_p}(p=1,\cdots,m)$ 局部最小刚性拓扑${{G}_{j}}(i\ne j)$中的$m$条链路; ${\mathcal {N}_i}$ 节点 $i$的通信邻居的集合; ${\mathcal {N}_i}^\prime $ 节点$i$的逻辑邻居节点集合; ${D_i}$ 节点$i$的度; $i_2^{VV}$ 节点$i$的 2-Voronoi 顶点; $i_2^{VIP}$ 节点$i$的 2-Voronoi 交点; ${q_i}(t)$ 节点$i$的位置函数; $(q_i^1,q_i^2)$ 节点$i$的位置坐标; $id(i)$ 节点$i$的 ID; $P_i^j$ 节点$i$和$j$信息成功传输所需的功率; $d_i^j$ 节点$i$和$j$的欧氏距离; $w_i^j$ 链路$l_i^j$的权重函数; ${r_c}$ 节点的通信半径; ${r_s}$ 节点的感知半径; $M$ Delaunay 三角剖分图对应的刚性矩阵; ${M_{f}}$ 最小刚性图对应的刚性矩阵; ${D_{ev}}$ 网络的平均节点度; $|\mathcal {E}|$ 拓扑结构中链路的数目; ${a_s}$ 拓扑${\hat G_i}$与${G_j}$的公共链路; ${b_{s1}}$ ${\mathcal {E}_{ij}}$中仅存在于${\hat G_i}$中的链路; ${b_{s2}}$ ${\mathcal {E}_{ij}}$中仅存在于${G_j}$中的链路; ${r_a}$ 每个网格的长度值; ${r_b}$ 每个网格的宽度值; ${E_{Tx}}(k,d)$ 节点传输$k$bits 信息所需的发射能耗; ${E_{Rx}}(k)$ 节点传输$k$bits 信息所需的接收能耗; $d$ 传输距离; ${E_{elec}}$ 发射电路和接收电路的能量消耗; ${\varepsilon _{fs}}$ 自由空间传输模型系数; ${E_{0}}$ 节点的初始能量. 
下载: 导出CSV
-
[1] Gui J S, Liu A F. A new distributed topology control algorithm based on optimization of delay and energy in wireless networks. Journal of Parallel and Distributed Computing, 2012, 72(8):1032-1044 doi: 10.1016/j.jpdc.2012.04.007 [2] 洪榛, 俞立, 张贵军, 陈友荣.基于最小连通支配集的无线传感网拓扑构建研究.电子与信息学报, 2012, 34(8):2000-2006 http://www.cnki.com.cn/Article/CJFDTOTAL-DZYX201208035.htmHong Zhen, Yu Li, Zhang Gui-Jun, Chen You-Rong. Topology construction based on minimum connected dominating set for wireless sensor networks. Journal of Electronics & Information Technology, 2012, 34(8):2000-2006 http://www.cnki.com.cn/Article/CJFDTOTAL-DZYX201208035.htm [3] Zhang Y M, He S, Chen J. Data gathering optimization by dynamic sensing and routing in rechargeable sensor networks. In:Proceedings of the 10th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON). New Orleans, LA:IEEE, 2013. 273-281 [4] 康一梅, 李志军, 胡江, 董吉昌.一种低能耗层次型无线传感器网络拓扑控制算法.自动化学报, 2010, 36(4):543-549 doi: 10.3724/SP.J.1004.2010.00543Kang Yi-Mei, Li Zhi-Jun, Hu Jiang, Dong Ji-Chang. A low-power hierarchical wireless sensor network topology control algorithm. Acta Automatica Sinica, 2010, 36(4):543-549 doi: 10.3724/SP.J.1004.2010.00543 [5] 罗小元, 闫彦霖, 郝丽娟, 李绍宝, 关新平.基于最优刚性图的能量有效分布式拓扑控制算法.通信学报, 2013, 34(12):1-10 http://www.cnki.com.cn/Article/CJFDTOTAL-TXXB201312001.htmLuo Xiao-Yuan, Yan Yan-Lin, Hao Li-Juan, Li Shao-Bao, Guan Xin-Ping. Based on optimally rigid graph energy efficient distributed topology control algorithm. Journal on Communications, 2013, 34(12):1-10 http://www.cnki.com.cn/Article/CJFDTOTAL-TXXB201312001.htm [6] Yu C S, Lee B, Youn H Y. Energy efficient routing protocols for mobile ad hoc networks. Wireless Communications and Mobile Computing, 2003, 3(8):959-973 doi: 10.1002/(ISSN)1530-8677 [7] Li L, Halpern J Y, Bahl P, Wang Y M, Wattenhofer R. A cone-based distributed topology-control algorithm for wireless multi-hop networks. IEEE/ACM Transactions on Networking, 2005, 13(1):147-159 doi: 10.1109/TNET.2004.842229 [8] Chen B J, Jamieson K, Balakrishnan H, Morris R. Span:an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks. Wireless Networks, 2002, 8(5):481-494 doi: 10.1023/A:1016542229220 [9] Berman P, Calinescu G, Shah C, Zelikovsky A A. Efficient energy management in sensor networks. Ad Hoc and Sensor Networks, Wireless Networks and Mobile Computing. New York:Nova Science Publishers, 2005. 71-90 [10] Li N, Hou J C, Sha L. Design and analysis of an MST-based topology control algorithm. IEEE Transactions on Wireless Communications, 2005, 4(3):1195-1206 doi: 10.1109/TWC.2005.846971 [11] Shang D, Zhang B, Yao Z, Li C. An energy efficient localized topology control algorithm for wireless multihop networks. Journal of Communications and Networks, 2014, 16(4):371-377 doi: 10.1109/JCN.2014.000066 [12] Wang Y, Li X Y. Localized construction of bounded degree and planar spanner for wireless ad hoc networks. Mobile Networks and Applications, 2006, 11(2):161-175 doi: 10.1007/s11036-006-4469-5 [13] Xu Y, Heidemann J, Estrin D. Geography-informed energy conservation for ad hoc routing. In:Proceedings of the 7th Annual International Conference on Mobile Computing and Networking. Rome, Italy:ACM, 2001. 70-84 [14] 苏金树, 郭文忠, 余朝龙, 陈国龙.负载均衡感知的无线传感器网络容错分簇算法.计算机学报, 2014, 37(2):445-456 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201402017.htmSu Jin-Shu, Guo Wen-Zhong, Yu Zhao-Long, Chen Guo-Long. Fault-tolerance clustering algorithm with load-balance aware in wireless sensor network. Chinese Journal of Computers, 2014, 37(2):445-456 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201402017.htm [15] Li N, Hou J C. Localized fault-tolerant topology control in wireless ad hoc networks. IEEE Transactions on Parallel and Distributed Systems, 2006, 17(4):307-320 doi: 10.1109/TPDS.2006.51 [16] Luo X Y, Yan Y L, Li S B, Guan X P. Topology control based on optimally rigid graph in wireless sensor networks. Computer Networks, 2013, 57(4):1037-1047 doi: 10.1016/j.comnet.2012.12.002 [17] Cárbunar B, Grama A, Vitek J, Cárbunar O. Redundancy and coverage detection in sensor networks. ACM Transactions on Sensor Networks (TOSN), 2006, 2(1):94-128. doi: 10.1145/1138127 [18] 罗小元, 邵士凯, 关新平, 赵渊洁.多智能体最优持久编队动态生成与控制.自动化学报, 2013, 39(9):1431-1438 http://www.aas.net.cn/CN/abstract/abstract18176.shtmlLuo Xiao-Yuan, Shao Shi-Kai, Guan Xin-Ping, Zhao Yuan-Jie. Dynamic generation and control of optimally persistent formation for multi-agent systems. Acta Automatica Sinica, 2013, 39(9):1431-1438 http://www.aas.net.cn/CN/abstract/abstract18176.shtml [19] 罗小元, 杨帆, 李绍宝, 关新平.多智能体系统的最优持久编队生成策略.自动化学报, 2014, 40(7):1311-1319 http://www.aas.net.cn/CN/abstract/abstract18402.shtmlLuo Xiao-Yuan, Yang Fan, Li Shao-Bao, Guan Xin-Ping. Generation of optimally persistent formation for multi-agent systems. Acta Automatica Sinica, 2014, 40(7):1311-1319 http://www.aas.net.cn/CN/abstract/abstract18402.shtml [20] 董箭, 彭认灿, 郑义东.利用局部动态最优Delaunay三角网改进逐点内插算法.武汉大学学报:信息科学版, 2013, 38(5):613-617 http://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201305024.htmDong Jian, Peng Ren-Can, Zheng Yi-Dong. An improved algorithm of point-by-point interpolation by using local dynamic optimal Delaunay triangulation network. Geomatics and Information Science of Wuhan University, 2013, 38(5):613-617 http://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201305024.htm [21] 王朝瑞.图论(第3版).北京:北京理工大学出版社, 2005. 15Wang Chao-Rui. Graph Theory (3rd Edition). Beijing:Beijing Institute of Technology Press, 2005. 15 [22] Tian D, Georganas N D. A coverage-preserving node scheduling scheme for large wireless sensor networks. In:Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications. Atlanta, Georgia, USA:ACM, 2002. 32-41 [23] Xing G L, Wang X R, Zhang Y F, Lu C Y, Pless R, Gill C. Integrated coverage and connectivity configuration for energy conservation in sensor networks. ACM Transactions on Sensor Networks, 2005, 1(1):36-72 doi: 10.1145/1077391 -
计量
- 文章访问数: 2370
- HTML全文浏览量: 308
- PDF下载量: 635
- 被引次数: 0
