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

(1.重慶郵電大學(xué) 移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶400065;2.重慶大學(xué) 光電技術(shù)及系統(tǒng)教育部重點(diǎn)實(shí)驗(yàn)室，重慶400044)

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

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

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

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

1.1 FIMF網(wǎng)絡(luò)模型

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

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

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

1.2 存在問(wèn)題

FIMF路由方案中存在以下問(wèn)題:

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

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

2 改進(jìn)的FIMF方案

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

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

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

所以本機(jī)制的改進(jìn)方法是可行的，并且能達(dá)到預(yù)期的有益效果。

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

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

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

表1 y與P的分布律

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

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

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

3.1 仿真設(shè)置

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

表2 參數(shù)列表

3.2 性能分析

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

圖2 消息傳遞成功率

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

圖3 網(wǎng)絡(luò)控制開(kāi)銷

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

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

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

圖5 總能量消耗

4 結(jié)論

機(jī)會(huì)網(wǎng)絡(luò)中的FIMF路由機(jī)制中，普通節(jié)點(diǎn)在傳遞控制消息(如節(jié)點(diǎn)位置消息、Hello消息)時(shí)存在多余的通信開(kāi)銷，并且采用了大功率發(fā)送位置消息會(huì)耗費(fèi)過(guò)多能量。本文提出了FIMF的改進(jìn)路由算法AFIMF，該算法降低了節(jié)點(diǎn)長(zhǎng)距離無(wú)線電發(fā)送控制消息的功率，減少了node發(fā)送Hello消息的次數(shù)。仿真結(jié)果表明，AFIMF在保證消息傳遞成功率不低于FIMF方案的前提下，能減小網(wǎng)絡(luò)的總能量消耗、控制開(kāi)銷和節(jié)點(diǎn)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)絡(luò)中ferry節(jié)點(diǎn)的MSSL路由算法研究［J］.計(jì)算機(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.