基于最优刚性图的能量有效分布式拓扑控制算法

doi:10.3969/j.issn.1000-436X.2013.12.001

通信学报 ›› 2013, Vol. 34 ›› Issue (12): 1-10.doi: 10.3969/j.issn.1000-436X.2013.12.001

• 学术论文 • 下一篇

基于最优刚性图的能量有效分布式拓扑控制算法

罗小元¹,闫彦霖¹,郝丽娟¹,李绍宝²,关新平³

¹ 燕山大学电气学院，河北秦皇岛066004
² 香港城市大学制造工程及工程管理部，香港
³ 上海交通大学电子信息与电气工程学院，上海201100

出版日期:2013-12-25 发布日期:2017-07-05
基金资助:
国家重点基础研究发展计划(“973”计划)基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目;河北省自然科学基金资助项目

Based on optimally rigid graph energy efficient distributed topology control algorithm

Xiao-yuan LUO¹,Yan-lin YAN¹,Li-juan HAO¹,Shao-bao LI²,Xin-ping GUAN³

¹ Institute of Electrical Engineering, Yanshan University, Qinhuangdao 066004, China
² Department of Manufacturing Engineering and Engineering Management, City University of Hong Kong, Hong Kong, China
³ School of Electronic and Electric Engineering, University of Shanghai Jiaotong, Shanghai 201100, China

Online:2013-12-25 Published:2017-07-05
Supported by:
The National Basic Research Program of China (973 Program);The National Natural Science Foundation of China;The National Natural Science Foundation of China;The Natural Science Foundation of Hebei Province

摘要/Abstract

摘要：

针对现有无线传感器网络拓扑控制算法无法平衡各节点能量消耗的问题，基于最优刚性图提出了一种具有平衡负载特性的能量有效分布式拓扑控制算法。算法引入综合反映能量消耗及剩余能量两方面因素的链路权值函数，能够根据当前节点剩余能量实时地动态优化拓扑结构，从而有效地平衡网络节点的能量消耗。从理论上证明了优化后的拓扑是2-连通的而且具有稀疏性；同时优化后拓扑中各节点的平均度趋于4。仿真结果表明，与其他算法相比，该算法能够有效地平衡各节点的能量消耗，进而延长网络生命期。

关键词: 无线传感器网络, 拓扑控制, 最优刚性图, 能量均衡

Abstract:

To solve the problem that most of existing algorithms cannot balance energy consumption,the energy efficient distributed topology control algorithm (OREE) based on optimally rigid graph was presented.Through the link weight function reflecting both the energy consumption and residual energy of two end nodes,OREE builds a dynamic network topology that changes with the variation of node energy,and thus balances energy consumption of nodes.The topology derived under OREE is 2-connected and sparse was proved,and the average degree of nodes in the topology converges to four approximately.Furthermore,simulation results show that OREE can balance energy consumption of nodes effi-ciently compared with other algorithms,thereby extend the lifetime of networks.

Key words: wireless sensor network, topology control, optimally rigid graph, energy balancing

罗小元,闫彦霖,郝丽娟,李绍宝,关新平. 基于最优刚性图的能量有效分布式拓扑控制算法[J]. 通信学报, 2013, 34(12): 1-10.

Xiao-yuan LUO,Yan-lin YAN,Li-juan HAO,Shao-bao LI,Xin-ping GUAN. Based on optimally rigid graph energy efficient distributed topology control algorithm[J]. Journal on Communications, 2013, 34(12): 1-10.

图/表 12

图1

图2

表1

图3

表2

图4

表3

图5

图6

图7

图8

图9

参考文献 19

[1]	KADIVAR M , SHIRI M E , DEHGHAN M . Distributed topology control algorithm based on one-and two-hop neighbors' information for ad hoc networks[J]. Computer Communication, 2009,32(2):368-375.
[2]	SHEN Y , CAI Y Z , XU X M . Shortest-path-based topology control algorithm in wireless multihop networks[J]. ACM SIGCOMM Com-puter Communication Review, 2007,37(5):29-38.
[3]	BURKHART M , RICKENBACH P V , WATTENHOFER R , et al. Does topology control reduce interference[A]. Proceedings of ACM MobiHoc04[C]. Lausanne, 2004.9-19.
[4]	LOYD E L , LIU R , MARATHE M V , et al. Algorithmic aspects of topology control problems for ad hoc networks[J]. Mobi Networks and Applications, 2005,10(1-2):19-34.
[5]	TOUSSAINT G T . The relative neighborhood graph of a finite planar set[J]. Pattern Recognition, 1980,12(4):261-268.
[6]	BLOUGH D , LEONCINI M , RESTA G , et al. The k-neighbors proto-col for symmetric topology control in ad hoc networks[A]. Proceed-ings of the 4th ACM International Symposium on Mobile Ad Hoc Networking ＆ Computing[C]. New York,USA, 2003.141-152.
[7]	WATTENHOFER R , ZOLLINGER A . XTC:a practical topology control algorithm for ad-hoc networks[A]. Proceedings of 18th Inter-national on Parallel and Distributed Processing Symposium[C]. Santa Fe,NM,USA, 2004.1-8.
[8]	SANTI P . Topology control in wireless ad hoc and sensor networks[J]. ACM Computing Surveys, 2005,37(5):164-194.
[9]	刘林峰，金杉 . 无线传感器网络的拓扑控制算法综述[J]. 计算机科学， 2008,35(3):6-12. LIU L F , JIN S . Survey on topology control algorithm in wireless sen-sor networks[J]. Computer Science, 2008,35(3):6-12.
[10]	ZHANG G Q , ZHANG Z L , FAN J X . A locally-adjustable planar structure for adaptive topology control in wireless ad hoc networks[J]. IEEE Transactions Parallel and Distributed Systems, 2010,21(10):1387-1397.
[11]	LUO X Y , LIU D , ZHANG F , et al. Flocking in target pursuit for multi-agent systems with partial informed agents[J]. IET Control Theory Application, 2012,6(4):560-569.
[12]	HENDRICKX J M , FIDAN B , YU C , et al. Formation reorganization by primitive operations on directed graphs[J]. IEEE Transactions on Automatic Control, 2008,4(53):968-979.
[13]	SMITH B , EGERSTEDT M , HOWARD A . Automatic generation o persistent formations for multi-agent networks under range con-straints[J]. Mobile Networks and Application, 2009,14(3):322-335.
[14]	TIAN Y , SHENG M , ZHANG J D , et al. Energy-aware self-adjusted topology control algorithm for heterogeneous wireless hoc net-works[A]. Global Telecommunications Conference[C]. Hawaii,USA, 2009.1-6.
[15]	LUO X Y , LI S B , GUAN X P . Automatic generation of min-weighted persistent formations[J]. Chinese Physics B, 2009,18(8):3104-3114.
[16]	REN R , ZHANG Y Y , LUO X Y . Automatic generation of opt mally rigid formations using decentralized methods[J]. International Journal of Automation and Computing, 2010,7(4):557-564.
[17]	TAY T S , WHITELEY W . Generating isostatic frameworks[J]. Struc-tual Topology, 1985,11:21-69.
[18]	王朝瑞 . 图论[M]. 北京：北京理工大学出版社， 2005.15-17. WANG C R . Graph Theory[M]. Beijing: Beijing Institute of Technol-ogy Press, 2005.15-17.
[19]	OK C S , LEE S , MITRA P . Distributed energy balanced routing for wireless sensor networks[J]. Computers ＆ Industrial En ineering, 2009,57(1):125-135.

链路	权值
(1,2)	3 × 10^?8
(1,3)	3 × 10^?8
(1,4)	6.5 × 10^?8
(2,3)	3.5 ×10^?8
(2,4)	5 × 10^?8
(3,4)	5 × 10^?8

区域	初始能量/J	通信半径/m	节点数目
20;10	1	8	21

基于最优刚性图的能量有效分布式拓扑控制算法

Based on optimally rigid graph energy efficient distributed topology control algorithm

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 19

相关文章 15

Metrics

推荐阅读 0

[1]	赵越, 李赞, 李冰, 郝本建. TDoA定位盲区分析与节点部署策略研究[J]. 通信学报, 2023, 44(1): 1-13.
[2]	孙雁飞, 尹嘉峥, 亓晋, 胡筱旋, 陈梦婷, 董振江. 基于动态图嵌入的车联网拓扑控制[J]. 通信学报, 2022, 43(6): 133-142.
[3]	李翠然, 王雪洁, 谢健骊, 吕安琪. 基于改进PSO的铁路监测线性无线传感器网络路由算法[J]. 通信学报, 2022, 43(5): 155-165.
[4]	杜秀娟, 王丽娟, 刘静萍, 金龙. 基于归零神经动力学的水下无线传感器网络节点测距定位方法[J]. 通信学报, 2022, 43(10): 177-185.
[5]	孙爱晶, 李世昌, 张艺才. 基于PSO优化模糊C均值的WSN分簇路由算法[J]. 通信学报, 2021, 42(3): 91-99.
[6]	王天荆,李秀琴,白光伟,沈航. 无线传感器网络中基于自适应网格的多目标定位算法[J]. 通信学报, 2019, 40(7): 197-207.
[7]	郝晓辰,姚宁,解力霞,王姣姣,王立元. 联合功率与信道的WSN生命期优化博弈算法[J]. 通信学报, 2019, 40(4): 62-70.
[8]	刘琳岚,高声荣,舒坚. 基于随机森林的链路质量预测[J]. 通信学报, 2019, 40(4): 202-211.
[9]	武小年,张楚芸,张润莲,孙亚平. WSN中基于改进粒子群优化算法的分簇路由协议[J]. 通信学报, 2019, 40(12): 114-123.
[10]	刘浩然,赵赫瑶,邓玉静,王星淇,尹荣荣. 基于非合作博弈的无线传感器网络覆盖控制算法[J]. 通信学报, 2019, 40(1): 71-78.
[11]	乐燕芬,汤卓,盛存宝,施伟斌. 基于多分布密度位置指纹的高效室内定位算法研究[J]. 通信学报, 2019, 40(1): 172-179.
[12]	舒坚,刘满兰,尚亚青,陈宇斌,刘琳岚. 基于高斯过程回归的链路质量预测模型[J]. 通信学报, 2018, 39(7): 148-156.
[13]	郝晓辰,王立元,刘金硕,解力霞,张文焕. WSN中基于双群体差分进化的资源分配优化算法[J]. 通信学报, 2018, 39(4): 68-75.
[14]	蒋婵,李陶深,梁俊斌. 移动低占空比无线传感器网络中低时延的数据持续性提高算法[J]. 通信学报, 2018, 39(3): 53-62.
[15]	陈志刚,殷滨安,吴嘉. 基于消息重要性的机会网络能量均衡路由算法[J]. 通信学报, 2018, 39(12): 91-101.

节点i的邻居信息
nid
E
E_cost
C_ij