機會網絡中基于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.