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

(1.重慶郵電大學 移動通信技術(shù)重慶市重點實驗室，重慶400065;2.重慶大學 光電技術(shù)及系統(tǒng)教育部重點實驗室，重慶400044)

由于網(wǎng)絡節(jié)點的連通性差，消息傳遞需要被動地等待節(jié)點隨機移動帶來的通信機會，節(jié)點的連接性難以預測，因而傳統(tǒng)的Internet路由算法(如RIP［2］，OSPF［3］)和MANET路由算法(如AODV［4］)不適用于機會網(wǎng)絡［1］。在目前適用于機會網(wǎng)絡的被動式路由協(xié)議(如Epidemic路由協(xié)議［5］)中，節(jié)點依靠本身的移動來建立路由，節(jié)點隨機移動時，相遇的機會是不可預測的以為了提高傳輸率，降低時延，普通節(jié)點選擇在網(wǎng)絡中大量復制以傳播消息，這使得網(wǎng)絡間節(jié)點間緩存以及能量消耗劇增。

為了緩解節(jié)點的能耗，降低網(wǎng)絡的時延，克服在長時間高度隔斷網(wǎng)絡中的通信間斷，基于主動運動的路由協(xié)議(如消息擺渡機制路由協(xié)議［6］)中引進了一種非隨機移動的特殊節(jié)點——Ferry節(jié)點。Ferry利用高速主動運動的能力使斷裂的網(wǎng)絡連接起來，以“存儲—攜帶—轉(zhuǎn)發(fā)”的方式協(xié)助網(wǎng)絡傳輸消息，在消息的傳輸過程中充當渡船的角色。路由分兩種形式，分別為node主動靠近Ferry進行通信(node必須具備主動運動的能力)和Ferry主動靠近node進行數(shù)據(jù)交互。

自從基于消息擺渡的機會網(wǎng)絡路由方法被提出以后，人們對其加以改進和拓展的研究一直在進行，在主動運動節(jié)點的選擇、Ferry節(jié)點主動運動路徑的設(shè)計和優(yōu)化等方面已取得一定進展［7-10］。但通過研究發(fā)現(xiàn)，現(xiàn)有的基于消息擺渡的機會網(wǎng)絡路由方法在控制消息(如Hello消息和服務請求消息)的傳輸方面存在冗余的通信和存儲開銷，而且Ferry節(jié)點主動運動路線也仍然有不夠優(yōu)化的地方，這些問題對采用消息擺渡機制的機會網(wǎng)絡路由方法的性能具有重要影響。

1 FIMF網(wǎng)絡模型及存在問題

1.1 FIMF網(wǎng)絡模型

本文所采用的FIMF網(wǎng)絡模型如圖1所示，網(wǎng)絡區(qū)域大小為一個D×D的正方形，把網(wǎng)絡平均分成4個正方形小柵格，F(xiàn)erry節(jié)點的固定路徑即由每個小柵格的中心為頂點的正方形L，設(shè)R為長距離通信半徑，則當R 取不小于/4的某一定值時，F(xiàn)erry節(jié)點在封閉的路線L上移動一周，其通信范圍能夠覆蓋全網(wǎng)。

圖1 FIMF路由協(xié)議工作原理

網(wǎng)絡初始時Ferry節(jié)點沿著預先設(shè)置好的路徑移動，并通過大功率通信方式周期性地廣播包含當前自身位置信息的Hello消息。當普通節(jié)點S接收到Ferry節(jié)點廣播的Hello消息時，提取該Hello消息中的位置信息計算其本身與Ferry節(jié)點的距離d，若d＜Rth(這里Rth＜R)，且節(jié)點控制機制［7］判定滿足通知Ferry節(jié)點主動運動靠近進行通信的條件時，S會以大功率通信方式發(fā)送一個服務請求(Service_Request)的消息(包含節(jié)點當前位置)給Ferry節(jié)點(為了確保Service_Request的成功傳送，這里取Rth＜R)，如圖1a所示。一旦Ferry節(jié)點接收到S的服務請求消息，F(xiàn)erry節(jié)點會依據(jù)消息里面節(jié)點S的坐標消息改變自己的移動路線與節(jié)點S相遇。節(jié)點本身的控制機制會適時地以大功率通信方式向Ferry節(jié)點發(fā)送位置更新(Location_Update)消息，如圖1b所示。當普通節(jié)點和Ferry節(jié)點相遇時(進入雙方的短距離通信范圍，通信半徑為r)，普通節(jié)點和Ferry節(jié)點就會以正常通信方式開始交換消息，如圖1c所示。當Ferry節(jié)點和普通節(jié)點之間數(shù)據(jù)交互完畢時，F(xiàn)erry節(jié)點會返回原來的路由路徑，如圖1d所示。任何時候只要Ferry節(jié)點與普通節(jié)點進入對方的短距離通信范圍則進行數(shù)據(jù)交互。

1.2 存在問題

FIMF路由方案中存在以下問題:

1)普通節(jié)點上會發(fā)生以下3種事件，設(shè)事件A為節(jié)點物理層檢測到來自其他節(jié)點的信號;事件B為節(jié)點緩存中有數(shù)據(jù)待發(fā)送;事件C為發(fā)送Hello消息。事件A，B，C是相互獨立的，并且節(jié)點可以自主控制事件C的發(fā)生。原FIMF方案節(jié)點周期性地廣播Hello消息，仔細研究不難發(fā)現(xiàn)，當事件A與事件B同時不發(fā)生時，事件C的發(fā)生對數(shù)據(jù)傳輸不起作用。

2)普通節(jié)點都是以單一的大功率無線電發(fā)送服務請求消息與位置更新消息給Ferry節(jié)點，由于該動作發(fā)生在接收到Ferry節(jié)點的Hello消息后，因此這些節(jié)點當前與Ferry的距離d最多為R。通常通信半徑為d的傳輸功率與dm(m＞1，為路徑損耗系數(shù))成正比。因此當d小于Rth時，普通節(jié)點可以成指數(shù)倍地降低發(fā)射功率發(fā)送控制消息，節(jié)能效果是顯然的。

2 改進的FIMF方案

RSSI的測距技術(shù)不需要增加額外裝置和額外能量消耗，相對來說成本及復雜度低，普遍應用于各種無線多跳網(wǎng)絡中。本文采用基于RSSI測距技術(shù)，提出改進的FIMF方案(AFIMF方案)來解決以上問題。AFIMF方案包含以下兩種改進機制。

1)普通節(jié)點基于跨層信息共享方式按需廣播Hello消息。

在該機制中，當且僅當事件A或者事件B至少有一個發(fā)生時，發(fā)生事件C。這樣可以減少節(jié)點發(fā)送Hello包的次數(shù)，降低網(wǎng)絡通信的控制開銷，節(jié)約節(jié)點能量。證明如下:

所以本機制的改進方法是可行的，并且能達到預期的有益效果。

2)普通節(jié)點基于RSSI技術(shù)自適應地調(diào)整功率發(fā)送服務請求消息與位置更新消息。

本機制在普通節(jié)點MAC層采用RSSI測距技術(shù)保存最新接收到的Ferry—Hello消息的距離，當MAC層需要發(fā)送來自路由層的發(fā)送服務請求消息與位置更新消息時，根據(jù)該距離自適應地調(diào)節(jié)合適最小發(fā)射功率。這樣可以整體降低節(jié)點發(fā)射服務請求消息與位置更新消息的功率，節(jié)約節(jié)點能量。證明如下:

以Ferry當前的位置為中心，設(shè)此時需要發(fā)送服務請求消息或者位置消息的任一節(jié)點與Ferry的距離為x(其中0＜x≤R)，將距離R分成個子區(qū)間，其中第i(1≤i≤k-1)個子區(qū)間為((i-1)r，ir］，第k個子區(qū)間為((k-1)r，R］;每個子區(qū)間對應一個合適的最小發(fā)射功率Pi;設(shè)y表示x落在第i(1≤i≤k)個子區(qū)間，其中是一個隨機變量，因而對應發(fā)射功率P也是一個隨機變量，y和P的分布律如表1所示(p為對應的概率)。

表1 y與P的分布律

因此在相同網(wǎng)絡條件下，采用本機制能夠減少節(jié)點的能量消耗。

3 仿真結(jié)果及其分析

將采用本文提出的3種改進機制的FIMF路由算法稱為AFIMF，并使用OPNET仿真軟件分別對AFIMF與FIMF路由方案進行性能仿真分析。

3.1 仿真設(shè)置

本文對N(N=40，60，80，100，120)個節(jié)點隨機分布在網(wǎng)絡中，一個Ferry的5個場景進行仿真，每個場景采用相同的網(wǎng)絡設(shè)置。場景大小為5 000 m×5 000 m。隨機選擇場景中40%的節(jié)點產(chǎn)生數(shù)據(jù)，隨機選擇網(wǎng)絡中的其他節(jié)點作為數(shù)據(jù)目的地。源節(jié)點消息產(chǎn)生率服從泊松分布，消息超時值為3 000 s，節(jié)點移動模式為隨機路點模型，節(jié)點最大的移動速率為5 m/s。Ferry的移動速率為20 m/s，F(xiàn)erry固定路徑為以位置(1 250，1 250)和位置(3 750，3 750)為對角頂點的矩形，其他參數(shù)設(shè)置如表2所示。

表2 參數(shù)列表

3.2 性能分析

1)消息傳遞成功率:消息傳遞成功率是成功接收到的數(shù)據(jù)分組總比特數(shù)與發(fā)送數(shù)據(jù)分組的總比特數(shù)的比值，用來表征算法在運行過程中消息傳遞的成功率。圖2表明不同的網(wǎng)絡場景在相同網(wǎng)絡條件下，改進算法AFIMF與原FIMF消息傳遞率持衡，AFIMF有良好的穩(wěn)定性。

圖2 消息傳遞成功率

2)控制開銷:控制開銷是指控制分組的總比特數(shù)與發(fā)送數(shù)據(jù)分組的總比特數(shù)的比值，用來說明每發(fā)送一個數(shù)據(jù)分組，需要發(fā)送控制分組的比特數(shù)。圖3表明在相同網(wǎng)絡條件下，采用AFIMF算法的控制開銷均比FIMF低;這主要因為在AFIMF中，普通節(jié)點基于跨層信息共享方式按需廣播的Hello消息。由圖2知兩種算法消息傳遞成功率持衡，AFIMF較FIMF在不影響網(wǎng)絡消息傳遞的性能下，消耗更少的控制開銷。

圖3 網(wǎng)絡控制開銷

3)Hello包發(fā)送的總個數(shù):統(tǒng)計網(wǎng)絡中所有節(jié)點在網(wǎng)絡運行期間發(fā)送的Hello包個數(shù)。圖4表明在相同網(wǎng)絡條件下，采用AFIMF算法的Hello包發(fā)送的次數(shù)均比FIMF少;這是因為在AFIMF中，普通節(jié)點基于跨層信息共享方式按需地廣播Hello消息。由圖2知兩種算法消息傳遞率持衡，因此在不影響網(wǎng)絡消息傳遞性能的前提下，AFIMF較FIMF，節(jié)點發(fā)送的Hello消息更少，減少了節(jié)點的通信開銷。

圖4 Hello包發(fā)送的總個數(shù)

4)總能量消耗:網(wǎng)絡中所有節(jié)點發(fā)送和接收消息(包括數(shù)據(jù)分組和控制消息)總消耗的能量。圖5表明，采用AFIMF算法的總能量消耗均比FIMF少;這主要因為AFIMF采用普通節(jié)點基于RSSI技術(shù)自適應地調(diào)整功率發(fā)送服務請求消息與位置更新消息機制，降低了發(fā)射控制消息的功率期望值，另外，使用其他兩種機制節(jié)約了網(wǎng)絡開銷，進而節(jié)約了能量。由圖2知兩種算法消息傳遞率持衡，因此在不影響網(wǎng)絡消息傳遞性能的前提下，AFIMF較FIMF，節(jié)點消耗的能量更少，增強了路由算法的健壯性。

圖5 總能量消耗

4 結(jié)論

機會網(wǎng)絡中的FIMF路由機制中，普通節(jié)點在傳遞控制消息(如節(jié)點位置消息、Hello消息)時存在多余的通信開銷，并且采用了大功率發(fā)送位置消息會耗費過多能量。本文提出了FIMF的改進路由算法AFIMF，該算法降低了節(jié)點長距離無線電發(fā)送控制消息的功率，減少了node發(fā)送Hello消息的次數(shù)。仿真結(jié)果表明，AFIMF在保證消息傳遞成功率不低于FIMF方案的前提下，能減小網(wǎng)絡的總能量消耗、控制開銷和節(jié)點Hello消息的次數(shù)。

［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，F(xiàn)U 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網(wǎng)絡中ferry節(jié)點的MSSL路由算法研究［J］.計算機技術(shù)與發(fā)展，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.