2.624

2020影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

无线传感器网络中基于Voronoi覆盖及Delaunay三角剖分图的最小刚性拓扑控制算法

薛亮 陈晰 赵继军 黎作鹏 关新平

薛亮, 陈晰, 赵继军, 黎作鹏, 关新平. 无线传感器网络中基于Voronoi覆盖及Delaunay三角剖分图的最小刚性拓扑控制算法. 自动化学报, 2016, 42(10): 1570-1584. doi: 10.16383/j.aas.2016.c150702
引用本文: 薛亮, 陈晰, 赵继军, 黎作鹏, 关新平. 无线传感器网络中基于Voronoi覆盖及Delaunay三角剖分图的最小刚性拓扑控制算法. 自动化学报, 2016, 42(10): 1570-1584. doi: 10.16383/j.aas.2016.c150702
XUE Liang, CHEN Xi, ZHAO Ji-Jun, LI Zuo-Peng, GUAN Xin-Ping. A Minimal Rigid Topology Control Algorithm Based on Voronoi Coverage and Delaunay Triangulation in Wireless Sensor Networks. ACTA AUTOMATICA SINICA, 2016, 42(10): 1570-1584. doi: 10.16383/j.aas.2016.c150702
Citation: XUE Liang, CHEN Xi, ZHAO Ji-Jun, LI Zuo-Peng, GUAN Xin-Ping. A Minimal Rigid Topology Control Algorithm Based on Voronoi Coverage and Delaunay Triangulation in Wireless Sensor Networks. ACTA AUTOMATICA SINICA, 2016, 42(10): 1570-1584. doi: 10.16383/j.aas.2016.c150702

无线传感器网络中基于Voronoi覆盖及Delaunay三角剖分图的最小刚性拓扑控制算法

doi: 10.16383/j.aas.2016.c150702
基金项目: 

河北省自然科学基金 F2014402075

河北省教育厅科学研究计划 BJ2014019

河北省教育厅科学研究计划 ZD2015087

河北省自然科学基金 F2016402054

河北省教育厅科学研究计划 QN2015046

国家自然科学基金 61304131

国家自然科学基金 61402147

详细信息
    作者简介:

    薛亮 河北工程大学信息与电气工程学院副教授.主要研究方向为无线传感器网络, 认知无线网络技术.E-mail:lxue@ysu.edu.cn

    赵继军 河北工程大学信息与电气工程学院教授.主要研究方向为无线传感器网络, 宽带通信网.E-mail:zjijun@hebeu.edu.cn

    黎作鹏 河北工程大学信息与电气工程学院讲师.主要研究方向为无线传感器网络, 物联网技术, 纳米网络.E-mail:lizuopeng@hebeu.edu.cn

    关新平 上海交通大学电子信息与电气工程学院教授.主要研究方向为无线传感器网络, 认知无线电等通信网络的控制, 复杂网络动态系统的性能分析与控制, 非线性时滞系统的拓扑控制, 网络化控制系统设计.E-mail:xpguan@sjtu.edu.cn

    通讯作者:

    陈晰 河北工程大学硕士研究生.主要研究方向为无线传感器网络技术.本文通信作者.E-mail:cx3768255@hotmail.com

A Minimal Rigid Topology Control Algorithm Based on Voronoi Coverage and Delaunay Triangulation in Wireless Sensor Networks

Funds: 

Natural Science Foundation of Hebei Province F2014402075

Scientific Research Plan Projects of Hebei Education Department BJ2014019

Scientific Research Plan Projects of Hebei Education Department ZD2015087

Natural Science Foundation of Hebei Province F2016402054

Scientific Research Plan Projects of Hebei Education Department QN2015046

National Natural Science Foundation of China 61304131

National Natural Science Foundation of China 61402147

More Information
    Author Bio:

    Associate professor at the School of Information and Electrical Engineering, Hebei University of Engineering. His research interest covers wireless sensor networks and cognitive radio networks

    Professor at the School of Information and Electrical Engineering, Hebei University of Engineering. His research interest covers wireless sensor networks and broadband communication network

    Lecturer at the School of Information and electrical Engineering, Hebei University of Engineering. His research interest covers wireless sensor networks, internet of things, and nanonetworks

    Professor at the School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University. His research interest covers wireless sensor networks, cognitive radio communication network in the control, analysis and control of complex dynamic network system, topology control of nonlinear time-delay systems, and networked control system design

    Corresponding author: CHEN Xi Master student at Hebei University of Engineering. Her research interest covers wireless sensor networks. Corresponding author of this paper
  • 摘要: 为同时满足覆盖与节能应用需求,本文提出了无线传感器网络中一种最小刚性拓扑控制算法MRTc(Minimal rigid topology control algorithm based on Voronoi coverage and Delaunay triangulation).该算法基于Voronoi覆盖机制,准确控制节点工作状态,实现活动节点对目标区域的完全覆盖.在此基础上,MRTc利用Delaunay三角剖分图的特点,构建出适用于无线传感器网络的最小刚性拓扑结构.该结构有效约束了网络平均节点度,且同时具有容错性、覆盖性和稀疏性.此外,MRTc引入节点功率控制策略,在维持网络完全覆盖的基础上最小化节点能耗.仿真结果进一步验证了本文提出的MRTc算法的有效性.
  • 图  1  节点$i$的2-Voronoi图

    Fig.  1  The 2-Voronoi diagram of node $i$

    图  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.htm

    Hong 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.00543

    Kang 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.htm

    Luo 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.htm

    Su 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.shtml

    Luo 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.shtml

    Luo 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.htm

    Dong 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. 15

    Wang 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
  • 加载中
图(12) / 表(1)
计量
  • 文章访问数:  1933
  • HTML全文浏览量:  278
  • PDF下载量:  610
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-10-26
  • 录用日期:  2016-03-03
  • 刊出日期:  2016-10-01

目录

    /

    返回文章
    返回