改进的基于能量的多播路由算法

李 帅， 蔡 明

(江南大学 物联网工程学院，江苏 无锡214122)

区别于传统有线通信网络，无线自组织网络是一种由大量移动节点组成，具有流动性、自组织、分布式等特点的无线网络，又称Ad hoc 网络［1］。Ad hoc 网络由于布设灵活、简单操作，不受地理位置、环境因素等的限制，被广泛应用于农林、工程、生态等领域。

Ad hoc 网络中，常用的通信方式有两种:多播和单播。多播是指一对多或多对多形式的通信，如单个源节点向多个目的节点传送数据分组。单播是Ad hoc 网络中另一种通信方式，实现一对一形式的通信。多播与单播通信方式相比，数据传送效率高，能够使网络中的资源得到充分有效的利用［2］。

网络的生命周期可以理解为从网络投入运行到废弃使用的时间。一般地，当网络中节点的能量耗尽或者小于某个阈值时，不足以满足信息处理和正常工作的要求，即认为此节点死亡。当网络中死亡节点的数量占到网络中节点总数的某个限定比例时，将认为该网络不再能正常发挥作用，该网络也会被废弃不用。因此，为延长网络的生命周期，使得网络能够更长时间地发挥其作用，降低网络的节点死亡率是一个很有意义的研究方向。

1 相关工作

基于地理位置信息的无线多播路由协议中，GEographic Multicast(GEM［3］)是很典型的一种，其设计灵感源于Euclidean Steiner Tree(EST［4］，欧式Steiner 树)模型。GEM 路由协议中，邻居节点之间可以直接通信。GEM 协议的中心工作是挑选合适的下一转发节点和传输数据，直到将数据传送给所有目的节点。与同类路由协议相比，GEM 协议中节点不需要维护全局或局部路由信息，需要知道节点的位置信息完成路由过程。然而，在其路由算法设计过程中，没有考虑节点的剩余能量。因此，可以改进GEM 路由算法，对所选的节点增加能量约束，以此降低节点死亡率，从而延长应用网络的使用寿命。

文献［5-7］介绍了Ad hoc 网络中常见的基于能量的路由协议。在文献［5］中，提出了一个能量消耗模型。在该模型中，节点状态分为4 种，分别为发送状态、接收状态、空闲状态和休眠状态。节点处于休眠状态时消耗的能量可以忽略不计，能量消耗主要集中在节点收发状态和空闲状态。文献［6］提出的GEAR 中，采用能量感知的启发式路由策略选择地理位置相近的邻居节点来转发分组，并通过发送HELLO 报文获取邻居节点的位置信息和剩余能量值。文献［7］介绍了一种无线传感网中的层次路由协议，协议中根据节点与基站的距离将网络节点划分为不同层次，低层节点数据汇聚后由高层剩余能量较大的节点传送给基站。

基于上述研究，为延长网络的使用寿命，改造GEM 路由算法，对节点的剩余能量加以约束，文中提出一种改进的多播路由算法。算法中系统采用了类似文献［5］中的能量消耗模型，以解决节点在信息传输过程中的能量消耗问题。

2 改进后的多播路由算法EGEM

2.1 系统模型和标记

将网络抽象为一个无向图G = (V，E)，其中V是节点的集合，E 是节点间有效链路的集合。有效链路指此链路为双工类型的链路，双工链路指构成链路的两节点可以同时进行双向信息传输，任一节点既是信息发送方又是信息接收方。假设网络中所有节点具有相似的特征，如节点无线覆盖半径相等，记为R。

将网络中第i 个节点记为vi，同时vi代表节点在网络中的地理位置标识。此网络模型中，节点的位置信息用二维坐标对表示，如vi= (xi，yi)表示节点vi的地理位置坐标。d(vi，vj)表示节点vi和vj之间的欧式距离，在二维直角坐标系中，两点间的欧式距离即两点间的几何距离计算公式如下:

记v 到目的节点集合V(D)的累积距离［4］为cd(v，V(D))，其中V(D)是V 的子集。累积距离计算公式如下:

给定节点v 和w，集合V(D)，V(D)是V 的一个子集，定义节点w 相对于v 到集合V(D)的累积距离为cp(v，w，V(D))，即v 到集合V(D)的累积距离与w 到集合V(D)累积距离的差值，计算公式如下:

用公式3 比较候选节点的优劣程度。在cd(v，V(D))值一定的情况下，cp(v，w，V(D))值越大，cd(w，V(D))的值越小。根据cd(w，V(D))的含义可知，节点w 到目的节点集合V(D)累积距离越小，节点w 越接近目的节点群，这样节点v 通过节点w 到达目的节点群的可能性就越大，w 作为下一中继节点的可能性就越大。

一般地，网络中目的节点的分布不总是集中的，经常会出现孤立节点或节点群的情形。为解决这个问题，在选择下一中继节点的过程中，引入分支的概念。为实现分支，在选择下一中继节点时，考虑了所有可能的节点对并挑选出最佳的一对，与不引入分支情况下选择的节点作比较。在引入分支的情况下，衡量节点作为候选节点的优劣程度时，公式3 不能很好地满足这种需求。

为满足此需求，引入参数ap(v，w，V(D))，用来比较引入分支时节点作为下一中继节点的优劣程度，计算公式如下:

其中| V(D)| 表示集合V(D)包含节点的个数。这样，在使用公式4 的方法比较优劣程度值时，孤立的目的节点或目的节点群在下一中继节点选择的过程中所占的权值越大，这样使得在靠近源点处分支的可能性更大，一定程度上减少了到孤立目的节点或目的节点群的跳数，从而减少了开销。

2.2 选择转发方向

假设当前转发节点为vi，负责将数据分组转发到目的节点集合V(D)。假设节点vi知道V(D)中目的节点的地理位置信息，对于节点位置信息的更新和维护策略参阅文献［8］。

要解决的重要问题之一是如何挑选合适的下一转发节点。在选择过程中，还要考虑是否引入分支的问题。在选择转发方向时，每一个当前中继节点均要考虑是否在本节点处引入分支。这一步很重要，因为在合适的位置分支将减少当前转发节点到目的节点或节点群的中间节点的数目，从而减少开销。另外，基于EST 的理论研究还表明，引入分支的数目最多不超过2 个。下面分步详细介绍其选择流程。

1)假设vj为节点vi无线覆盖范围内的节点，即节点vi的邻居节点。由于vi的邻居节点能直接接收来自节点vi的所有消息，因此首先要从V(D)中移除所有在其无线传输范围内的目的节点。

2)不分支情形下，求取使得ap(vi，vθ，V(D))取得最大值的转发方向角θ0。节点无线覆盖半径为R，则以节点vi为圆心、R 为半径的圆周上任一点坐标可表示为

选取最佳转发方向时，选取使得ap(vi，vθ，V(D))取最大值对应的θ 值，求解公式如下:

其中θ 为节点vi，vθ连线与x 轴所成夹角。为计算方便，选取θ = μ* Δθ，μ = 0，1，2，…，μmax。Δθ 称为搜索粒度，计算表达式为Δθ = ［2π/μmax］。可以看出，Δθ 越大，θ 值取值个数就越少，很大程度上能减少计算负担。

3)分支情况下，计算ap(vi，vθ，V(D))最大值之和与对应的方向对(θ1，θ2)。ap(vi，vθ，V(D))值的计算过程与2)相似，不同之处有3 点。首先，在计算前，要将目的节点集合V(D)划分。其中，V(D1)表示相对于vi节点、分布靠近θ1的目的节点集合。同样的，V(D2)表示相对于vi节点、分布靠近θ2的目的节点集合。V(D1)和V(D2)存在如下关系:V(D1)= V(D)－V(D2)。其次，在选择转发方向对(θ1，θ2)时，从［0，2π］* ［0，2π］区间内选取，为减少计算负担，令θ2=θ1+2π/3，这样只需比较μmax个方向对。最后，在两转发方向计算出相应ap(vi，vθ，V(D))值后，求和，记为sap(vi，vθ，V(D))。

4)比较ap(vi，vθ，V(D))和sap(vi，vθ，V(D))的大小并判定在当前中继节点vi处是否分支。若ap(vi，vθ，V(D))大于等于sap(vi，vθ，V(D))，不分支，否则分支。

2.3 选择下一转发节点

确定转发方向后，当前转发节点在其无线覆盖范围内广播消息，并选出最佳下一转发节点。此阶段，节点vi产生一个控制消息Request_Forward，并广播给其无线覆盖范围内的所有邻居节点。这个控制消息包含转发方向值、vi及目的节点对应的标识和位置信息、分支标识FLAG。其中，若不引入分支，置FLAG = 0，否则，置FLAG = 1。

记t0为vi发送Request_Forward 消息的时刻，此刻起，vi节点的邻居节点开始下一中继节点的竞争。假设vj是无线传输范围中任一节点，即vi的邻居节点。当vj接收到Request_Forward 消息后，会将此消息存储在本地内存中。首先，vj会读取控制消息中FLAG 的值，并根据FLAG 的不同值执行不同的操作。但无论FLAG 取值如何，都需引入一个参数，用来衡量vj沿转发方向θ 作为下一中继节点的好坏程度，此参数标记为μ(vj，vi，θ*)，表示vj，vi连线在某一方向θ*上的投影值，如图1 所示。计算公式如下:

其中，d(vj，vi)是节点vi和vj之间的欧式距离，θ 为vi，vj两节点连线与x 轴所成夹角(见图1)。θ 计算公式如下:

图1 中继节点选择Fig.1 Graph of the relay node selection

从式7 中可以看出，θ 与转发方向角θ*偏离程度越小，μ(vj，vi，θ*)值越大，节点vj距离目的集合就相对越近，节点vi沿θ 方向转发数据分组的概率越大。

以FLAG = 0 为例说明vj执行的操作。FLAG =0，令θ*= θ0，计算μ(vj，vi，θ0)。然后vj会依据一个指数分布函数产生一个随机值ζj，这个函数以μ(vj，vi，θ0)为参数，且μ(vj，vi，θ0)值越大，ζj值越小。vj在(t0+ζj)时刻发送一个Reply_Forward 消息，内容包括分支标识FLAG、转发方向值θ0、转发方向对应的μ(vj，vi，θ0)，vj的标识、位置和节点的剩余能量e。很 明 显，μ(vj，vi，θ0) 值 越 大，vj就 越 早 发 送Reply_Forward 消息。针对FLAG = 1，要计算μ(vj，vi，θ1)和μ(vj，vi，θ2)两个值并比较，vj会根据μ(vj，vi，θ*)值较大者产生随机值ζj。

在时刻t0发送Request_Forward 消息后，节点vi会等待一段时间，这段时间用来接收来自其邻居节点发回的Reply_Forward 消息。vi节点在发送Request_Forward 消息后，也会产生一条记录，称为最佳记录，同时产生一条备用记录，记录包含下述信息:分支标识FLAG;转发方向值θ0，θ1，θ2;沿对应转发方向的射影μ0，μ1，μ2;取相应射影节点的标识v0，v1，v2;剩余能量值e。

vi收到一个Reply_Forward 消息后，会将所需的信息插入到此记录的相应位置。插入时注意，若FLAG = 0，θ1，θ2，μ1，μ2，v1，v2置为空，对应地，若FLAG = 1，θ0，μ0，v0也置空。需要说明一下，节点vi产生的最佳记录用来存放最优解，备用记录用来存放次优解。最优解是指μ 值较大，同时剩余能量值e满足能量约束e_need 的解;次优解是指满足约束条件，但μ 值较小或其他情况。节点vi收到Reply_Forward 信息的过程中，不断更新最佳记录和备用记录中的信息。

在TEND时，vi停止接收Reply_Forward 信息。此时节点vi会检查最佳记录中是否有节点信息，如果没有则到备用记录中查询节点信息，并将此节点作为下一中继节点。

筛选出下一中继节点后，当前中继节点vi会在其无线传输范围内以广播的方式发送一个CT 消息结束选择过程。该CT 消息包括下一中继节点的标识和位置信息、数据分组信息。节点vj接收到此CT消息后，读取此消息内容并判断是否被选为下一中继节点。如果是，vj将接收包含在CT 消息中的数据分组，转发该数据分组的副本并开始新一轮的竞争选择，否则vj忽略此数据分组。当vi监听到下一中继节点转发数据分组后，会将最佳记录和备用记录删除。

3 实 验

实验以eclipse 软件为工具，以50* 100 m2的矩形作为实验区域，节点均匀散落在此区域中，每个节点的无线传输半径R = 10 m。源节点和目的节点的位置信息用二维坐标对表示，实验过程中预设目的节点数量10 个。节点密度定义为节点数量与仿真场景面积的比值，记为σ，分别取σ1= 0.03 m－2，σ2=0.04 m－2。节点能量初始化为10 J，能量阈值为2 J，发送状态下能量消耗1.4 J，接收和空闲状态下能量消耗均为0.8 J［9］。实验中，考察改进前后算法在不同实验次数下节点的死亡率和平均跳数等性能参数。

定义节点死亡率为网络中能量耗尽的节点数目与节点总数的比值，平均跳数为路由选择过程中经历的总跳数与实验次数的比值。通常情况下，网络中节点死亡率越高，不能发挥正常作用的节点数目越多，对应网络的使用寿命越短，节点死亡率超过某个限值网络将会被废弃使用。表1，2 中分别表示σ1= 0.03 m－2，σ2= 0.04 m－2时不同实验次数下节点的死亡率及其他性能参数。

表1 σ1 下性能参数结果Tab.1 Results of performance parameters under σ1

表2 σ2 下性能参数结果Tab.2 Results of performance parameters under σ2

从表1，2 中可以看出，随着实验次数的增加，两者的节点死亡率基本呈增加趋势;相同实验次数下EGEM 的节点死亡率明显小于GEM 对应的节点死亡率，但平均跳数保持不变或增加。原因在于，在选择下一转发节点过程中，GEM 总是选择μ(vj，vi，θ*)值最大的节点作为下一转发节点，保证了跳数最少，但是未考虑节点的剩余能量，在多次传输之后，节点能量耗尽导致节点死亡。而EGEM 在选择下一转发节点时，总是选择剩余能量较多者进行转发，在相同实验次数下对应的节点死亡率较小。但由于EGEM 挑选的节点对应的μ(vj，vi，θ*)值并不一定保证最大，导致路由过程中平均跳数不变或增加。

4 结 语

文中研究了Ad Hoc 网络中几种常见的基于能量的无线路由协议，提出了一种改进的提供能量约束的多播路由算法。与原算法相比，新算法中引入了能量消耗模型。新算法对节点剩余能量加以约束，选择剩余能量较多的节点进行数据传输，一定程度上降低了节点死亡率，延长了网络的使用寿命。由于在数据传送过程中节点需要知道目的节点的地理位置信息，会导致消息头部开销增加，下一步将集中在降低开销上。

［1］闫丽丽，彭代渊，高悦翔. Ad hoc 网络中认证路由协议的改进及其安全性分析［J］. 电子科技大学学报，2011，40(4):578-581.YAN Lili，PENG Daiyuan，GAO Yuexiang.An improved routing protocol in ad hoc networks with safety analysis［J］. Journal of University of Electronic Science and Technology，2011，40(4):578-581.(in Chinese)

［2］李群.Ad hoc 网络多播路由协议研究进展分析［J］.计算机技术与发展，2014，24(2):187-188.LI Qun.Research and analysis of multicast routing protocol in ad hoc networks［J］. Computer Technology and Development，2014，24(2):187-188.(in Chinese)

［3］Galluccio L，Morabito G，Palazzo S. GEographic Multicast for dense wireless networks:protocol and performance analysis［J］.IEEE/ACM，2012，4(21):1332-1346.

［4］Herring M.The euclidean steiner tree problem［R］.Granville:Denison University，2004.

［5］陈祖爵，欧阳烨龙.一种层次蜂窝结构的负载均衡GAF 算法［J］.计算机工程，2012，38(3):105-118.CHEN Zujue，OUYANG Hualong. The load balancing GAF algorithm based on hierarchical cellular structure［J］. Computer Engineer，2012，38(3):105-118.(in Chinese)

［6］魏斌，王维先.基于模糊区域宽松距离的改进GEAR 传感网络均衡算法［J］.计算机科学，2012，39(9):71-73.WEI Bin，WANG Weixian. The improved GEAR sensor network balancing algorithm based on relaxed distance in fuzzy region［J］.Computer Science，2012，39(9):71-73.(in Chinese)

［7］康一梅，赵磊，胡江.基于能量感知的无线传感器网络层次型路由协议［J］.计算机工程与设计，2011，32(12):3948-3956.KANG Yimei，ZHAO Lei，HU Jiang.An hierarchical routing protocol in sensor networks based on energy awareness［J］.Computer Engineer and Design，2011，32(12):3948-3956.(in Chinese)

［8］林彦汝，周继鹏.基于地理位置的Ad Hoc 路由协议［J］.计算机应用，2011，31(1):226-228.LIN Yanru，ZHOU Jipeng.The routing protocol based on geographic information in ad hoc networks［J］.Computer Application，2011，31(1):226-228.(in Chinese)

［9］叶海滨，张华熊，马汉杰.基于NS2 的能量模型的研究［J］.工业控制计算机，2013，26(1):77-79.YE Haibin，ZHANG Huaxiong，MA Hanjie.The survery of energy model bases on NS2［J］.Industrial Control Computer，2013，26(1):77-79.(in Chinese)