搜索

x

留言板

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

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

一种基于势博弈的无线传感器网络拓扑控制算法

李小龙 冯东磊 彭鹏程

引用本文:
Citation:

一种基于势博弈的无线传感器网络拓扑控制算法

李小龙, 冯东磊, 彭鹏程

A potential game based topology control algorithm for wireless sensor networks

Li Xiao-Long, Feng Dong-Lei, Peng Peng-Cheng
PDF
导出引用
  • 在实际的应用中, 无线传感器网络常常由大量电池资源有限的传感器节点组成. 如何降低网络功耗, 最大化网络生存时间, 是传感器网络拓扑控制技术的重要研究目标. 随着传感节点的运行, 节点的能量分布可能越来越不均衡, 需要在考虑该因素的情况下, 动态地调整节点的网络负载以均衡节点的能耗, 达到延长网络生存时间的目的. 该文引入博弈理论和势博弈的概念, 综合考虑节点的剩余能量和节点发射功率等因素, 设计了一种基于势博弈的拓扑控制模型, 并证明了该模型纳什均衡的存在性. 通过构造兼顾节点连通性和能耗均衡性的收益函数, 以确保降低节点功耗的同时维持网络的连通性. 通过提高邻居节点的平均剩余能量值以实现将剩余能量多的节点选择作为自身的邻居节点, 提高节点能耗的均衡性. 在此基础上, 提出了一种分布式的能耗均衡拓扑控制算法. 理论分析证明了该算法能保持网络的连通性. 与现有基于博弈理论的DIA算法和MLPT算法相比, 本算法形成的拓扑负载较重、剩余能量较小的瓶颈节点数量较少, 节点剩余能量的方差较小, 网络生存时间更长.
    In real-world applications, wireless sensor networks often consist of a large number of sensor nodes with constraint battery resources. How to reduce the power consumption of sensor nodes and maximize the network life, becomes the most important goal of topology control schemes in wireless sensor networks. During the operation of networks, sensor nodes may spend different levels of energy, and result in the uneven distribution of residual energy of sensor nodes. In order to extend the network life, it is essential to adjust the network burden of sensor nodes dynamically, so as to achieve energy balance among nodes under the consideration of different energy levels at nodes. In this paper, we introduce the game theory and the concept of game potential. By synthetically considering the factors of the residual energy and transmission power of nodes, a potential game based mathematical model of topology control is constructed. We prove the existence of Nash equilibrium. Through designing a payoff function, which takes into account both network connectivity and energy balance of nodes, the connectivity of sensor networks can be maintained while the power of sensor nodes is reduced. By increasing the average value of residual energy of neighbors, it enables to select nodes with more energy that reserves in neighborhood as neighbors, to improve the energy balance among nodes. Based on that, a distributed energy-balanced topology control algorithm (DEBA) is proposed. Theoretical analysis proves that the algorithm can maintain network connectivity. Compared with other existing game theory based algorithms DIA and MLPT, the topologies formed by the proposed algorithm have fewer bottleneck nodes which feature heavy traffic load and low residual energy, and smaller variance of node residual energy, thus achieving a longer life.
      通信作者: 冯东磊, xlli@guet.edu.cn
    • 基金项目: 国家自然科学基金(批准号: 61462021, 61262074)和广西可信软件重点实验室开放项目(批准号: PF130549)资助的课题.
      Corresponding author: Feng Dong-Lei, xlli@guet.edu.cn
    • Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 61462021, 61262074), and the Opening Project of Guangxi Key Laboratory of Trusted Software (Grant No. PF130549).
    [1]

    Zhang X, Lu S L, Chen G H, Chen D X, Xie L 2007 Journal of Software 18 943 (in Chinese) [张学, 陆桑璐, 陈贵海, 陈道蓄, 谢立 2007 软件学报 18 943]

    [2]

    Huang Y, Martnez J F, Daz V H, Sendra J 2014 Sensors 14 4762

    [3]

    Wattenhofer R, Li L, Bahl P, Wang Y M 2001 Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies Washington, USA, April 27-28, 2001 p1388

    [4]

    Zhang G, Zhang Z, Fan J 2010 IEEE Transactions on Parallel and Distributed Systems 21 1387

    [5]

    Tian Y, Sheng M, Li J, ZhangY, Yao J, Tang D 2008 Global Telecommunications Conference New Orleans, USA, December 1-4, 2008 p1

    [6]

    Chu X, Sethu H 2014 Wireless and Mobile Computing, Networking and Communications Larnaca, Cyprus, October 8-10, 2014 p556

    [7]

    Li N, Hou J C, Sha L 2005 Wireless Communications 4 1195

    [8]

    Shang D, Zhang B, Yao Z, Li C 2014 Communications and Networks 16 371

    [9]

    Wang X, Sheng M, Liu M, Zhai D, Zhang Y 2013 Wireless Communications and Networking Conference (WCNC) Shanghai, China, April 7-10, 2013 p1009

    [10]

    Li X H, Ge J Q, Zhang D F 2013 Joural of Communication 34 35 (in Chinese) [李晓鸿, 葛静巧, 张大方 2013 通信学报 34 35]

    [11]

    Qiao J, Liu S, Duan W 2015 International Journal of Distributed Sensor Networks 2015

    [12]

    Fang W, Song X H 2014 Acta Phys. Sin. 63 220701 (in Chinese) [方伟, 宋鑫宏 2014 物理学报 63 220701]

    [13]

    Liu Z Z, Wang F B 2014 Acta Phys. Sin. 63 190504 (in Chinese) [刘洲洲, 王福豹 2014 物理学报 63 190504]

    [14]

    Bagci H, Korpeoglu I, Yazici A 2015 Parallel and Distributed Systems 26 914

    [15]

    Eidenbenz S, Kumar V S, Zust S 2006 Mobile Networks and Applications 11 143

    [16]

    Abbasi M, Fisal N 2015 Sensors Journal 15 2344

    [17]

    Komali R S, MacKenzie A B 2006 Proceedings of IEEE CCNC Las Vegas, USA, January 8-10 2006 563

    [18]

    Komali R S, MacKenzie A B, Gilles R P 2008 Mobile Computing 7 1057

    [19]

    Komali R S 2008 Ph. D. Dissertation (Virginia: Virginia Polytechnic Institute and State University)

    [20]

    Sajjad Z, Nasser Y, Amir N 2012 Computer Networks 56 902

    [21]

    Hao X C, Zhang Y X, Jia N, Liu B 2013 Wireless personal communications 69 1289

    [22]

    Fudenberg D, Tirole J 1991 Game Theory (New York: MIT Press)

    [23]

    Monderer D, Shapley L S 1996 Games and Economic Behavior 14 124

    [24]

    Akkaya K, Senel F, Thimmapuram A, Uludag S 2010 IEEE Transactions on Computers 59 258

    [25]

    MacKenzie A B, DaSilva L A 2006 Synthesis Lectures on Communications 1 1

  • [1]

    Zhang X, Lu S L, Chen G H, Chen D X, Xie L 2007 Journal of Software 18 943 (in Chinese) [张学, 陆桑璐, 陈贵海, 陈道蓄, 谢立 2007 软件学报 18 943]

    [2]

    Huang Y, Martnez J F, Daz V H, Sendra J 2014 Sensors 14 4762

    [3]

    Wattenhofer R, Li L, Bahl P, Wang Y M 2001 Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies Washington, USA, April 27-28, 2001 p1388

    [4]

    Zhang G, Zhang Z, Fan J 2010 IEEE Transactions on Parallel and Distributed Systems 21 1387

    [5]

    Tian Y, Sheng M, Li J, ZhangY, Yao J, Tang D 2008 Global Telecommunications Conference New Orleans, USA, December 1-4, 2008 p1

    [6]

    Chu X, Sethu H 2014 Wireless and Mobile Computing, Networking and Communications Larnaca, Cyprus, October 8-10, 2014 p556

    [7]

    Li N, Hou J C, Sha L 2005 Wireless Communications 4 1195

    [8]

    Shang D, Zhang B, Yao Z, Li C 2014 Communications and Networks 16 371

    [9]

    Wang X, Sheng M, Liu M, Zhai D, Zhang Y 2013 Wireless Communications and Networking Conference (WCNC) Shanghai, China, April 7-10, 2013 p1009

    [10]

    Li X H, Ge J Q, Zhang D F 2013 Joural of Communication 34 35 (in Chinese) [李晓鸿, 葛静巧, 张大方 2013 通信学报 34 35]

    [11]

    Qiao J, Liu S, Duan W 2015 International Journal of Distributed Sensor Networks 2015

    [12]

    Fang W, Song X H 2014 Acta Phys. Sin. 63 220701 (in Chinese) [方伟, 宋鑫宏 2014 物理学报 63 220701]

    [13]

    Liu Z Z, Wang F B 2014 Acta Phys. Sin. 63 190504 (in Chinese) [刘洲洲, 王福豹 2014 物理学报 63 190504]

    [14]

    Bagci H, Korpeoglu I, Yazici A 2015 Parallel and Distributed Systems 26 914

    [15]

    Eidenbenz S, Kumar V S, Zust S 2006 Mobile Networks and Applications 11 143

    [16]

    Abbasi M, Fisal N 2015 Sensors Journal 15 2344

    [17]

    Komali R S, MacKenzie A B 2006 Proceedings of IEEE CCNC Las Vegas, USA, January 8-10 2006 563

    [18]

    Komali R S, MacKenzie A B, Gilles R P 2008 Mobile Computing 7 1057

    [19]

    Komali R S 2008 Ph. D. Dissertation (Virginia: Virginia Polytechnic Institute and State University)

    [20]

    Sajjad Z, Nasser Y, Amir N 2012 Computer Networks 56 902

    [21]

    Hao X C, Zhang Y X, Jia N, Liu B 2013 Wireless personal communications 69 1289

    [22]

    Fudenberg D, Tirole J 1991 Game Theory (New York: MIT Press)

    [23]

    Monderer D, Shapley L S 1996 Games and Economic Behavior 14 124

    [24]

    Akkaya K, Senel F, Thimmapuram A, Uludag S 2010 IEEE Transactions on Computers 59 258

    [25]

    MacKenzie A B, DaSilva L A 2006 Synthesis Lectures on Communications 1 1

  • [1] 蒋锐, 杨震. 基于质心迭代估计的无线传感器网络节点定位算法. 物理学报, 2016, 65(3): 030101. doi: 10.7498/aps.65.030101
    [2] 罗小元, 李昊, 马巨海. 基于最小刚性图代数特性的无线网络拓扑优化算法. 物理学报, 2016, 65(24): 240201. doi: 10.7498/aps.65.240201
    [3] 郝晓辰, 刘伟静, 辛敏洁, 姚宁, 汝小月. 一种无线传感器网络健壮性可调的能量均衡拓扑控制算法. 物理学报, 2015, 64(8): 080101. doi: 10.7498/aps.64.080101
    [4] 郝晓辰, 姚宁, 汝小月, 刘伟静, 辛敏洁. 基于生命期模型的无线传感器网络信道分配博弈算法. 物理学报, 2015, 64(14): 140101. doi: 10.7498/aps.64.140101
    [5] 彭海霞, 赵海, 李大舟, 林川. 基于动态最小生成树路由协议的数据聚融算法. 物理学报, 2014, 63(9): 090206. doi: 10.7498/aps.63.090206
    [6] 黄锦旺, 冯久超, 吕善翔. 混沌信号在无线传感器网络中的盲分离. 物理学报, 2014, 63(5): 050502. doi: 10.7498/aps.63.050502
    [7] 刘浩然, 尹文晓, 董明如, 刘彬. 一种强容侵能力的无线传感器网络无标度拓扑模型研究. 物理学报, 2014, 63(9): 090503. doi: 10.7498/aps.63.090503
    [8] 方伟, 宋鑫宏. 基于Voronoi图盲区的无线传感器网络覆盖控制部署策略. 物理学报, 2014, 63(22): 220701. doi: 10.7498/aps.63.220701
    [9] 宋佳, 罗清华, 彭喜元. 基于节点健康度的无线传感器网络冗余通路控制方法. 物理学报, 2014, 63(12): 128401. doi: 10.7498/aps.63.128401
    [10] 刘彬, 董明如, 刘浩然, 尹荣荣, 韩丽. 基于综合故障的无线传感器网络无标度容错拓扑模型研究. 物理学报, 2014, 63(17): 170506. doi: 10.7498/aps.63.170506
    [11] 刘洲洲, 王福豹. 一种能耗均衡的无线传感器网络加权无标度拓扑研究. 物理学报, 2014, 63(19): 190504. doi: 10.7498/aps.63.190504
    [12] 尹荣荣, 刘彬, 刘浩然, 李雅倩. 无线传感器网络中无标度拓扑的动态容错性分析. 物理学报, 2014, 63(11): 110205. doi: 10.7498/aps.63.110205
    [13] 韩丽, 刘彬, 李雅倩, 赵磊静. 能量异构的无线传感器网络加权无标度拓扑研究. 物理学报, 2014, 63(15): 150504. doi: 10.7498/aps.63.150504
    [14] 刘浩然, 尹文晓, 韩涛, 董明如. 一种优化无线传感器网络生命周期的容错拓扑研究. 物理学报, 2014, 63(4): 040509. doi: 10.7498/aps.63.040509
    [15] 刘向丽, 李赞, 胡易俗. 无线传感网中基于质心的高效坐标压缩算法. 物理学报, 2013, 62(7): 070201. doi: 10.7498/aps.62.070201
    [16] 祁浩, 王福豹, 邓宏. 基于无线传感器网络的地震信号特征提取方法研究. 物理学报, 2013, 62(10): 104301. doi: 10.7498/aps.62.104301
    [17] 王翥, 王祁, 魏德宝, 王玲. 无线传感器网络中继节点布居算法的研究. 物理学报, 2012, 61(12): 120505. doi: 10.7498/aps.61.120505
    [18] 佟晓筠, 左科, 王翥. 基于无线传感器网络的混合混沌新分组加密算法. 物理学报, 2012, 61(3): 030502. doi: 10.7498/aps.61.030502
    [19] 王亚奇, 杨晓元. 一种无线传感器网络簇间拓扑演化模型及其免疫研究. 物理学报, 2012, 61(9): 090202. doi: 10.7498/aps.61.090202
    [20] 周杰, 刘元安, 吴帆, 张洪光, 俎云霄. 基于混沌并行遗传算法的多目标无线传感器网络跨层资源分配. 物理学报, 2011, 60(9): 090504. doi: 10.7498/aps.60.090504
计量
  • 文章访问数:  4501
  • PDF下载量:  315
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-07-31
  • 修回日期:  2015-10-08
  • 刊出日期:  2016-01-20

一种基于势博弈的无线传感器网络拓扑控制算法

  • 1. 桂林电子科技大学, 计算机科学与工程学院, 桂林 541004;
  • 2. 桂林电子科技大学, 广西可信软件重点实验室, 桂林 541004
  • 通信作者: 冯东磊, xlli@guet.edu.cn
    基金项目: 国家自然科学基金(批准号: 61462021, 61262074)和广西可信软件重点实验室开放项目(批准号: PF130549)资助的课题.

摘要: 在实际的应用中, 无线传感器网络常常由大量电池资源有限的传感器节点组成. 如何降低网络功耗, 最大化网络生存时间, 是传感器网络拓扑控制技术的重要研究目标. 随着传感节点的运行, 节点的能量分布可能越来越不均衡, 需要在考虑该因素的情况下, 动态地调整节点的网络负载以均衡节点的能耗, 达到延长网络生存时间的目的. 该文引入博弈理论和势博弈的概念, 综合考虑节点的剩余能量和节点发射功率等因素, 设计了一种基于势博弈的拓扑控制模型, 并证明了该模型纳什均衡的存在性. 通过构造兼顾节点连通性和能耗均衡性的收益函数, 以确保降低节点功耗的同时维持网络的连通性. 通过提高邻居节点的平均剩余能量值以实现将剩余能量多的节点选择作为自身的邻居节点, 提高节点能耗的均衡性. 在此基础上, 提出了一种分布式的能耗均衡拓扑控制算法. 理论分析证明了该算法能保持网络的连通性. 与现有基于博弈理论的DIA算法和MLPT算法相比, 本算法形成的拓扑负载较重、剩余能量较小的瓶颈节点数量较少, 节点剩余能量的方差较小, 网络生存时间更长.

English Abstract

参考文献 (25)

目录

    /

    返回文章
    返回