一种基于马尔可夫博弈的能量均衡路由算法

《一种基于马尔可夫博弈的能量均衡路由算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第３６卷第７期计算机学报Ｖｏｌ．３６Ｎｏ．７２０１３年７月ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＪｕｌｙ２０１３一种基于马尔可夫博弈的能量均衡路由算法董荣胜１）马争先２）郭云川１），３）古天龙１）１）（广西可信软件重点实验室（桂林电子科技大学）广西桂林５４１００４）２）（格力电器股份有限公司广东珠海５１９０７０）３）（中国科学院信息工程研究所北京１０００９３）摘要针对无线传感器网络中耗能不均问题，引入马尔可夫博弈理论，构建了无线传感器网络的马尔可夫博弈模型．在能量均衡路由分析的基础上，给出了一种基于马尔可夫博弈的能量均衡路由算法，该算法从无线传感器网络整体耗能出发，兼顾

2、节点之间的合作．定义了能量和信誉值的二元收益函数，给出了节点转发的状态转移概率，根据收益函数进行能量调节，求解出能量和收益之间的均衡系数———纳什均衡，实现了节点能量的均衡消耗，延长了网络的生命周期．使用ＰＲＩＳＭ概率仿真工具进行仿真，验证了该博弈模型存在纳什均衡点，同时表明该模型能促进节点之间合作，最大化无线传感器网络的生命周期．关键词马尔可夫博弈；纳什均衡；能耗；网络生命周期；路由算法；绿色网络中图法分类号ＴＰ３９３犇犗犐号１０．３７２４／ＳＰ．Ｊ．１０１６．２０１３．０１５００犃犕犪狉犽狅狏犌犪犿犲犜犺犲狅狉狔犅犪狊犲犱犈狀犲狉犵狔犅犪犾犪狀犮犲犚狅狌狋犻狀犵犃犾犵狅狉犻狋

3、犺犿ＤＯＮＧＲｏｎｇＳｈｅｎｇ１）ＭＡＺｈｅｎｇＸｉａｎ２）ＧＵＯＹｕｎＣｈｕａｎ１），３）ＧＵＴｉａｎＬｏｎｇ１）１）（犌狌犪狀犵狓犻犓犲狔犔犪犫狅狉犪狋狅狉狔狅犳犜狉狌狊狋犲犱犛狅犳狋狑犪狉犲（犌狌犻犾犻狀犝狀犻狏犲狉狊犻狋狔狅犳犈犾犲犮狋狉狅狀犻犮犜犲犮犺狀狅犾狅犵狔），犌狌犻犾犻狀，犌狌犪狀犵狓犻５４１００４）２）（犌狉犲犲犈犾犲犮狋狉犻犮犃狆狆犾犻犪狀犮犲狊，犐狀犮．犣犺狌犺犪犻，犌狌犪狀犵犱狅狀犵５１９０７０）３）（犐狀狊狋犻狋狌狋犲狅犳犐狀犳狅狉犿犪狋犻狅狀犈狀犵犻狀犲犲狉犻狀犵，犆犺犻狀犲狊犲犃犮犪犱犲犿狔狅犳犛犮犻犲狀犮犲狊，犅犲犻犼犻狀犵１０００９３）犃

4、犫狊狋狉犪犮狋Ｅｎｅｒｇｙｂａｌａｎｃｅｒｏｕｔｉｎｇｉｓｏｆｇｒｅａｔｉｍｐｏｒｔａｎｃｅｉｎｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ（ＷＳＮｓ）．Ａｓａｒｅｓｐｏｎｓｅｔｏｔｈｉｓｉｓｓｕｅ，ｉｎｔｈｅｐａｐｅｒ，ａＭａｒｋｏｖＧａｍｅＭｏｄｅｌｆｏｒＷＳＮｓｉｓｐｒｏｐｏｓｅｄ．Ｂａｓｅｄｏｎｔｈｅｂａｓｉｃｃｈａｒａｃｔｅｒｉｓｔｉｃｏｆｅｎｅｒｇｙｂａｌａｎｃｅｒｏｕｔｉｎｇａｎｄｎｏｄｅｃｏｏｐｅｒａｔｉｏｎ，ａＭａｒｋｏｖＧａｍｅＴｈｅｏｒｙＢａｓｅｄＥｎｅｒｇｙＢａｌａｎｃｅＲｏｕｔｉｎｇ（ＭＧＴＥＢＲ）Ａｌｇｏｒｉｔｈｍｉｓｄｅｓｉｇｎｅｄｆｏｒｄｅｃｒｅａ

5、ｓｉｎｇｔｈｅｗｈｏｌｅｅｎｅｒｇｙｃｏｎｓｕｍｐｔｉｏｎａｎｄｍａｘｉｍｉｚｉｎｇｔｈｅｎｅｔｗｏｒｋｌｉｆｅｔｉｍｅ．Ｆｉｒｓｔ，ａｂｉｎａｒｙｐａｙｏｆｆｆｕｎｃｔｉｏｎｏｆｅｎｅｒｇｙａｎｄｒｅｐｕｔａｔｉｏｎｉｓｄｅｆｉｎｅｄ，ａｎｄｔｈｅｔｒａｎｓｉｔｉｏｎｐｒｏｂａｂｉｌｉｔｙｏｆｎｏｄｅｆｏｒｗａｒｄｉｎｇｓｔａｔｅｉｓｇｉｖｅｎ．Ｂａｓｅｄｏｎｔｈｅｐａｙｏｆｆｆｕｎｃｔｉｏｎ，ｔｈｅｅｑｕｉｌｉｂｒｉｕｍｃｏｅｆｆｉｃｉｅｎｔｂｅｔｗｅｅｎｅｎｅｒｇｙａｎｄｒｅｐｕｔａｔｉｏｎｖａｌｕｅｓ—Ｎａｓｈｅｑｕｉｌｉｂｒｉｕｍｉｓｃｏｍｐｕｔｅｄ．Ｐｒｏｂａｂｉｌｉｓ

6、ｔｉｃｍｏｄｅｌｃｈｅｃｋｅｒＰＲＩＳＭｉｓａｄｏｐｔｅｄｆｏｒｓｉｍｕｌａｔｉｏｎ．ＴｈｅｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｒｅｅｘｉｓｔｓＮａｓｈｅｑｕｉｌｉｂｒｉｕｍｉｎｏｕｒａｌｇｏｒｉｔｈｍ，ａｎｄｔｈｅｃｏｏｐｅｒａｔｉｏｎｂｅｔｗｅｅｎｔｈｅｎｏｄｅｓｃａｎｂｅｐｒｏｍｏｔｅｄ，ｔｈｅｍａｘｉｍｕｍｌｉｆｅｃａｎｂｅｏｂｔａｉｎｅｄ．犓犲狔狑狅狉犱狊Ｍａｒｋｏｖｇａｍｅ；Ｎａｓｈｅｑｕｉｌｉｂｒｉｕｍ；ｅｎｅｒｇｙｃｏｎｓｕｍｐｔｉｏｎ；ｎｅｔｗｏｒｋｓｌｉｆｅｔｉｍｅ；ｒｏｕｔｉｎｇａｌｇｏｒｉｔｈｍ；ｇｒｅｅｎｎｅｔｗｏｒｋｉｎｇ器节点不仅能量有限，其野外工作的

7、环境也导致了１引言节点的更换和充电困难，这些因素使得在设计无线传感网络时须考虑尽量减少节点能量的消耗．无线传感器网络由大量微型传感器组成，传感无线传感器网络不同于传统的无线网络，其所收稿日期：２０１１１２２９；最终修改稿收到日期：２０１３０３１３．本课题得到国家自然科学基金（６１１００１８６，６１２６２０７４）资助．董荣胜，男，１９６５年生，教授，中国计算机学会（ＣＣＦ）高级会员，主要研究领域为网络安全协议、传感器网络、形式化技术、计算思维与计算机方法论．Ｅ