基于博弈理论的无线传感器网络分布式节能路由算法

第 30 卷第 5 期 2008 年 5 月

电 子 与 信 息 学 报 Journal of Electronics & Information Technology

Vol.30No.5 May 2008

基于博弈理论的无线传感器网络分布式节能路由算法
杨 宁 田 辉 黄 平
北京





(北京邮电大学通信工程学院

100876)

摘 要:为了有效解决无线传感器网络路由节能问题,该文提出适合无线传感器网络的节能路由算法。在引入博弈 理论概念建立网络模型的基础上,通过对于以往传感器网络簇首选择方法的研究,设计了一种基于博弈论的,兼顾 节点剩余能量及簇首分布的节能路由 DEER(Distributed Energy-Economical Routing),大大节省了分布式决策网 络协议的能量损耗。仿真证明了该方法在无线传感器网络中,能够有效地平衡网络负载,节省节点能量,延长网络 寿命。 关键词:无线传感器网络;路由;博弈论;节能 中图分类号:TP393 文献标识码:A 文章编号:1009-5896(2008)05-1230-04

Distributed Energy-Economical Routing Algorithm Based on Game-Theory for WSN
Yang Ning Tian Hui Huang Ping Zhang Ping
(School of Telecommunications, Beijing University of Posts and Telecommunications, Beijing 100876, China) Abstract: In order to efficiently solve the energy problem of routing, the game-theory is borrowed and an energy efficient routing algorithm is proposed. Based on the research of game model and other routing schemes for wireless sensor networks, the Distributed Energy-Economical Routing (DEER) is designed to save the energy of the whole network through paying attention to both remained energy and the distribution of head nodes. The simulation results prove that this scheme can effectively balance the load and prolong the life of the wireless sensor networks. Key words: Wireless Sensor Networks (WSN); Routing; Game-theory; Energy-economical

1 引言
随着移动通信技术、嵌入式计算技术和感应技术的飞速 发展, 有着多种应用场景的无线传感器网络(Wireless Sensor Network,WSN) 越来越受到人们的关注。但是由于无线传 感器网络是自组织无源网络,无法在布设后对节点能量进行 补充,因此其性能很大程度上受限于节点初始能量。如何通 过合理的路由策略,在保证数据传输的前提下,延长网络寿 命是无线传感器网络亟待解决的问题。 无线路由策略大致分为平面路由算法与分层路由算法 两类。其中分层路由算法具有能耗小、选路机制简单、扩展 方便等有利因素,从而使数据能够得到更加高效快捷可靠地 传输,适合无线传感器网络应用。而在现有分层无线传感器 网络路由协议中,对于网络能量效率的改善方法各不相同。 文献[1]中利用一定簇首选择概率进行簇首选择控制,但是这 种簇首选择方法需要预先确定簇首选择概率并且假设节点 传输范围任意变化;文献[2]则引入了定位功能,使每一个节 点基于节点位置信息形成簇的结构,从而建立高效路由。然 而这些方法由于簇首分布不合理或者节点复杂度等原因,并 非解决无线传感器网络能量问题的理想方案。
2006-11-09 收到,2007-03-21 改回 中兴通讯有限公司资助课题

本文引入博弈理论思想,设计了一种分布式节能路由协 议。尽管针对基于博弈论的路由协议已经有了一定的研究, 然而大部分路由协议都如文献[3,4]中,针对平面型网络而 设计;针对无线传感器网络分层型路由的研究中,文献[5] 设计了一种动态、能量有效的层次分簇算法,然而算法仅考 虑了节点能量,并没有同时考虑节点在网络中的分布,具有 一定的局限性;而文献[6]设计了一种综合考虑节点能量与节 点分布的路由协议,然而该算法需要 GPS 的辅助,大大增 加了无线传感器网络的成本。 本 文 中 所 提 出 的 分 布 式 节 能 路 由 算 法 DEER (Distributed and Energy-Economical Routing)在无需任何 定位装置或定位算法的前提条件下,综合考虑节点剩余能量 以及节点在网络中的分布,选出具有较高能量,且簇内传输 损耗较小的节点作为簇首,从而延长了传感器网络的使用寿 命。

2 网络结构描述
本文所提出的 DEER 路由算法采用分层网络拓扑结构, 整个算法由簇首选择阶段与数据传输阶段两部分组成。在簇 首选择阶段,所有节点通过设定机制选择簇首,当所有节点 都有归属簇后,开始进行数据传输;为了平衡负载,使节点 能量消耗分布平均,在一定时间后重复初始的簇首选择过

第5期



宁等: 基于博弈理论的无线传感器网络分布式节能路由算法 成为簇首时的支付方程 π ;

1231

程。其中网络模型假设如下: (1)所有传感器节点都处于准静止状态; (2)节点没有位置感知功能, 不能如文献[2]中的路由协议 一样,得到簇首或者其它节点的位置信息; (3)所有节点都是平等的,没有特殊节点存在,但节点初 始能量可以不同; (4)节点一旦部署,即进入自组织自控制模式,没有任何 中心控制信息; (5)为了简化节点节省能量, 假设节点射频仅有两个传输 范围,分别为节点间的小范围传输及节点至基站的大范围传 输; (6)不需要预先设置簇首数或者选择概率。

(2)每一个节点建立邻节点信息集合,并广播 π 值; (3)接收到邻节点 π 值的节点,将其与自身 π 值进行比 较,并将大于自身 π 值的邻节点记录到邻节点信息集中; (4)如果节点的邻节点信息集为空,则自动成为簇首,并 广播簇首选择信息;接收到一个或多个簇首选择信息的邻节 点,发送归属信息加入 π 值最大的簇首节点,此时若多个簇 首选择信息中的簇首节点具有相同的 π 值,则随机选择一个 作为归属簇并发送归属信息; (5)如果无线传感器节点收到了来自自身邻节点信息集 中某个节点发送的归属信息,却没收到任何簇首选择信息, 则表明该节点不在任何已生成簇首的传输范围之内,该节点 将由邻节点信息集中删去已有归属簇的邻节点,并回到(4); (6)当所有参与人均决定自身策略后,分层式路由建立, 并开始数据传输。 由以上步骤可以看出,本算法中的均衡与传统的纳什均 衡有所不同,首先本路由算法中的博弈为扩展式博弈中的多 阶段可观察行动博弈,在整个过程中,博弈分阶段进行,所 有参与人在某一阶段选择策略行动时均知道所有相关参与 人在以前阶段所选择的行动;其次所有参与者在选择行动时 均是根据所有相关参与人的历史行动策略以及相关信息做 出策略选择;再次该多阶段博弈的策略组合在每一个阶段均 为纳什均衡;而最终策略组合为完美子博弈均衡。 路由算法时间复杂度分析:DEER 路由算法中,最直接 的时间复杂度影响因素是决策过程中的(4)-(5)迭代。由上述 路由决策过程可以得出,当节点成为簇首并发送簇首选择信 息后,该节点传输范围内存在且仅存在一个簇首,而每次簇 首选择迭代至少生成一个簇,因此簇首选择及决策过程中的 迭代次数由传感器区域中生成的簇首数决定,即由大小为
L ? L 的区域与小范围传输半径 A 来决定, 与节点数 N 无关。

3 分布式节能路由算法(DEER)
在无线传感器网络中,路由算法需要尽可能地保证单个 节点与整个网络同时得到能量优化,从而延长网络寿命,而 两者的优化是相互依存又彼此矛盾的。单个节点的能量最优 策略将减少节点之间的合作,增加节点直接与基站进行数据 传输的次数,这对于网络能量节省是十分不利的;而网络能 量最优策略可能由于过度使用某些热点节点,而使其能量过 早耗尽,从而影响网络的整体传输性能。为了解决路由算法 中整体与个体的矛盾,引入经济学中分析冲突与合作的博弈 理论[7],并在此基础上提出了新的路由算法。 在分布式节能路由算法 DEER 中, 网络中所有无线传感 器节点构成理性参与人集合 S = {s1, s2,
, sn } ;每一次簇首

选择过程中,节点是否成为簇首的决策作为该节点的策略, 而 所 有 节 点 策 略 构 成 本 次 簇 首 选 择 纯 策 略 集 合 L = {l1,
l2, , ln } ,其中,如果节点为簇首, li = 1 ;否则 li = 0 。

此外,分层路由算法的均衡点定义为簇首选择时,每一 个节点根据支付方程 π 得出的最佳簇首选择方案,也就是最 佳策略集合。其中节点 i 成为簇首的支付方程为
πi = εEi / E init ? (1 ? ε)∑ Ppathloss / ni ? PGen , 0 ≤ ε ≤ 1 (1)

因此若小范围传输区域为 (A / 2) ? (A / 2) ,此时最大簇首 生成迭代次数即最大簇首生成时间复杂度为
? L ?2 ? ? ? N iter ≤ ? ? ≈ O(1) ? ? ?A / 2 ? ?

内的邻节点数目, ∑ Ppathloss 表示邻节点到节点 i 的路径损

在支付方程中, Ei 为节点 i 的剩余能量, ni 为在节点 i 范围

(2)

耗之和, E init 与 PGen 分别是节点的初始能量以及节点间传 而 输时的最大传输路径损耗。因此, Ei / E init 表示节点的归一 化能量,保证了节点在剩余能量较少的情况下,成为簇首的 概率较小; ?∑ Ppathloss / ni ? PGen 表示节点周围邻节点到自 而 身的平均路径损耗归一化,该值保证邻节点到备选簇首的平 均路径损耗较小的节点,成为最终簇首的概率较大;调节参 数 ε 为方程调节因子。该支付方程综合考虑了节点剩余能量 以及邻节点到节点自身的平均路径损耗,从而得出合理有效 的簇首选择方案。 具体分布式节能路由决策过程如下: (1)利用博弈思想建立网络模型,包括:参与人集合 S ; 所有节点在某个时刻的策略所构成的策略集 L ;以及节点 i

由式(2)可以看出,最大簇首生成时间复杂度为有限次,且与 网络中节点数目无关,不会随着网络节点规模的增加而增 大;同时,若网络覆盖面积增加,则最大簇首生成时间将会 随着网络覆盖规模的增加而增大。

4 仿真验证及分析
4.1 仿真参数 仿真将所提出的分布式节能路由算法与所熟知的 LEACH 算法进行比较, 由于网络中节点初始能量可以不同, 因此使用了文献[8]中的 LEACH 协议的改进 gen-LEACH 算 法,即簇首基于剩余能量进行选择,其簇首选择概率为 Pi (t ) ? ? ? E (t ) ? = min ? i k,1? ,其中 Ei (t ) 为节点 i 的剩余功率,而 ? ? ? E total (t ) ? ? ? ? ?

1232

电 子 与 信 息 学 报 4.2.2 网络寿命比较

第 30 卷 本处将所提出的 DEER 协议与 gen-

E total (t ) 为网络中所有节点的平均功率。 其它仿真参数如表 1

所示。
表 1 仿真参数 信令包长度 数据包长度 电路消耗能量 Eelec 近距离放大器参数 ε fs 远距离放大器参数 ε mp 数据整合能量 EDA 传感器初始能量 簇首重选间隔时间 ε值 25byte 100 byte 50 nJ/bit 10 pJ/bit/ m
2

LEACH 协议进行比较,采取 3 个时间点考察网络性能:首 节点死亡时间,40%节点死亡时间,末节点死亡时间。网络 寿命通过 Round 来表示,仿真计入重要的开销。 从性能比较可以看到, 无论是 gen-LEACH 还是 DEER, 性能均随着传感器布设区域至基站距离的增大而降低。此外 由图 2 可以看到,当网络中存在 100 节点时,由于 genLEACH 按照 5%的比例产生簇首, 因此簇首较少, 长距离传 输较少,其首节点性能略好于 DEER,但是由 40%与末节点
4

0.0013 pJ/bit/ m 5 nJ/bit/signal 2 J/node

消亡性能可以看出 gen-LEACH 的整体性能差于 DEER;在 图 3 中,当网络中存在 300 节点时, DEER 簇首数量与 gen-LEACH 差不多,此时 DEER 协议的网络寿命曲线性能 均大大优于 gen-LEACH 协议。

5 TDMA frames 0.4

在仿真参数表中,传输能量损耗包含信令传输能量损耗 与数据传输能量损耗两部分。本算法中,信令能量损耗主要 集中在 π 值信息广播与簇首信息广播两部分,在仿真中这两 部分信令包也同样得到考虑。 此外,对于连续传输传感器网络,由于簇首承担了繁重 的传输和处理任务,因此过长时间或者过短时间的簇首重选 间隔均不适当。具体来说,长时间的簇首重选间隔会由于大 量的转发和处理任务而造成首节点消亡失间的大幅度提前; 短时间的簇首重选间隔则会使得簇首重选过于频繁,造成系 统开销增大。 综上, 簇首重选间隔时间单位为秒级甚至更短, 在此设置的 5 TDMA frames 作为簇首重选间隔。 4.2 仿真结果及分析 4.2.1 网络簇首分布状况比较 节点。 由仿真可以看到,在 gen-LEACH 协议中,存在簇首分 布不均匀不合理现象(圈中所示),而在 DEER 协议中,簇首 节点囊括了尽可能多的普通传感器节点且分布均匀合理。这 是由于在 DEER 路由协议中,首先簇首节点不会彼此覆盖, 从而避免了多个簇首节点相距较近的情况;此外,考虑了节 点到簇首节点的路径损耗,从而使簇首节点分布比较均匀, 且位置较为合理。
[1] application-specific microsensor
图 2 100 节点寿命比较 图 3 300 节点寿命比较

DEER 曲线性能优异的原因, 首先是由于网络中簇首个 数在网络大小固定后,基本固定,不会随着网络内部节点数 量的增加, 造成簇首数量的增加, 具有很强的扩展性;其次, 网络中簇首均匀分布,且综合考虑自身剩余能量与节点分 布,从而使簇首的选择更加合理。

该部分重点考察 300 节点网

络中,簇首分布是否合理。图 1 中圆圈为簇首,星号为普通

5 结束语
本文通过对博弈理论及在无线传感器网络中的应用研 究,提出了一种兼顾节点能量与节点分布的传感器网络路由 算法 DEER。仿真结果显示,本算法能够有效地使簇首节点 均匀合理分布,从而平衡网络负载,节省节点能量,延长网 络寿命。

参 考 文 献
Heinzelman W, Chandrakasan A, and Balakrishnan H. An protocol architecture
Trans.

for
on

wireless
Wireless

networks.

IEEE

Communications, 2002, 1(4): 660-667.

[2]

Yu Y, Govindan R, and Estrin D. Geographical and energy-aware routing: a recursive data dissemination

protocol for wireless sensor networks. Technical Report UCLA-CSD
图 1

TR-01-0023,

Los

Angeles:

University

of

California, 2001: 1-11.

第5期
[3]



宁等: 基于博弈理论的无线传感器网络分布式节能路由算法
[7] [8]

1233

Kannan R, Ray L, and Iyengar S S, et al.. Max-min length-energy-constrained routing in wireless sensor networks. Proceedings of 1st European Conference Workshop on Wireless Sensor Networks, Berlin, Germany, January 18-21, 2004: 234-249.

Myerson R B. Game Theory–Analysis of Conflict. Boston: Harvard University Press, 1991, Chapter 4. Younis O and Fahmy S. Distributed clustering in ad-hoc sensor networks: A hybrid, energy-efficient approach. Proceedings of IEEE INFOCOM on Computer and

[4]

Kannan R and Iyengar S S. Game-theoretic models for reliable path-length and energy-constrained routing with data aggregation in wireless sensor networks. IEEE Trans. on
Selected Areas of Communications, 2004, 22(6): 1141-1150. 杨

Communications Societies, Hongkong, China, March 7-11, 2004, Vol. 1: 629-640.

宁:

男,1981 年生,博士生,研究方向为无线传感器网络、

[5]

Wang Weidong and Zhu Qingxin. A hierarchical clustering algorithm and cooperation analysis for wireless sensor networks. Journal of Software, 2006, 17(5): 1157-1167.


Ad hoc 网络等.
辉: 女,1963 年生,教授,主要研究方向为下一代无线通信 网、Ad hoc 网络、无线传感器网络等. 黄 平: 男,1982 年生,硕士生,研究方向为无线传感器网络、

[6]

Zheng Zengwei, Wu Zhaohui, and Lin Huaizhong. Clustering routing algorithm using game-theoretic techniques for WSNs. Proceedings of 2004 IEEE International Symposium on Circuits and Systems, Vancouver, BC, Canada, May 23-26, 2004, Vol. 4: 904-907.

Ad hoc 网络.
张 平: 男,1959 年生,教授,博士生导师,主要研究方向为下 一代无线通信新理论与新技术.


相关文档

基于博弈论的无线传感器网络非均匀分簇路由算法
无线传感器网络中的节能路由算法
基于无线传感器网络的Multi_topLEACH节能路由算法实现
基于博弈论的无线传感器网络路由算法研究
一种分布式无线传感器网络能量均衡路由算法
基于分簇的无线传感器网络节能路由算法
无线传感器网络簇间节能路由算法
无线传感器网络中基于K均值聚类算法的节能层次路由算法
无线传感器网络动态成簇节能路由算法研究
无线传感器网络不等规模节能分簇路由算法
电脑版