王汝言，金 勇，吳大鵬，林艷芳，徐 蕾

(1.重慶郵電大學寬帶泛在接入技術研究所，重慶 400065;2.中國移動通信集團設計院有限公司重慶分公司，重慶 400042;3.無錫源清高新技術研究所有限公司傳感網(wǎng)研究中心，江蘇 無錫 214000)

0 引言

隨著具有無線通信能力的個人手持設備逐漸普及，節(jié)點間可以通過自組織的形式組成通信網(wǎng)絡，進而實現(xiàn)數(shù)據(jù)傳輸。但在復雜多變的實際環(huán)境中，節(jié)點頻繁移動以及周期性休眠等原因，導致通信雙方可能并不存在完整的端到端路徑。為了提高此種網(wǎng)絡狀態(tài)下的通信靈活性，研究人員提出了一種新的網(wǎng)絡體系結(jié)構(gòu)，即機會網(wǎng)絡［1］，利用節(jié)點移動形成的通信機會，以“存儲—攜帶—轉(zhuǎn)發(fā)”的路由模式實現(xiàn)節(jié)點間通信。

機會網(wǎng)絡的路由機制可以分為兩大類:單副本路由機制和多副本路由機制。對于單副本路由機制來說，整個網(wǎng)絡中只存在給定消息的唯一副本。根據(jù)其采用的路由策略，源節(jié)點和中繼節(jié)點將該消息逐跳轉(zhuǎn)發(fā)到目的節(jié)點。但是對于動態(tài)性極強的機會網(wǎng)絡來說，此種路由機制的消息投遞難以保障。與單副本機制相對，多副本路由機制中，網(wǎng)絡中存在多個相同消息的副本，以達到提高消息成功投遞率的目的，此種機制的缺陷也比較明顯，即多個副本將消耗掉更多的網(wǎng)絡帶寬及存儲資源。

可見，機會網(wǎng)絡采用面向無連接的消息轉(zhuǎn)發(fā)方法，對于多副本機制來說，任何節(jié)點無法獲知所攜帶消息其他副本的狀態(tài)，其中包括副本數(shù)量及投遞狀態(tài)等。當消息的某個副本成功轉(zhuǎn)發(fā)至目的節(jié)點之后，其他中繼節(jié)點的緩存中可能依然保存該消息的副本，若繼續(xù)對其余副本執(zhí)行轉(zhuǎn)發(fā)操作將極大地浪費有限的網(wǎng)絡資源。因此，有效的冗余消息刪除機制對提高資源有限的機會網(wǎng)絡性能至關重要。

目前，對于上述冗余消息的刪除方法主要是通過分發(fā)確認消息(acknowledgement，ACK)來實現(xiàn)，文獻［2］提出了一種被動式ACK消息分發(fā)方法，攜帶ACK消息的節(jié)點并不執(zhí)行主動擴散過程，而是當有其他節(jié)點向其轉(zhuǎn)發(fā)已成功投遞的消息時，節(jié)點才將對應的確認消息轉(zhuǎn)發(fā)給對方，以刪除冗余消息。雖然此種方法能夠防止ACK消息的泛洪，但是，ACK信息在網(wǎng)絡中擴散的速度較慢，無法及時刪除消息的冗余副本。文獻［3］提出了一種主動分發(fā)方法，每個節(jié)點保存相應的ACK列表，以標識其攜帶的ACK信息，當與其他節(jié)點相遇之后，首先轉(zhuǎn)發(fā)彼此攜帶的全部ACK信息，從而快速擴散ACK消息。在主動分發(fā)ACK消息的基礎上，文獻［4］考慮了人類移動的特點，通過在人類聚集點設立固定的轉(zhuǎn)發(fā)節(jié)點來分發(fā)ACK列表信息，從而以更快的速度刪除冗余消息?？梢姡鲜霾呗跃宰畲蠡疉CK信息轉(zhuǎn)發(fā)速度為目標，并未考慮ACK信息的分發(fā)所帶來的開銷。顯然，每個成功投遞的消息均與多個ACK消息對應，在網(wǎng)絡規(guī)模較大或者所產(chǎn)生消息較多的情況下，轉(zhuǎn)發(fā)ACK消息所耗費的網(wǎng)絡資源將快速增加。此外，若兩個節(jié)點的相遇間隔時間較短，仍然轉(zhuǎn)發(fā)全部的ACK信息將引入不必要的開銷。

本文提出了一種自適應的ACK分發(fā)機制(adaptive ACK distribution，AAD)，通過網(wǎng)絡運行過程的歷史信息，各個節(jié)點以分布式的方式估計區(qū)域消息密度，并根據(jù)ACK消息歷史轉(zhuǎn)發(fā)節(jié)點及ACK消息轉(zhuǎn)發(fā)跳數(shù)來執(zhí)行轉(zhuǎn)發(fā)判定。由于考慮了不同ACK消息對于節(jié)點必要性之間的差異，所提出的ACK分發(fā)機制能夠更好的使用網(wǎng)絡資源。

1 ACK消息

對于任一節(jié)點，當收到以自身為目的節(jié)點的消息時會產(chǎn)生ACK消息，用來表示該消息已經(jīng)成功投遞。如前所述，機會網(wǎng)絡中的數(shù)據(jù)轉(zhuǎn)發(fā)過程需要多個中繼節(jié)點輔助，網(wǎng)絡中存在多個給定消息的副本，在消息成功投遞后，容易產(chǎn)生冗余消息。與傳統(tǒng)網(wǎng)絡中TCP的確認機制不同，機會網(wǎng)絡中的ACK消息并不是為了實現(xiàn)數(shù)據(jù)的可靠傳輸，而是為了刪除冗余消息，防止其繼續(xù)執(zhí)行傳輸過程，占用網(wǎng)絡資源，從而實現(xiàn)提高網(wǎng)絡資源利用率的目標。

在節(jié)點維護的ACK列表中，每條記錄與相應的ACK消息對應，其結(jié)構(gòu)如圖1所示，圖1中源節(jié)點序列號與目的節(jié)點序列號標識了消息的發(fā)送節(jié)點與接收節(jié)點，大小為48 bit［5］。序列號字段記錄源節(jié)點發(fā)送消息時對應的數(shù)據(jù)序號。按照上述方法，ACK所對應的消息由三元組唯一標識，其中包括源節(jié)點序列號，目的節(jié)點序列號，消息序列號。生存時間記錄了該ACK消息能夠在網(wǎng)絡中存活的最長時間。節(jié)點定期檢查ACK列表，當記錄中的ACK消息生存期到期時，則刪除該記錄。

圖1 ACK消息結(jié)構(gòu)Fig.1 Structure of ACK message

2 自適應的ACK分發(fā)機制

機會網(wǎng)絡中的各個節(jié)點所攜帶的消息不同，各個節(jié)點對于ACK消息的需求程度也呈現(xiàn)出一定的差異;同時，網(wǎng)絡資源有限，節(jié)點之間的連接持續(xù)時間較短，因此，需要將ACK消息有針對性地轉(zhuǎn)發(fā)給攜帶冗余消息以及將來可能接收冗余消息的節(jié)點。本文提出自適應ACK分發(fā)機制包含兩個階段，分別為洪泛階段及轉(zhuǎn)發(fā)控制階段，在不同的階段內(nèi)定義了不同的轉(zhuǎn)發(fā)的條件。

1)泛洪階段:此階段為ACK消息產(chǎn)生的初期階段。為了以最快的速度刪除冗余消息，ACK消息的攜帶節(jié)點以洪泛的方式向其他節(jié)點發(fā)送相關信息，即節(jié)點相遇之后，轉(zhuǎn)發(fā)彼此攜帶的所有ACK消息。為了有效地限制轉(zhuǎn)發(fā)過程中所產(chǎn)生的資源消耗，本文采用基于跳數(shù)的方法來控制ACK的轉(zhuǎn)發(fā)范圍。所提出的方法中，每個ACK消息具有相應的轉(zhuǎn)發(fā)上限值，表明消息轉(zhuǎn)發(fā)次數(shù)的最大值。圖2描述了由節(jié)點A產(chǎn)生的初始轉(zhuǎn)發(fā)上限值L=3的消息轉(zhuǎn)發(fā)歷史記錄。

2)轉(zhuǎn)發(fā)控制階段:當節(jié)點攜帶的某個ACK消息的轉(zhuǎn)發(fā)上限為0時，則進入轉(zhuǎn)發(fā)控制階段。該階段中，ACK消息的轉(zhuǎn)發(fā)由局部消息密度確定，在某個區(qū)域中，攜帶有消息i的節(jié)點數(shù)與這個區(qū)域中所有節(jié)點數(shù)的比值稱為消息i的局部密度。若消息i的密度較高，則表明該區(qū)域內(nèi)消息i對應的ACK消息較少，這時消息i會以較大的概率在區(qū)域中繼續(xù)轉(zhuǎn)發(fā)，感染其余節(jié)點，此種情況下需要轉(zhuǎn)發(fā)ACK來減少這個區(qū)域中消息i的冗余度，以有效地降低冗余消息繼續(xù)轉(zhuǎn)發(fā)所帶來的資源浪費。

圖2 基于跳數(shù)轉(zhuǎn)發(fā)的示例Fig.2 Illustration of hop-based forwarding

根據(jù)機會網(wǎng)絡的消息轉(zhuǎn)發(fā)原理，節(jié)點相遇之后，需要交換彼此的消息索引列表來告知對方自身所攜帶的消息狀態(tài)，進而，節(jié)點可以維護相遇歷史信息表，如圖3所示，包括相遇節(jié)點的地址、相遇時間及節(jié)點攜帶消息的ID。消息的局部密度通過對列表內(nèi)的信息進行估算得到。

圖3 歷史節(jié)點相遇信息Fig.3 Historical meeting information of node

根據(jù)T時間內(nèi)相遇節(jié)點的個數(shù)N(T)及當中攜帶i消息的節(jié)點個數(shù)Mi(T)，可獲知消息i的局部密度MDi(T)，如式(1)所示

根據(jù)消息i的局部密度值，節(jié)點按照式(2)執(zhí)行ACK消息的轉(zhuǎn)發(fā)判定。

(2)式中，ρth為局部密度閾值。

此外，ACK消息的分發(fā)方法至關重要，大多文獻采用Hello或者Reply分組來攜帶ACK信息［6-7］，但此種分組采用周期發(fā)送方式，使得大量ACK消息出現(xiàn)重復投遞的情況。本文提出的ACK分發(fā)機制中充分地考慮了相應的歷史狀態(tài)信息，節(jié)點轉(zhuǎn)發(fā)ACK消息列表時，只針對未轉(zhuǎn)發(fā)過的ACK消息。按照此種方式，Hello分組的轉(zhuǎn)發(fā)數(shù)量得到了控制，降低了發(fā)送ACK消息列表所帶來的開銷，且沒有增加新的控制分組來傳送。

自適應ACK消息轉(zhuǎn)發(fā)機制原理如圖4所示，其中節(jié)點Y為相遇節(jié)點，ACK_i為消息i的確認消息。

圖4 自適應的ACK消息轉(zhuǎn)發(fā)機制Fig.4 Adaptive forwarding mechanism of ACK

加入ACK后路由的轉(zhuǎn)發(fā)步驟會有所不同。對于節(jié)點X，Y來舉例，X節(jié)點通過周期廣播帶有本地數(shù)據(jù)消息列表的Hello分組來尋找鄰居節(jié)點，當Y節(jié)點收到X節(jié)點發(fā)送的Hello分組時，返回Reply對需要的數(shù)據(jù)消息進行請求，并轉(zhuǎn)發(fā)按照圖4確定需要轉(zhuǎn)發(fā)的ACK，X節(jié)點收到Reply后首先根據(jù)收到的ACK列表對自身的冗余消息進行刪除，然后按照路由轉(zhuǎn)發(fā)策略發(fā)送請求分組。

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

本部分采用ONE(opportunistic network environment)仿真平臺［8］對所提機制的相關性能進行驗證，并與其他典型路由機制進行比較，其中包括Epidemic［9］及 PROPHT［10］路由機制。具體參數(shù)如表 1 所示。

仿真場景中的節(jié)點包含3類，分別為電車節(jié)點、汽車節(jié)點和行人節(jié)點，電車節(jié)點按照固定軌道進行運動，行人及汽車都是以隨機選擇一個目的節(jié)點，然后按照最短路徑移動到目的節(jié)點的方式進行運動。實驗在不同緩存及不同節(jié)點數(shù)的情況下，將AAD方法與洪泛ACK的方法以及無ACK這3種情況進行了比較。其中初始轉(zhuǎn)發(fā)上限L取6，ρth為0.2。

表1 仿真參數(shù)設置Tab.1 Simulation parameters

圖5為ACK消息的平均攜帶率，也就是攜帶某個ACK消息的節(jié)點數(shù)與全網(wǎng)節(jié)點數(shù)的比例，ACK消息的平均攜帶率可以反映出ACK消息的平均分發(fā)程度?？梢钥吹剑斅酚刹捎煤榉篈CK的方法時，ACK消息幾乎都能投遞到網(wǎng)絡中的所有節(jié)點，忽略了節(jié)點對于不同ACK的需求程度差異。而在采用AAD的Epidemic及PROPHT中，通過有效的分發(fā)控制，將ACK消息平均投遞到網(wǎng)絡中四分之一的節(jié)點中，并且具有與洪泛ACK相近的冗余消息刪除能力，說明了AAD能夠滿足不同節(jié)點對于ACK消息的需求差異，降低了網(wǎng)絡資源的消耗，相比洪泛ACK具有更高的效益。

圖5 ACK消息的攜帶率比較Fig.5 Carriage ratio of ACK message

圖6為網(wǎng)絡性能隨節(jié)點組個數(shù)變化的仿真圖。在這個場景中，節(jié)點內(nèi)存大小為50 MByte，行人組及汽車組中的節(jié)點個數(shù)在40－80之間變化。

圖6 節(jié)點組個數(shù)變化對性能的影響Fig.6 Network performance under different group number

圖6a表明引入ACK消息能夠較大程度的提高消息的投遞率。隨著節(jié)點個數(shù)的增加，節(jié)點之間相遇的機會也隨之增多，進而導致洪泛ACK所帶來的開銷更大，由于AAD能夠使得ACK消息更加有效的分發(fā)，所以Epidemic及PROHPET路由采用AAD機制的投遞率較采用洪泛ACK的投遞率高。由圖6b可以看到消息的傳輸時延隨節(jié)點數(shù)量的增加而逐漸降低，其主要原因在于更多節(jié)點可以充當中繼節(jié)點，從而使得平均時延降低。由于減少了ACK消息的轉(zhuǎn)發(fā)，所提出的機制降低了控制開銷，比采用洪泛ACK路由機制的時延更低。圖6c中的網(wǎng)絡負載率為:(轉(zhuǎn)發(fā)的消息數(shù)－成功投遞的消息數(shù))/成功投遞的消息數(shù)，反映的是平均轉(zhuǎn)發(fā)多少個消息才能成功投遞一個消息。圖6c表明ACK消息的引入能夠刪除網(wǎng)絡中的冗余消息，從而避免轉(zhuǎn)發(fā)這類消息產(chǎn)生的不必要的開銷。AAD及洪泛ACK都具有相似的開銷，這說明AAD也能夠及時的刪除網(wǎng)絡中的冗余消息，提高網(wǎng)絡效率。

圖7為性能隨緩存大小變化的仿真圖，在這個場景中，行人組及汽車組中的節(jié)點個數(shù)為50，節(jié)點內(nèi)存在10－50 MByte變換。

圖7 緩存大小變化對性能的影響Fig.7 Network performance under different buffer size

圖7a中消息的投遞率隨著節(jié)點緩存的增大而提高，這是由于節(jié)點內(nèi)存較小時容易發(fā)生擁塞，使得節(jié)點不得不丟棄某些消息從而影響投遞率，隨著內(nèi)存的增加更多的消息能夠保存在內(nèi)存中使得消息成功投遞的機會增加。ACK消息的引入能夠刪除冗余消息，騰出空間用來存放其余的消息，從而進一步提高投遞率。路由使用AAD后能用較少的ACK消息來實現(xiàn)刪除冗余消息的目標，在提高投遞率的同時降低消息的平均時延。在圖7b中傳輸時延逐漸增加，這是因為那些因內(nèi)存不足被刪除的消息在節(jié)點內(nèi)存較大的時候會被保留下來，它們會經(jīng)歷更長的時間被投遞到目的節(jié)點，導致傳輸時延的增加。圖7c中AAD與洪泛ACK幾乎具有相同的開銷，表明AAD能夠達到洪泛ACK對網(wǎng)絡冗余消息刪除的效果。

4 總結(jié)

本文研究了ACK消息在冗余消息刪除上發(fā)揮的作用，闡明了洪泛ACK消息帶來的問題，并根據(jù)節(jié)點對于ACK消息需要程度的不同，提出了自適應的ACK分發(fā)機制，該機制實現(xiàn)簡單，且擴展性極強，能夠適用于任何多副本路由機制。仿真結(jié)果表明，改進后的ACK分發(fā)機制能夠有效的提高網(wǎng)絡數(shù)據(jù)的投遞率，降低端到端時延，提高網(wǎng)絡性能。

［1］熊永平，孫利民，牛建偉，等.機會網(wǎng)絡［J］.軟件學報，2009，20(1):124-137.XIONG Yongping，SUN Limin，NIU Jianwei，et al.opportunistic networks［J］.Journal of Software，2009，20(1):124-137.

［2］KHALED H，KEVIN A，ELIZABETH B.Delay Tolerant Mobile Networks (DTMNs): Controlled Flooding Schemes in Sparse Mobile Networks［J］.IFIP Networking，2005:1180-1192.

［3］RICHARD J L，PADMA M ，MATT E ，et al.Epidemic routing with immunity in Delay Tolerant Networks［J］.Military Communications Conference，2008，21(1):1-7.

［4］KAVEEVIVITCHAI S，OCHIAI H，ESAKI H.Message Deletion and Mobility Patterns for Efficient Message Delivery in DTNs［J］.Pervasive Computing and Communications Workshops，2010，23(6):760-763.

［5］WIKIPEDIA.The Free Encyclopedia.MAC Address［EB/OL］.(2011-09-06)［2012-03-05］.http://en.wikipedia.org/wiki/MAC_address.

［6］MATSUDA T，TAKINE T.(p，q)-epidemic routing for sparsely populated mobile ad hoc networks［J］.Selected Areas in Communications，2008，26(5):783-793.

［7］JIN Zhigang，ZHAO Ximan，LUO Yongmei，et al.Adaptive Priority Routing with Ack_Mechanism for DTN networks［J］.Wireless Communications ＆ Signal Processing，2009，32(1):1-5.

［8］KERANEN A，OTT J，KARKKAINEN T.The ONE Simulator for DTN Protocol Evaluation［C］//ICST.The 2nd International Conference on Simulation Tools and Techniques.Italy:ACM，2009:1-10.

［9］VAHDAT A，BECKER D.Epidemic Routing for Partially connected Ad Hoc Networks［R］.Duke University:Technical Report CS-200006，2000.

［10］ANDERS L，AVRI D，OLOV S.Probabilistic routing in intermittently connected networks［J］.Service Assurance with Partial and Intermittent Resources，2004，18(2):239-254.