机会网络中基于Ferry的低能耗路由算法

雷宏江，刘彩梅，高 潮，任 智

(1.重庆邮电大学 移动通信技术重庆市重点实验室，重庆400065;2.重庆大学 光电技术及系统教育部重点实验室，重庆400044)

由于网络节点的连通性差，消息传递需要被动地等待节点随机移动带来的通信机会，节点的连接性难以预测，因而传统的Internet路由算法(如RIP［2］，OSPF［3］)和MANET路由算法(如AODV［4］)不适用于机会网络［1］。在目前适用于机会网络的被动式路由协议(如Epidemic路由协议［5］)中，节点依靠本身的移动来建立路由，节点随机移动时，相遇的机会是不可预测的以为了提高传输率，降低时延，普通节点选择在网络中大量复制以传播消息，这使得网络间节点间缓存以及能量消耗剧增。

为了缓解节点的能耗，降低网络的时延，克服在长时间高度隔断网络中的通信间断，基于主动运动的路由协议(如消息摆渡机制路由协议［6］)中引进了一种非随机移动的特殊节点——Ferry节点。Ferry利用高速主动运动的能力使断裂的网络连接起来，以“存储—携带—转发”的方式协助网络传输消息，在消息的传输过程中充当渡船的角色。路由分两种形式，分别为node主动靠近Ferry进行通信(node必须具备主动运动的能力)和Ferry主动靠近node进行数据交互。

自从基于消息摆渡的机会网络路由方法被提出以后，人们对其加以改进和拓展的研究一直在进行，在主动运动节点的选择、Ferry节点主动运动路径的设计和优化等方面已取得一定进展［7-10］。但通过研究发现，现有的基于消息摆渡的机会网络路由方法在控制消息(如Hello消息和服务请求消息)的传输方面存在冗余的通信和存储开销，而且Ferry节点主动运动路线也仍然有不够优化的地方，这些问题对采用消息摆渡机制的机会网络路由方法的性能具有重要影响。

1 FIMF网络模型及存在问题

1.1 FIMF网络模型

本文所采用的FIMF网络模型如图1所示，网络区域大小为一个D×D的正方形，把网络平均分成4个正方形小栅格，Ferry节点的固定路径即由每个小栅格的中心为顶点的正方形L，设R为长距离通信半径，则当R 取不小于/4的某一定值时，Ferry节点在封闭的路线L上移动一周，其通信范围能够覆盖全网。

图1 FIMF路由协议工作原理

网络初始时Ferry节点沿着预先设置好的路径移动，并通过大功率通信方式周期性地广播包含当前自身位置信息的Hello消息。当普通节点S接收到Ferry节点广播的Hello消息时，提取该Hello消息中的位置信息计算其本身与Ferry节点的距离d，若d＜Rth(这里Rth＜R)，且节点控制机制［7］判定满足通知Ferry节点主动运动靠近进行通信的条件时，S会以大功率通信方式发送一个服务请求(Service_Request)的消息(包含节点当前位置)给Ferry节点(为了确保Service_Request的成功传送，这里取Rth＜R)，如图1a所示。一旦Ferry节点接收到S的服务请求消息，Ferry节点会依据消息里面节点S的坐标消息改变自己的移动路线与节点S相遇。节点本身的控制机制会适时地以大功率通信方式向Ferry节点发送位置更新(Location_Update)消息，如图1b所示。当普通节点和Ferry节点相遇时(进入双方的短距离通信范围，通信半径为r)，普通节点和Ferry节点就会以正常通信方式开始交换消息，如图1c所示。当Ferry节点和普通节点之间数据交互完毕时，Ferry节点会返回原来的路由路径，如图1d所示。任何时候只要Ferry节点与普通节点进入对方的短距离通信范围则进行数据交互。

1.2 存在问题

FIMF路由方案中存在以下问题:

1)普通节点上会发生以下3种事件，设事件A为节点物理层检测到来自其他节点的信号;事件B为节点缓存中有数据待发送;事件C为发送Hello消息。事件A，B，C是相互独立的，并且节点可以自主控制事件C的发生。原FIMF方案节点周期性地广播Hello消息，仔细研究不难发现，当事件A与事件B同时不发生时，事件C的发生对数据传输不起作用。

2)普通节点都是以单一的大功率无线电发送服务请求消息与位置更新消息给Ferry节点，由于该动作发生在接收到Ferry节点的Hello消息后，因此这些节点当前与Ferry的距离d最多为R。通常通信半径为d的传输功率与dm(m＞1，为路径损耗系数)成正比。因此当d小于Rth时，普通节点可以成指数倍地降低发射功率发送控制消息，节能效果是显然的。

2 改进的FIMF方案

RSSI的测距技术不需要增加额外装置和额外能量消耗，相对来说成本及复杂度低，普遍应用于各种无线多跳网络中。本文采用基于RSSI测距技术，提出改进的FIMF方案(AFIMF方案)来解决以上问题。AFIMF方案包含以下两种改进机制。

1)普通节点基于跨层信息共享方式按需广播Hello消息。

在该机制中，当且仅当事件A或者事件B至少有一个发生时，发生事件C。这样可以减少节点发送Hello包的次数，降低网络通信的控制开销，节约节点能量。证明如下:

所以本机制的改进方法是可行的，并且能达到预期的有益效果。

2)普通节点基于RSSI技术自适应地调整功率发送服务请求消息与位置更新消息。

本机制在普通节点MAC层采用RSSI测距技术保存最新接收到的Ferry—Hello消息的距离，当MAC层需要发送来自路由层的发送服务请求消息与位置更新消息时，根据该距离自适应地调节合适最小发射功率。这样可以整体降低节点发射服务请求消息与位置更新消息的功率，节约节点能量。证明如下:

以Ferry当前的位置为中心，设此时需要发送服务请求消息或者位置消息的任一节点与Ferry的距离为x(其中0＜x≤R)，将距离R分成个子区间，其中第i(1≤i≤k-1)个子区间为((i-1)r，ir］，第k个子区间为((k-1)r，R］;每个子区间对应一个合适的最小发射功率Pi;设y表示x落在第i(1≤i≤k)个子区间，其中是一个随机变量，因而对应发射功率P也是一个随机变量，y和P的分布律如表1所示(p为对应的概率)。

表1 y与P的分布律

因此在相同网络条件下，采用本机制能够减少节点的能量消耗。

3 仿真结果及其分析

将采用本文提出的3种改进机制的FIMF路由算法称为AFIMF，并使用OPNET仿真软件分别对AFIMF与FIMF路由方案进行性能仿真分析。

3.1 仿真设置

本文对N(N=40，60，80，100，120)个节点随机分布在网络中，一个Ferry的5个场景进行仿真，每个场景采用相同的网络设置。场景大小为5 000 m×5 000 m。随机选择场景中40%的节点产生数据，随机选择网络中的其他节点作为数据目的地。源节点消息产生率服从泊松分布，消息超时值为3 000 s，节点移动模式为随机路点模型，节点最大的移动速率为5 m/s。Ferry的移动速率为20 m/s，Ferry固定路径为以位置(1 250，1 250)和位置(3 750，3 750)为对角顶点的矩形，其他参数设置如表2所示。

表2 参数列表

3.2 性能分析

1)消息传递成功率:消息传递成功率是成功接收到的数据分组总比特数与发送数据分组的总比特数的比值，用来表征算法在运行过程中消息传递的成功率。图2表明不同的网络场景在相同网络条件下，改进算法AFIMF与原FIMF消息传递率持衡，AFIMF有良好的稳定性。

图2 消息传递成功率

2)控制开销:控制开销是指控制分组的总比特数与发送数据分组的总比特数的比值，用来说明每发送一个数据分组，需要发送控制分组的比特数。图3表明在相同网络条件下，采用AFIMF算法的控制开销均比FIMF低;这主要因为在AFIMF中，普通节点基于跨层信息共享方式按需广播的Hello消息。由图2知两种算法消息传递成功率持衡，AFIMF较FIMF在不影响网络消息传递的性能下，消耗更少的控制开销。

图3 网络控制开销

3)Hello包发送的总个数:统计网络中所有节点在网络运行期间发送的Hello包个数。图4表明在相同网络条件下，采用AFIMF算法的Hello包发送的次数均比FIMF少;这是因为在AFIMF中，普通节点基于跨层信息共享方式按需地广播Hello消息。由图2知两种算法消息传递率持衡，因此在不影响网络消息传递性能的前提下，AFIMF较FIMF，节点发送的Hello消息更少，减少了节点的通信开销。

图4 Hello包发送的总个数

4)总能量消耗:网络中所有节点发送和接收消息(包括数据分组和控制消息)总消耗的能量。图5表明，采用AFIMF算法的总能量消耗均比FIMF少;这主要因为AFIMF采用普通节点基于RSSI技术自适应地调整功率发送服务请求消息与位置更新消息机制，降低了发射控制消息的功率期望值，另外，使用其他两种机制节约了网络开销，进而节约了能量。由图2知两种算法消息传递率持衡，因此在不影响网络消息传递性能的前提下，AFIMF较FIMF，节点消耗的能量更少，增强了路由算法的健壮性。

图5 总能量消耗

4 结论

机会网络中的FIMF路由机制中，普通节点在传递控制消息(如节点位置消息、Hello消息)时存在多余的通信开销，并且采用了大功率发送位置消息会耗费过多能量。本文提出了FIMF的改进路由算法AFIMF，该算法降低了节点长距离无线电发送控制消息的功率，减少了node发送Hello消息的次数。仿真结果表明，AFIMF在保证消息传递成功率不低于FIMF方案的前提下，能减小网络的总能量消耗、控制开销和节点Hello消息的次数。

［1］LILIEN L，KAMAL Z H，GUPTA A.Opportunistic networks［R］.Kalamazoo:Department of Computer Science Western Michigan University，2006.

［2］RFC 1058，Routing information protocol［S］.1988.

［3］SIDHU D，FU T，ABDALLAH S，et al.Open shortest path first(OSPF)routing protocol simulation［J］.Computer Communication Review，1993，23(4):53-62.

［4］PERKINS C E，ROYER E M.Ad-hoc on-demand distance vector routing［C］//Proc.Ninety-ninth Mobile Computing Systems and Applications.［S.l.］:IEEE Press，1999:90-100.

［5］VAHDAT A，BECKE D.Epidemic routing for partially connected Ad Hoc networks［R］.Durham:Department of Computer Science in Duke University，2000.

［6］ZHAO W R，AMMAR M.Message ferrying:proactive routing in highly-partitioned wireless Ad Hoc networks［C］//Proc.Ninth IEEE Workshop on Future Trends of Distributed Computing Systems.［S.l.］:IEEE Press，2003:308-314.

［7］ZHAO W R，AMMAR M，ZEGURA E.A message ferrying approach for data delivery in sparse mobile Ad Hoc networks［C］//Proc.Fifth ACM International Symp Mobile Ad Hoc Networking and Computing.［S.l.］:IEEE Press，2004:187-198.

［8］章韵，魏鹏，王汝传，等.DTN网络中ferry节点的MSSL路由算法研究［J］.计算机技术与发展，2009，19(5):107-110.

［9］POLAT B K，SACHDEVA P，AMMAR M H.Message ferries as generalized dominating sets intermittently connected mobile networks［J］.Pervasive and Mobile Computing，2011，7(2):189-205.

［10］WANG T，LOW C P.Dynamic message ferry route(DMFR)for partitioned MANETs［C］//Proc.International Conference on Communications and Mobile Computing.［S.l.］:IEEE Press，2010:447-451.