能量均衡的间断连接无线网络数据转发策略

工程科学学报，第39卷，第6期：962-971,2017年6月 Chinese Journal of Engineering,Vol.39,No.6:962-971,June 2017 D0L:10.13374/j.issn2095-9389.2017.06.020;htp:/journals..usth.edu.cn 能量均衡的间断连接无线网络数据转发策略 杨 鹏23)，司书山12)四，许稳2)，杨静2)，张鸿12) 1)重庆邮电大学通信与信息工程学院，重庆4000652)重庆高校市级光通信与网络重点实验室，重庆400065 3)中国信息通信研究院，北京100191 ☒通信作者，E-mail:1063603919@q9-com 摘要针对间断连接无线网络中节点负载不均衡和能量资源受限的问题，提出了一种能量有效的数据转发策略.该策略 根据网络运行的历史相遇信息，充分考虑网络特性，以分布式方式估计节点的活跃度、剩余能量和数据转发率，准确地估计节 点效用值，感知网络节点的服务能力，以帕累托最优作为自适应选择最佳下一跳中继节点的理论依据，执行数据转发操作，有 效地解决了由于节点自私性所导致的网络性能下降.数值结果表明，与其他能量管理机制相比，所提出的机制能够均衡网络 节点负载，有效解决网络“热点”问题，延长网络生存时间，使投递率、时延等系统性能都得到大幅度提升 关键词间断连接无线网络：负载均衡：帕累托最优：效用值 分类号TP929.5 Data forwarding strategy for wireless network with intermittent connectivity based on energy equilibrium YANG Peng 2),SI Shu-shan'),XU Wen'2),YANG Jing )ZHANG Hong 2) 1)School of Telecommunication and Information Engineering,Chongqing University of Posts and Telecommunications,Chongqing 400065,China 2)Optical Communication and Network Key Laboratory of Chongqing,Chongqing 400065,China 3)China Academy of Information and Communications Technology,Beijing 100191,China Corresponding author,E-mail:1063603919@qq.com ABSTRACT A suitable energy management mechanism for a wireless network with intermittent connectivity was proposed to deal with unbalanced load and limited energy resources of nodes.According to the historical information,the active degree,residual energy and data forwarding rate of nodes were estimated in a distributed way.In addition,the node utility was effectively estimated by fully considering network features.Furthermore,the proposed mechanism employs the serviceability differences of nodes and the Pareto optimal theory to choose the best next-hop relay node adaptively.The data forwarding operation was executed.Thus the network performance degradation caused by selfish nodes was prevented effectively.The simulation results show that the proposed mechanism can not only balance the load on nodes and solve the problem of network "hotspots",but also prolong network lifetime and improve its delivery rate and delay performance greatly compared to other energy management mechanisms. KEY WORDS intermittent connectivity wireless network;load balance;Pareto optimal theory;utility value 间断连接无线网络(intermittent connected wireless 的“存储-携带-转发”的协作方式逐跳进行传输， network,ICWN)不需要源节点和目的节点在转发数据 ICWN具有自组织、节点稀疏、间歇连接、资源受限、负 前建立完整的端到端路径，消息在节点间以更加灵活 载不均衡、拓扑动态变化等特性].在这种复杂多变 收稿日期：2016-07-19

工程科学学报,第 39 卷,第 6 期:962鄄鄄971,2017 年 6 月 Chinese Journal of Engineering, Vol. 39, No. 6: 962鄄鄄971, June 2017 DOI: 10. 13374 / j. issn2095鄄鄄9389. 2017. 06. 020; http: / / journals. ustb. edu. cn 能量均衡的间断连接无线网络数据转发策略 杨 鹏1,2,3) , 司书山1,2) 苣 , 许 稳1,2) , 杨 静1,2) , 张 鸿1,2) 1) 重庆邮电大学通信与信息工程学院, 重庆 400065 2) 重庆高校市级光通信与网络重点实验室, 重庆 400065 3) 中国信息通信研究院, 北京 100191 苣通信作者, E鄄mail: 1063603919@ qq. com 摘 要 针对间断连接无线网络中节点负载不均衡和能量资源受限的问题,提出了一种能量有效的数据转发策略. 该策略 根据网络运行的历史相遇信息,充分考虑网络特性,以分布式方式估计节点的活跃度、剩余能量和数据转发率,准确地估计节 点效用值,感知网络节点的服务能力,以帕累托最优作为自适应选择最佳下一跳中继节点的理论依据,执行数据转发操作,有 效地解决了由于节点自私性所导致的网络性能下降. 数值结果表明,与其他能量管理机制相比,所提出的机制能够均衡网络 节点负载,有效解决网络“热点冶问题,延长网络生存时间,使投递率、时延等系统性能都得到大幅度提升. 关键词 间断连接无线网络; 负载均衡; 帕累托最优; 效用值 分类号 TP929郾 5 Data forwarding strategy for wireless network with intermittent connectivity based on energy equilibrium YANG Peng 1,2,3) , SI Shu鄄shan 1,2) 苣 , XU Wen 1,2) , YANG Jing 1,2) , ZHANG Hong 1,2) 1) School of Telecommunication and Information Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, China 2) Optical Communication and Network Key Laboratory of Chongqing, Chongqing 400065, China 3) China Academy of Information and Communications Technology, Beijing 100191, China 苣Corresponding author, E鄄mail:1063603919@ qq. com ABSTRACT A suitable energy management mechanism for a wireless network with intermittent connectivity was proposed to deal with unbalanced load and limited energy resources of nodes. According to the historical information, the active degree, residual energy and data forwarding rate of nodes were estimated in a distributed way. In addition, the node utility was effectively estimated by fully considering network features. Furthermore, the proposed mechanism employs the serviceability differences of nodes and the Pareto optimal theory to choose the best next鄄hop relay node adaptively. The data forwarding operation was executed. Thus the network performance degradation caused by selfish nodes was prevented effectively. The simulation results show that the proposed mechanism can not only balance the load on nodes and solve the problem of network “hotspots冶, but also prolong network lifetime and improve its delivery rate and delay performance greatly compared to other energy management mechanisms. KEY WORDS intermittent connectivity wireless network; load balance; Pareto optimal theory; utility value 收稿日期: 2016鄄鄄07鄄鄄19 间断连接无线网络( intermittent connected wireless network, ICWN)不需要源节点和目的节点在转发数据 前建立完整的端到端路径,消息在节点间以更加灵活 的“存储鄄鄄 携带鄄鄄 转发冶 的协作方式逐跳进行传输[1] , ICWN 具有自组织、节点稀疏、间歇连接、资源受限、负 载不均衡、拓扑动态变化等特性[2] . 在这种复杂多变

杨鹏等：能量均衡的间断连接无线网络数据转发策略 ·963· 的组网环境下，节点需要消耗大量能量来探测邻居节 数据转发看成多个非合作子博弈过程，要求链路上的 点，并利用移动带来的相遇机会进行通信，因此，优化 负载均衡分担，虽然降低了网络的投递时延，优化了网 网络能耗，提高网络可靠性成为研究间断连接无线网 络的整体性能，但未考虑网络节点的自私性 络的关键问题[) 为了克服上述策略的不足，本文结合间断连接无 在拓扑动态变化的ICWN中，由节点移动产生的 线网络实际环境和帕累托最优理论，提出了一种能量 相遇机会十分珍贵，因此，部分较活跃的节点在数据转 均衡的数据转发策略(energy equilibrium data forward-- 发过程中会起到非常重要的作用，它们能够较快地将 ing strategy,EEDFS).该策略采用分布式方式评估节 数据中继到目的节点[-).然而，由于此类节点所转发 点的活跃度、剩余能量和数据转发率，预测节点的转发 的数据较多，有限的能量资源过度消耗将导致节点过 意愿强度，同时兼顾链路的可靠性，采用帕累托最优理 早死亡，这会对网络的可靠性及生存性造成极大威胁， 论动态选择最优下一跳中继节点.与其他策略相比， 产生网络“热点”问题6.目前，国内外研究人员多采 所提策略能够充分考虑节点的转发能力，选取剩余能 用优化邻居节点探测能耗的方式来减少节点能量消 量充足且转发意愿强的节点作为中继节点，有效地提 耗，但这些方法未考虑“热点”问题，选取任意节点进 高了通信链路的可靠性和数据转发率，并解决了“热 行合作转发，忽略了网络节点因能量受限而引起的自 点”问题带来的网络性能下降.本文的主要贡献如下. 私性，即节点并非每次都愿意为其他节点转发数据，从 (1)提出用转发意愿来衡量节点为其他节点提供 而，会造成整体网络性能下降[-).因此，如何综合考 转发服务的概率.以分布式的方法评估节点的活跃 虑节点剩余能量和活跃度是选择最佳下一跳中继节点 度、剩余能量以及数据转发率并以此对节点的转发意 的关键问题. 愿进行量化，解决了网络中存在的“热点”问题和节点 根据间断连接无线网络数据转发原理，可将数据 自私性问题，并提高了数据的传播速度和投递率，降低 转发过程看作网络资源分配问题)，并通过博奔论的 了数据的投递时延，使网络性能得到较大改善. 理论知识分析解决，将上一跳节点和下一跳节点作为 (2)利用帕累托最优理论对网络进行扩展式动态 博弈双方，通过博弈上一跳节点获得下一跳节点为其 博弈建模分析，设计出了一种高效的合作数据转发机 提供的数据转发服务，下一跳节点获得上一跳节点为 制(EEDS).该机制将网络中的节点看作是博弈的有 其提供的互惠收益.针对上述“热点”问题，国内外相 限个参与者，将最佳下一跳中继节点的选择看作资源 关研究人员把博弈论应用到ICWN研究中[o-],以解 配置问题，采用局部信息对网络进行建模分析，从网络 决节点负载不均衡和自私性问题，进而建立有效的管 运行环境中获取信息，计算节点的效用函数同时对其 理机制，提高有限网络资源的利用率，优化网络性能. 他节点的状态和行为动机作出合理地判断，从而选择 文献[12]基于博弈论提出了一种分布式可扩展 最佳的合作对象 的数据转发策略.该策略对节点的中继转发请求进行 1节点服务状态分析 选择性接收，推导出了纳什均衡的存在性并给予求解， 进而，选择合适的中继节点，达到优化网络性能的目 如前所述，节点的活跃度能够衡量节点的负载状 的.然而，其使用的假设条件过于牵强，与实际网络运 况、重要程度以及节点对网络的贡献程度，剩余能量百 行环境有一定差距.Wang等为了解决ICWN中的资 分比是节点自身资源水平的直接表达，数据转发率能 源分配问题，在文献[13]中提出联盟博弈模型.通过 够客观地反映节点转发服务状态，因此，这三个参数能 分析多个理性联盟的收益与代价函数，判决是否允许 够客观地评价节点服务状态，并为下一跳中继节点的 节点加人联盟，在一定程度上能够激励节点的合作意 选择提供科学依据，本节将对其进行具体分析 愿，但是在网络拓扑动态变化的ICWN中，节点的移动 1.1节点活跃度估计 使得策略中联盟的划分和维护实现难度较大.文献 在网络拓扑动态变化的ICN中，若某个节点在 [14]提出基于概率的节点自私行为检测的博弈模型. 网络中与其他节点的相遇持续时间长、相遇时间间隔 采用传统的博弈理论验证其合理性，并在网络中部署 短、相遇频率高，则该节点便能够将数据迅速转发给其 了一些可信且概率适中的节点，以保证数据安全转发， 他节点，从而提高数据的传播速度和投递率，降低数据 并使得投递代价降低，达到优化网络性能的目的，但该 的投递时延，达到改善网络性能的目的，因此，本文引 模型未考虑随着可信节点自身资源消耗，其自私性也 入节点活跃度来衡量节点在网络中的重要程度，并精 会加重的问题.此外，文献[15]设计出负载均衡的博 确地估计该参数. 弈数据转发策略，将数据的投递时延作为效用函数，把 如前所述，节点间的平均相遇次数和平均相遇持

杨 鹏等: 能量均衡的间断连接无线网络数据转发策略 的组网环境下,节点需要消耗大量能量来探测邻居节 点,并利用移动带来的相遇机会进行通信,因此,优化 网络能耗,提高网络可靠性成为研究间断连接无线网 络的关键问题[3] . 在拓扑动态变化的 ICWN 中,由节点移动产生的 相遇机会十分珍贵,因此,部分较活跃的节点在数据转 发过程中会起到非常重要的作用,它们能够较快地将 数据中继到目的节点[4鄄鄄5] . 然而,由于此类节点所转发 的数据较多,有限的能量资源过度消耗将导致节点过 早死亡,这会对网络的可靠性及生存性造成极大威胁, 产生网络“热点冶问题[6] . 目前,国内外研究人员多采 用优化邻居节点探测能耗的方式来减少节点能量消 耗,但这些方法未考虑“热点冶问题,选取任意节点进 行合作转发,忽略了网络节点因能量受限而引起的自 私性,即节点并非每次都愿意为其他节点转发数据,从 而,会造成整体网络性能下降[7鄄鄄8] . 因此,如何综合考 虑节点剩余能量和活跃度是选择最佳下一跳中继节点 的关键问题. 根据间断连接无线网络数据转发原理,可将数据 转发过程看作网络资源分配问题[9] ,并通过博弈论的 理论知识分析解决,将上一跳节点和下一跳节点作为 博弈双方,通过博弈上一跳节点获得下一跳节点为其 提供的数据转发服务,下一跳节点获得上一跳节点为 其提供的互惠收益. 针对上述“热点冶问题,国内外相 关研究人员把博弈论应用到 ICWN 研究中[10鄄鄄11] ,以解 决节点负载不均衡和自私性问题,进而建立有效的管 理机制,提高有限网络资源的利用率,优化网络性能. 文献[12]基于博弈论提出了一种分布式可扩展 的数据转发策略. 该策略对节点的中继转发请求进行 选择性接收,推导出了纳什均衡的存在性并给予求解, 进而,选择合适的中继节点,达到优化网络性能的目 的. 然而,其使用的假设条件过于牵强,与实际网络运 行环境有一定差距. Wang 等为了解决 ICWN 中的资 源分配问题,在文献[13]中提出联盟博弈模型. 通过 分析多个理性联盟的收益与代价函数,判决是否允许 节点加入联盟,在一定程度上能够激励节点的合作意 愿,但是在网络拓扑动态变化的 ICWN 中,节点的移动 使得策略中联盟的划分和维护实现难度较大. 文献 [14]提出基于概率的节点自私行为检测的博弈模型. 采用传统的博弈理论验证其合理性,并在网络中部署 了一些可信且概率适中的节点,以保证数据安全转发, 并使得投递代价降低,达到优化网络性能的目的,但该 模型未考虑随着可信节点自身资源消耗,其自私性也 会加重的问题. 此外,文献[15]设计出负载均衡的博 弈数据转发策略,将数据的投递时延作为效用函数,把 数据转发看成多个非合作子博弈过程,要求链路上的 负载均衡分担,虽然降低了网络的投递时延,优化了网 络的整体性能,但未考虑网络节点的自私性. 为了克服上述策略的不足,本文结合间断连接无 线网络实际环境和帕累托最优理论,提出了一种能量 均衡的数据转发策略( energy equilibrium data forward鄄 ing strategy, EEDFS). 该策略采用分布式方式评估节 点的活跃度、剩余能量和数据转发率,预测节点的转发 意愿强度,同时兼顾链路的可靠性,采用帕累托最优理 论动态选择最优下一跳中继节点. 与其他策略相比, 所提策略能够充分考虑节点的转发能力,选取剩余能 量充足且转发意愿强的节点作为中继节点,有效地提 高了通信链路的可靠性和数据转发率,并解决了“热 点冶问题带来的网络性能下降. 本文的主要贡献如下. (1)提出用转发意愿来衡量节点为其他节点提供 转发服务的概率. 以分布式的方法评估节点的活跃 度、剩余能量以及数据转发率并以此对节点的转发意 愿进行量化,解决了网络中存在的“热点冶问题和节点 自私性问题,并提高了数据的传播速度和投递率,降低 了数据的投递时延,使网络性能得到较大改善. (2)利用帕累托最优理论对网络进行扩展式动态 博弈建模分析,设计出了一种高效的合作数据转发机 制(EEDFS). 该机制将网络中的节点看作是博弈的有 限个参与者,将最佳下一跳中继节点的选择看作资源 配置问题,采用局部信息对网络进行建模分析,从网络 运行环境中获取信息,计算节点的效用函数同时对其 他节点的状态和行为动机作出合理地判断,从而选择 最佳的合作对象. 1 节点服务状态分析 如前所述,节点的活跃度能够衡量节点的负载状 况、重要程度以及节点对网络的贡献程度,剩余能量百 分比是节点自身资源水平的直接表达,数据转发率能 够客观地反映节点转发服务状态,因此,这三个参数能 够客观地评价节点服务状态,并为下一跳中继节点的 选择提供科学依据,本节将对其进行具体分析. 1郾 1 节点活跃度估计 在网络拓扑动态变化的 ICWN 中,若某个节点在 网络中与其他节点的相遇持续时间长、相遇时间间隔 短、相遇频率高,则该节点便能够将数据迅速转发给其 他节点,从而提高数据的传播速度和投递率,降低数据 的投递时延,达到改善网络性能的目的,因此,本文引 入节点活跃度来衡量节点在网络中的重要程度,并精 确地估计该参数. 如前所述,节点间的平均相遇次数和平均相遇持 ·963·

·964· 工程科学学报，第39卷，第6期 续时间可以作为衡量节点活跃度的两个重要因素.因 此，将节点的活跃度(active degree,AD)定义为节点在 ACDI I En'l (7) 给定时间段T内有效相遇时间所占的比例，如下式 将式(5)和(7)带入(1)可求得网络中任意给定节 所示. 点i的活跃度，如下式所示.可见，节点的活跃度与给 AD =AMT,ACDT12.3.. (1) 定T无关，与网络节点数n及相遇节点数IEn1有关. T 式中，AMT:表示给定节点i与其他节点的平均相遇次 (n-1)∑ AD, jijcEn 数；ACDT:是给定节点i与其他节点的平均相遇持续 ∑ ,i=1,2,3,…,n.(8) 时间. jrijc Ea' 1.2节点能量估计方法 在ICWN中活跃度较高的节点所承载的网络负载 活跃节点能够以较高概率投递数据，降低数据投 较大，因此，为了准确评估网络节点的活跃度，衡量节 递时延，但是由于“热点”问题，网络的可靠性及生存 点的负载状况，本文根据节点运动过程中所存储的历 性受到了极大的挑战.因此，需要综合考虑节点的活 史信息，以分布式方式计算任意两节点间的平均相遇 跃度和剩余能量选择最佳下一跳中继节点，解决这种 次数.假定在给定时间段T内，与给定节点i相遇的节 负载不均衡问题 点集合为En={Eni,En,En…En},相遇的节点个 在资源受限的ICWN中，节点主要依靠电池供电， 数是IE'1,则给定节点i与任意节点j的相遇时间间 由于网络环境复杂多变，节点不能更换电池也不能及 隔如下式所示： 时充电，因此能量资源十分受限.为了节省有限的能 e=min{(t-to):‖L,(t)-L,(t)‖≤R},t>to 量资源，网络中的节点并非总是自愿为其他节点转发 (2) 数据，拒绝为其他节点服务或者丢弃数据的节点会给 式中，L,()、L(1)分别表示节点i和j在时刻t的坐 网络带来一定的风险6.如果节点倾向于不活跃，可 标：R是两节点的传输半径；。为上次两者离开彼此 以在一定程度上减轻节点的负载压力，但是对数据的 通信半径的时刻；‖·胰示距离. 成功投递率和时延会造成较大的影响.因此，有效量 根据网络运行历史相遇信息，可以估计给定节点i 化节点的剩余能量是本文亟待解决的另一个关键 在T内，与其他节点的平均相遇时间间隔： 问题. ∑只er 国内外大量研究结果表明，ICWN节点的能耗主 EMTL,=产iE 要用于邻居节点探测、数据发送和数据接收三个过程， I Enl (3) 网络节点在三种工作状态间切换].在邻居节点探 可见，节点的EMTL越小，则节点间相遇频率越 测过程中，节点在其通信范围内广播探测信标消息 高.因此，在T内，节点间总的相遇次数TMT(total (probing beacon,PB),探测邻居节点的存在并建立通 meet times)可表示为： 信连接，邻居节点探测能耗是节点扫描信道所消耗的 -2 (4) 能量，用E。表示.数据发送能耗E。和数据接收能耗 E,则由转发数据的大小决定.因此，本文在给定T时 式中，n为网络中节点总数.进而，给定节点i与网络 间段内，建立节点能耗矩阵，如下式所示 中其他节点的平均相遇次数如下式所示： AMT,TMT.=T(a-1) (5) n EMTI. E=Ep E E. (9) 同理，给定节点i在T内，与任意节点j相遇持续 EpE。 E 时间为： 式中，E是由状态i转移到状态j的能量消耗，若m= mm=min{(t-te):‖L,(t)-L,(t)‖>R},t>le. n,则表示节点持续在m状态下的能耗. (6) 根据上述能量消耗矩阵E,可以估计任意给定节 式中，。表示节点i和j进入彼此通信范围的时刻：若 点i在t时刻总能量消耗，如下式所示： c为t.的前一时刻，则有‖L()-L(t)‖>和 Ea()=∑∑E (10) P,,因P,, 川L(1)-L(t)‖=R,其他参数与式(2)相同. 进而，任意给定节点i的剩余能量可表示为： 给定节点i在T内，与其他节点的平均相遇持续 E()=E.(t)-E(t).(11) 时间为： 式中，E,()为上一更新时段T结束时刻节点剩余能

工程科学学报,第 39 卷,第 6 期 续时间可以作为衡量节点活跃度的两个重要因素. 因 此,将节点的活跃度(active degree, AD)定义为节点在 给定时间段 T 内有效相遇时间所占的比例,如下式 所示. ADi = AMTiACDTi T ,{i = 1,2,3…,n}. (1) 式中,AMTi 表示给定节点 i 与其他节点的平均相遇次 数;ACDTi 是给定节点 i 与其他节点的平均相遇持续 时间. 在 ICWN 中活跃度较高的节点所承载的网络负载 较大,因此,为了准确评估网络节点的活跃度,衡量节 点的负载状况,本文根据节点运动过程中所存储的历 史信息,以分布式方式计算任意两节点间的平均相遇 次数. 假定在给定时间段 T 内,与给定节点 i 相遇的节 点集合为 En i = {En i 1 ,En i 2 ,En i 3 …En i n },相遇的节点个 数是| En i | ,则给定节点 i 与任意节点 j 的相遇时间间 隔如下式所示: t ij inter = min {(t - t 0 ):椰Li(t) - Lj(t)椰臆R ij T },t > t 0 . (2) 式中,Li(t)、Lj ( t) 分别表示节点 i 和 j 在时刻 t 的坐 标;R ij T 是两节点的传输半径;t 0 为上次两者离开彼此 通信半径的时刻;椰·椰表示距离. 根据网络运行历史相遇信息,可以估计给定节点 i 在 T 内,与其他节点的平均相遇时间间隔: EMTIi = 移 j屹i,j沂En i t ij inter | En i | . (3) 可见,节点的 EMTIi 越小,则节点间相遇频率越 高. 因此,在 T 内,节点间总的相遇次数 TMT ( total meet times)可表示为: TMTi = Tn(n - 1) EMTIi . (4) 式中,n 为网络中节点总数. 进而,给定节点 i 与网络 中其他节点的平均相遇次数如下式所示: AMTi = TMTi n = T(n - 1) EMTIi . (5) 同理,给定节点 i 在 T 内,与任意节点 j 相遇持续 时间为: t ij duration = min {(t - t c):椰Li(t) - Lj(t)椰 > R ij T },t > t c . (6) 式中,t c 表示节点 i 和 j 进入彼此通信范围的时刻;若 t - c 为 t c 的前一时刻,则有椰Li(t - c ) - Lj( t - c )椰 > R ij T 和 椰Li(t c) - Lj(t c)椰 = R ij T ,其他参数与式(2)相同. 给定节点 i 在 T 内,与其他节点的平均相遇持续 时间为: ACDIi = 移i屹j,j沂En i t ij duration | En i | . (7) 将式(5)和(7)带入(1)可求得网络中任意给定节 点 i 的活跃度,如下式所示. 可见,节点的活跃度与给 定 T 无关,与网络节点数 n 及相遇节点数| En i | 有关. ADi = (n - 1) 移 j屹i,j沂En i t ij duration 移 j屹i,j沂En i t ij inter , i = 1,2,3,…,n. (8) 1郾 2 节点能量估计方法 活跃节点能够以较高概率投递数据,降低数据投 递时延,但是由于“热点冶问题,网络的可靠性及生存 性受到了极大的挑战. 因此,需要综合考虑节点的活 跃度和剩余能量选择最佳下一跳中继节点,解决这种 负载不均衡问题. 在资源受限的 ICWN 中,节点主要依靠电池供电, 由于网络环境复杂多变,节点不能更换电池也不能及 时充电,因此能量资源十分受限. 为了节省有限的能 量资源,网络中的节点并非总是自愿为其他节点转发 数据,拒绝为其他节点服务或者丢弃数据的节点会给 网络带来一定的风险[16] . 如果节点倾向于不活跃,可 以在一定程度上减轻节点的负载压力,但是对数据的 成功投递率和时延会造成较大的影响. 因此,有效量 化节点的剩余能量是本文亟待解决的另一个关键 问题. 国内外大量研究结果表明,ICWN 节点的能耗主 要用于邻居节点探测、数据发送和数据接收三个过程, 网络节点在三种工作状态间切换[17] . 在邻居节点探 测过程中,节点在其通信范围内广播探测信标消息 (probing beacon, PB),探测邻居节点的存在并建立通 信连接,邻居节点探测能耗是节点扫描信道所消耗的 能量,用 Ep 表示. 数据发送能耗 Es 和数据接收能耗 Er 则由转发数据的大小决定. 因此,本文在给定 T 时 间段内,建立节点能耗矩阵,如下式所示. E = Epp Eps Epr Esp Ess Esr Erp Ers Err . (9) 式中,Emn是由状态 i 转移到状态 j 的能量消耗,若 m = n,则表示节点持续在 m 状态下的能耗. 根据上述能量消耗矩阵 E,可以估计任意给定节 点 i 在 t 时刻总能量消耗,如下式所示: E i total(t) = m移= p,s,rn移= p,s,r Emn . (10) 进而,任意给定节点 i 的剩余能量可表示为: E i remaining(t) = Ea(t) - Etotal(t). (11) 式中,Ea(t) 为上一更新时段 T 结束时刻节点剩余能 ·964·

杨鹏等：能量均衡的间断连接无线网络数据转发策略 ·965· 量，可通过节点信息列表获取. 1.4转发意愿 假定节点的初始能量为Ea,则给定节点i在t时 网络节点均是自私理性的实体，因此，为了提高自 刻的剩余能量占初始能量百分比为： 身对网络的贡献大小以获得其他节点提供给自身的互 _E。aus( 惠帮助，节点应该适当的为其他节点提供转发服务，本 E=- (12) Einid 文首次提出用转发意愿衡量节点为其他节点提供转发 为了衡量节点i在局部范围中的能量水平，则节 服务的概率.历史信息表明，当节点活跃度较高时，则 点i的邻居节点剩余能量均值为： 节点在网络中的重要程度就越高，也具有较高的转发 ∑E.iae(d） 意愿：当自身节点剩余能量百分比较高时，为了提高自 Bieae ieali (13) I NeiL'I 身对网络的贡献，节点同样具有较强的转发意愿；同 式中，NeiL={Nei,Nei,Nei,…,Nei}为节点i的邻 理，当节点历史转发率较高，则节点转发的倾向性也越 居节点集合：I NeiL'I为节点i邻居节点的个数. 大.因此，节点活跃度、剩余能量百分比和转发率是衡 剩余能量能够在一定程度上反映节点的转发服务 量节点转发意愿的三个重要因素 能力，剩余能量充足的节点不会因能量耗尽而丢弃该 节点的转发意愿是节点为其他节点转发数据的概 数据.因此，综合考虑节点的活跃度和剩余能量可以 率大小，由节点自身服务状态决定，用W“={W”, 获得更好的网络性能 W”,…,W}表示.对于任意给定的节点i,其t时刻 1.3数据转发率估计 转发意愿如下式所示 由于网络节点的自私性，节点优先为自身产生的 W”=aAD,+BE,+yPag（t), (17) 数据提供转发服务，然后再为其他节点产生的数据提 a+B+y=1,a≥0，B≥0，y≥0. (18) 供转发服务.节点活跃度在一定程度上能反应出节点 式中，AD:、E:和Pin(t)分别表示节点i的活跃度、 的重要程度和对网络的贡献程度，但不能客观实际地 剩余能量百分比和数据转发率；α，B和y是三个可调 衡量节点的转发服务能力，因此，活跃度高的节点可能 参数 因为剩余能量低，导致其不转发数据，反之，活跃度低 由于节点的活跃度和数据转发率是动态变化的， 的节点也不一定不转发数据.因此，需要综合节点的 而节点的剩余能量变化是严格递减的，一旦三个参数 数据转发率来进一步衡量节点的转发服务能力.数据 中有一个变小，节点的转发意愿就会随之减弱.因此， 转发率与节点的活跃度、剥余能量、网络状况等因素有 本文采用自适应加权法，当节点活跃度比节点剩余能 关，数据转发率越高，节点的转发服务能力就越强，本 量百分比小时，则前者对节点转发意愿影响加大.反 文通过统计节点历史转发信息来计算节点的数据转发 之，影响减小，权重值计算如下： 率.任意给定节点i在T内的数据转发率如下式所示 AD 0= (19) sizefomanel AD:+E+p()' Pforanling(I)= sizeReceived (14) E 式中，Si,e分别表示节点i为其他节点转 B=AD,+E,+P（d）' (20) 发的数据大小和接收的数据大小 Piwanling( (21) 当节点i遇到新节点并为之服务时，设之前的数 y=AD.+E,+P（t) 据转发率为Pan.(t),本次连接的数据转发率为 2能量均衡的数据转发策略 Pding,(t),则数据转发率更新为： Pmaing（t)=P.r(t）+(1-ω)P.(t). 2.1中继节点选择博弈模型 (15) 设计一种高效的合作转发机制，激励节点根据自 式中，0<ω<1为常数，表示本次连接数据转发率的影 身服务状态，适当为其他节点提供转发服务.该机制 响因子，由不同应用场景下所转发数据的重要程度决 考虑到数据的转发依赖于节点间的合作意向，任意两 定.本文采用排序加权法[]来确定该因子的大小，对 个相邻节点之间的数据转发可以看作是一个具有两个 当前所转发数据与历史转发数据进行排序，得到当前 参与者的博弈过程：此外，由于网络固有的拓扑动态变 转发数据的排名r,若到目前为止节点i总转发数据次 化性和节点稀疏性，节点是时刻随机移动的并探测可 数为m,则 能存在的邻居节点，建立通信连接；节点不可能在掌握 0=2m+1-r 了网络中的全部数据信息之后才进行决策，因此，本文 m(m+1) (16) 提出的能量均衡的数据转发策略采用局部信息对网络

杨 鹏等: 能量均衡的间断连接无线网络数据转发策略 量,可通过节点信息列表获取. 假定节点的初始能量为 Einital,则给定节点 i 在 t 时 刻的剩余能量占初始能量百分比为: Ei = E i remaining(t) E i inital . (12) 为了衡量节点 i 在局部范围中的能量水平,则节 点 i 的邻居节点剩余能量均值为: E i average = 移 j屹i,j沂NeiL i E j remaining(t) | NeiL i | . (13) 式中,NeiL i = {Nei i 1 ,Nei i 2 ,Nei i 3 ,…,Nei i n }为节点 i 的邻 居节点集合; | NeiL i | 为节点 i 邻居节点的个数. 剩余能量能够在一定程度上反映节点的转发服务 能力,剩余能量充足的节点不会因能量耗尽而丢弃该 数据. 因此,综合考虑节点的活跃度和剩余能量可以 获得更好的网络性能. 1郾 3 数据转发率估计 由于网络节点的自私性,节点优先为自身产生的 数据提供转发服务,然后再为其他节点产生的数据提 供转发服务. 节点活跃度在一定程度上能反应出节点 的重要程度和对网络的贡献程度,但不能客观实际地 衡量节点的转发服务能力,因此,活跃度高的节点可能 因为剩余能量低,导致其不转发数据,反之,活跃度低 的节点也不一定不转发数据. 因此,需要综合节点的 数据转发率来进一步衡量节点的转发服务能力. 数据 转发率与节点的活跃度、剩余能量、网络状况等因素有 关,数据转发率越高,节点的转发服务能力就越强,本 文通过统计节点历史转发信息来计算节点的数据转发 率. 任意给定节点 i 在 T 内的数据转发率如下式所示. p i forwarding(t) = size i forwarded size i Received . (14) 式中,size i forwarded ,size i Received分别表示节点 i 为其他节点转 发的数据大小和接收的数据大小. 当节点 i 遇到新节点并为之服务时,设之前的数 据转发率为 p i forwarding, ( t),本次连接的数据转发率为 p i forwarding,new (t),则数据转发率更新为: p i forwarding(t) = 棕p i forwarding,new (t) + (1 - 棕)p i forwarding, (t). (15) 式中,0 < 棕 < 1 为常数,表示本次连接数据转发率的影 响因子,由不同应用场景下所转发数据的重要程度决 定. 本文采用排序加权法[18] 来确定该因子的大小,对 当前所转发数据与历史转发数据进行排序,得到当前 转发数据的排名 r,若到目前为止节点 i 总转发数据次 数为 m,则 棕 = 2 m + 1 - r m(m + 1) . (16) 1郾 4 转发意愿 网络节点均是自私理性的实体,因此,为了提高自 身对网络的贡献大小以获得其他节点提供给自身的互 惠帮助,节点应该适当的为其他节点提供转发服务,本 文首次提出用转发意愿衡量节点为其他节点提供转发 服务的概率. 历史信息表明,当节点活跃度较高时,则 节点在网络中的重要程度就越高,也具有较高的转发 意愿;当自身节点剩余能量百分比较高时,为了提高自 身对网络的贡献,节点同样具有较强的转发意愿;同 理,当节点历史转发率较高,则节点转发的倾向性也越 大. 因此,节点活跃度、剩余能量百分比和转发率是衡 量节点转发意愿的三个重要因素. 节点的转发意愿是节点为其他节点转发数据的概 率大小,由节点自身服务状态决定,用 W (t) = { W (t) 1 , W (t) 2 ,…,W (t) n }表示. 对于任意给定的节点 i,其 t 时刻 转发意愿如下式所示. W (t) i = 琢ADi + 茁Ei + 酌p i forwarding(t), (17) 琢 + 茁 + 酌 = 1,琢逸0,茁逸0,酌逸0. (18) 式中,ADi、Ei 和 p i forwarding( t)分别表示节点 i 的活跃度、 剩余能量百分比和数据转发率;琢、茁 和 酌 是三个可调 参数. 由于节点的活跃度和数据转发率是动态变化的, 而节点的剩余能量变化是严格递减的,一旦三个参数 中有一个变小,节点的转发意愿就会随之减弱. 因此, 本文采用自适应加权法,当节点活跃度比节点剩余能 量百分比小时,则前者对节点转发意愿影响加大. 反 之,影响减小,权重值计算如下: 琢 = ADi ADi + Ei + p i forwarding(t) , (19) 茁 = Ei ADi + Ei + p i forwarding(t) , (20) 酌 = p i forwarding(t) ADi + Ei + p i forwarding(t) . (21) 2 能量均衡的数据转发策略 2郾 1 中继节点选择博弈模型 设计一种高效的合作转发机制,激励节点根据自 身服务状态,适当为其他节点提供转发服务. 该机制 考虑到数据的转发依赖于节点间的合作意向,任意两 个相邻节点之间的数据转发可以看作是一个具有两个 参与者的博弈过程;此外,由于网络固有的拓扑动态变 化性和节点稀疏性,节点是时刻随机移动的并探测可 能存在的邻居节点,建立通信连接;节点不可能在掌握 了网络中的全部数据信息之后才进行决策,因此,本文 提出的能量均衡的数据转发策略采用局部信息对网络 ·965·

·966· 工程科学学报，第39卷，第6期 进行建模分析，从网络运行环境中获取信息，还要对其 将式(17)、(22)带入式(24)并结合节点历史信息 他节点的状态和行为动机进行合理地判断，从而选择 便可以求出任意节点i的效用函数 最佳的合作对象 2.2数据转发策略 为了科学合理地选择最佳下一跳中继节点， 根据帕累托最优基本理论，ICWN中的资源最优 EEDFS综合考虑上述参数，对网络进行扩展式动态博 分配问题即上一跳给定节点i与其邻居节点集合Nei- 弈建模分析.根据网络特性作出以下假设：(1)网络 L之间的数据转发服务分配问题，两跳节点之间的一 节点的服务能力具有一定的差异性，随着网络的运行， 次会话是一次博弈过程.表1为一次博弈矩阵. 节点自身转发服务能力也在实时变化；(2)节点初始 表1节点：和j的博弈矩阵 能量不相同：(3)节点所追求自身生存周期和效用均 Table 1 Game matrix of nodes i and j 为最佳：(4)即使活跃节点也有一定的自私性，需要用 状态 转发 不转发 数据转发率客观地衡量节点转发服务概率，剩余能量 转发 (F,F,) (F,-n) 的水平直接决定着节点的转发服务能力 不转发 (-n,F,) (-n,-） 帕累托最优[]是博弈论中解决资源最优分配问 题的一种理想方法，能够保障资源分配过程的相对公 由上述矩阵可知，在节点选择转发时，其收益为对 平和效率.这种最优是资源配置的一种状态，其他任 应的效用函数，反之，节点选择不转发的收益为负.在 何形式的资源配置，均不可能满足使得至少一个节点 选择合作的节点时，虽然为其他节点转发数据会消耗 收益而不致使其他节点利益受损.如前所述，可将IC 一定的资源，但是在转发服务过程中也将获得收益，因 WN中最佳下一跳中继节点的选择看作资源配置问 此，只要收益函数大于代价函数即可；而如果节点选择 题，但是“热点”问题的存在，要求必须高效地配置稀 不合作，则其收益只能为负，所以与选择不合作转发相 缺的网络资源，使得有限的网络资源得到最大地利用. 比，选择合作转发将获得更大的收益 将网络中所有节点看作博弈的有限个参与者，用 经过一次博弈后，一次会话完成一次匹配过程： 集合N={1,2,…,n}表示，节点的策略集空间为S= F:i→NeiL,且NeiL,≠O.如果将单次会话应用到多次 {s,2,…,5.},3={0,1}表示节点i的策略选择，0表 会话中，节点间数据转发过程便可以看作是有限次重 示转发，1表示不转发，且策略选择只能为0或1. 复博弈过程[2如]，经过多次重复博弈，各节点的效用达 s:∈S:是除了i之外所有参与者的策略选择，则任一 到帕累托最优，最终选取最佳下一跳中继节点.通过 策略组合可表示为s=(s,s).参与者i在该策略组 博弈论解决资源分配问题时，并非每个模型都存在帕 合下的效用函数为F:(s,s),由收益函数门：(s,s-) 累托最优，为此，本节中将证明所提EEDFS中存在帕 和代价函数n(s,s)构成. 累托最优，假设N个节点参与的博弈G,每一跳都存在 由于节点的自私性，节点会降低自身能耗以其延 帕累托最优.根据帕累托最优理论可知，节点在最优 长网络生存时间.因此，可以将节点i的代价函数看作 状态时不可能在保证其他节点的收益不减少的情况下 是节点能量损耗和节点生存时间的函数，由于在节点i 使得至少一个节点收益提高.若当前节点i有M个邻 为其他节点提供转发数据服务的过程中，剩余能量直 居节点，则可以构成M个匹配过程，并选取最佳匹配 接决定网络生存时间，所以将给定节点i在策略组合 max(F:,F:),j∈NeiL,具体过程如图1所示 中消耗的剩余能量百分比作为代价函数： W=0.6Ea-2Enne=40一 E(t) W=1/M （d)） (22) E=3 F=0.8×1/M-2/40 E =30 由于节点的转发意愿能够直接体现任意节点i为 W=0.5Eta-2Ee=30 其他节点提供转发服务的可能性，同时可以间接反应 F=0.8x1/M-2/30 其他节点为给定节点i提供转发服务的概率大小.因 此，i的收益函数可定义为： F=0.8x×0.6-3/30 刀：=AW (23) Fm-0.8x0.5-3/30 式中，入>0为调节系数，体现网络整体自私性，与具体 网络环境有关 图1帕累托最优匹配过程 Fig.1 Pareto optimal matching process 进而，任意节点的效用函数可表示为： F:=n:-7=AW-n:. (24) 由表1结果可知，只有在上一跳节点和下一跳节

工程科学学报,第 39 卷,第 6 期 进行建模分析,从网络运行环境中获取信息,还要对其 他节点的状态和行为动机进行合理地判断,从而选择 最佳的合作对象. 为了 科 学 合 理 地 选 择 最 佳 下 一 跳 中 继 节 点, EEDFS综合考虑上述参数,对网络进行扩展式动态博 弈建模分析. 根据网络特性作出以下假设:(1) 网络 节点的服务能力具有一定的差异性,随着网络的运行, 节点自身转发服务能力也在实时变化;(2) 节点初始 能量不相同;(3) 节点所追求自身生存周期和效用均 为最佳;(4) 即使活跃节点也有一定的自私性,需要用 数据转发率客观地衡量节点转发服务概率,剩余能量 的水平直接决定着节点的转发服务能力. 帕累托最优[19] 是博弈论中解决资源最优分配问 题的一种理想方法,能够保障资源分配过程的相对公 平和效率. 这种最优是资源配置的一种状态,其他任 何形式的资源配置,均不可能满足使得至少一个节点 收益而不致使其他节点利益受损. 如前所述,可将 IC鄄 WN 中最佳下一跳中继节点的选择看作资源配置问 题,但是“热点冶问题的存在,要求必须高效地配置稀 缺的网络资源,使得有限的网络资源得到最大地利用. 将网络中所有节点看作博弈的有限个参与者,用 集合 N = {1,2,…,n}表示,节点的策略集空间为 S = {s1 ,s2 ,…,sn },si = {0,1}表示节点 i 的策略选择,0 表 示转发,1 表示不转发,且策略选择只能为 0 或 1. s - i沂S - i是除了 i 之外所有参与者的策略选择,则任一 策略组合可表示为 s = ( si,s - i). 参与者 i 在该策略组 合下的效用函数为 Fi(si,s - i ),由收益函数 浊i ( si,s - i ) 和代价函数 浊 * i (si,s - i)构成. 由于节点的自私性,节点会降低自身能耗以其延 长网络生存时间. 因此,可以将节点 i 的代价函数看作 是节点能量损耗和节点生存时间的函数,由于在节点 i 为其他节点提供转发数据服务的过程中,剩余能量直 接决定网络生存时间,所以将给定节点 i 在策略组合 中消耗的剩余能量百分比作为代价函数: 浊 * i = E i total(t) E i remaining(t) . (22) 由于节点的转发意愿能够直接体现任意节点 i 为 其他节点提供转发服务的可能性,同时可以间接反应 其他节点为给定节点 i 提供转发服务的概率大小. 因 此,i 的收益函数可定义为: 浊i = 姿Wi . (23) 式中,姿 > 0 为调节系数,体现网络整体自私性,与具体 网络环境有关. 进而,任意节点 i 的效用函数可表示为: Fi = 浊i - 浊 * i = 姿Wi - 浊 * i . (24) 将式(17)、(22)带入式(24)并结合节点历史信息 便可以求出任意节点 i 的效用函数. 2郾 2 数据转发策略 根据帕累托最优基本理论,ICWN 中的资源最优 分配问题即上一跳给定节点 i 与其邻居节点集合 Nei鄄 L i 之间的数据转发服务分配问题,两跳节点之间的一 次会话是一次博弈过程. 表 1 为一次博弈矩阵. 表 1 节点 i 和 j 的博弈矩阵 Table 1 Game matrix of nodes i and j 状态 转发 不转发 转发 (Fi,Fj) (Fi, - 浊j) 不转发 ( - 浊i,Fj) ( - 浊i, - 浊j) 由上述矩阵可知,在节点选择转发时,其收益为对 应的效用函数,反之,节点选择不转发的收益为负. 在 选择合作的节点时,虽然为其他节点转发数据会消耗 一定的资源,但是在转发服务过程中也将获得收益,因 此,只要收益函数大于代价函数即可;而如果节点选择 不合作,则其收益只能为负,所以与选择不合作转发相 比,选择合作转发将获得更大的收益. 经过一次博弈后,一次会话完成一次匹配过程: F:i寅NeiLi 且 NeiLi屹芰. 如果将单次会话应用到多次 会话中,节点间数据转发过程便可以看作是有限次重 复博弈过程[20] ,经过多次重复博弈,各节点的效用达 到帕累托最优,最终选取最佳下一跳中继节点. 通过 博弈论解决资源分配问题时,并非每个模型都存在帕 累托最优,为此,本节中将证明所提 EEDFS 中存在帕 累托最优,假设 N 个节点参与的博弈 G,每一跳都存在 帕累托最优. 根据帕累托最优理论可知,节点在最优 状态时不可能在保证其他节点的收益不减少的情况下 使得至少一个节点收益提高. 若当前节点 i 有 M 个邻 居节点,则可以构成 M 个匹配过程,并选取最佳匹配 max(Fi,Fj), j沂NeiL i ,具体过程如图 1 所示. 图 1 帕累托最优匹配过程 Fig. 1 Pareto optimal matching process 由表 1 结果可知,只有在上一跳节点和下一跳节 ·966·