間歇性連通網絡數據傳輸與路由技術研究* 1

康宗緒，雷文虎，李廣志，蘇凌旭

(1.重慶金美通信有限責任公司,重慶 400030；2.中國人民解放軍駐重慶氣體壓縮機廠軍事代表室,重慶 400030)

?

間歇性連通網絡數據傳輸與路由技術研究* 1

康宗緒1，雷文虎1，李廣志2，蘇凌旭1

(1.重慶金美通信有限責任公司,重慶 400030；2.中國人民解放軍駐重慶氣體壓縮機廠軍事代表室,重慶 400030)

摘要：移動網絡需要適應各種復雜應用環境，在出現節點密度較低、移動性又高的場景時，稀疏的節點就難以保證網絡拓撲的穩定性和全連通性。在這種不理想的網絡環境中，傳統的移動自組網路由協議會因為網絡頻繁中斷、間歇性連接和較大的網絡時延等條件限制，無法建立端到端穩定的路由路徑而造成算法失效。針對移動網絡間歇性連通的特性，結合DTN思想，充分利用節點間相遇的機會交互數據，借助代理節點來提高數據傳輸的成功率，最大化報文的傳輸可能性。

關鍵詞：移動網絡；容斷網絡；代理節點；機會網絡

0引言

在移動ad hoc網絡的實際應用中，常會出現因節點移動、障礙物反射、信號衰減等因素造成網絡在某些時刻不連通情況。傳統的移動ad hoc網絡在傳輸數據之前，需要節點通過相應的路由算法建立源到目的節點之間的路徑，然后將數據沿建好的路徑傳遞給目的節點。在這種數據傳輸模式下，就要求網絡在絕大部分時候處于連通狀態，網絡中節點之間至少存在一條端到端的路徑。而在實際應用中，由于某些客觀因素無法保證網絡一直處于連通狀態，網絡可能被分割成若干個互不連通的子網[1]。當源節點和目的節點不在同一子網時，傳統的移動ad hoc網絡路由機制就無法建立路由來完成數據傳輸。

由于節點可以隨機移動，當節點通過移動進入彼此的通信范圍時，便可以完成數據的交互，這使得網絡在不連通的條件下完成數據的交互成為可能。我們將這種利用節點移動創造的相遇機會來完成數據傳遞的網絡，稱為機會網絡[2]。

如果能夠解決在間歇性連通的網絡上傳遞數據，在民用和軍事領域都有很廣泛的應用和研究價值。與傳統無線網絡相比，機會網絡的拓撲動態變化更頻繁，節點間沒有穩定的傳輸路徑，甚至可能在任意時刻都沒有一條完整的傳輸路徑，使得那些依賴于穩定傳輸路徑的傳統路由機制難以發揮作用。

1技術思路

本文所提出的路由思想與傳統移動ad hoc所采用的表驅動路由或按需路由相比[3]，增加了對長時延容忍的考慮，提出了一種新的數據封裝、數據緩存、數據包雙重利用以及數據包緩存時間動態化等機制，同時強調了代理節點在網絡中所起的作用。

代理節點的選擇比較關鍵，其選擇好壞可以影響消息的轉發次數。代理節點的選擇基于歷史相遇記錄的概率估計和節點的社會性兩方面綜合考慮得出。節點的社會性主要由節點相似性和局部介效中心性兩部分組成。介數中心性是節點連接其他節點路徑程度上的度量，具有較大介數中心性的節點在網絡中的位置比較重要，有利它連接的節點之間的交互[4]。代理節點確定后，周期性廣播最小Age的代理節點通告消息。

假設存在如圖1所示的移動通信網絡使用場景，各節點之間的有效通信距離有限。區域內的各個節點在運行過程中根據上述機制選舉出一個代理節點(或稱為中心節點/網關節點)。區域內的各個節點均知道代理節點是誰，并且知道本節點距離代理節點跳數(H)；代理節點知道到達區域內其他節點的顯式路徑。代理節點在被摧毀或者節點本身不足以提供代理節點功能之后，可以動態的選舉出新的代理節點。

圖1　網絡拓撲示意

如果兩點間可直接交互(如M3傳遞數據給M2)，就直接傳送數據。如果不能直接交互(如M3傳遞數據給M5)，則將數據進行封裝發送給代理節點，由代理節點負責轉發。為了做到數據的可靠性傳輸，代理節點在收到數據后向源節點回傳一個確認數據包，表明已經受理該數據，同時將該數據緩存起來，負責將其傳送到目標節點。源節點接收到確認數據包后撤銷對該數據的管理。目標節點接收到數據后向代理節點回傳一個確認數據包，表明已經接收該數據。代理節點收到目標節點的確認數據包后撤銷對該數據的管理。也就是說，數據包只在源節點和代理節點上進行緩存和管理，中間節點只負責傳遞。

數據包在向代理節點轉發的過程中，會在數據包中攜帶上所經過的節點。代理節點收到外來數據包時，從數據包中提取出顯式路徑保存到路由表中。當數據包需要從代理節點向普通節點轉發時，利用路由表中的顯式路徑傳遞。

假設在圖1中的M3需要向M5發送數據，但M3發現它無法與M5直接交互，此時M3將數據進行封裝，設置源節點為M3，目標節點為Mc，距離代理節點跳數H=3，然后將數據包發送出去，該數據包可以被M2接收到。M2收到數據包后，發現該數據的目標節點為Mc，它將不再封裝數據，只需要修改距離代理節點跳數H=2，然后轉發出去。M1的處理方式與M2相同，它發送出去的數據即可被代理節點Mc接收到。當Mc收到M3的數據后，針對該數據生成一個確認數據包回傳給M3，并進一步轉發該數據。Mc發出的數據經過M4最終到達目標節點M5。M5收到數據之后，發現源節點是代理節點Mc，它需要針對該數據生成一個確認數據包回傳給Mc。Mc在接收到確認數據包后，撤銷對該數據的管理，本次通信結束。

從總體技術實現上可以看出，區域內存在兩種類型的節點：普通節點和代理節點。普通節點上只需要保存距離代理節點跳數H，代理節點上需要保存其到達區域內各個節點的顯式路徑。

2跳數學習

在網絡開通初期，各個節點不知道區域內的代理節點是誰，其距離代理節點跳數H為多少，在此通過被動學習方式來獲取。在網絡運行起來之后，就可以從接收到的數據包中提取最新的距離代理節點跳數并動態更新。

圖2　跳數探測過程

如圖2所示，由代理節點主動發出跳數探測數據包，各普通節點接收處理跳數探測數據包并判斷是否繼續向外轉發。普通節點可以接收任何跳數的探測數據包，它選擇跳數值最小的作為本節點距離代理節點跳數，將跳數值次之的作為備用跳數，然后將本節點距離代理節點跳數向外轉發。

代理節點Mc發出一個跳數探測數據包，指示區域內的當前代理節點為Mc，距離代理節點跳數H=0，這個包可以同時被M1、M4、M6、M7接收到。當M1、M4、M6、M7收到跳數探測包后，記錄區域內的當前代理節點為Mc，距離代理節點跳數H=1，同時繼續向外發送一個跳數探測數據包。當M5接收到M4發出跳數探測數據包后，記錄區域內的當前代理節點為Mc，距離代理節點跳數H=2。當M2接收到M1或M7發出的跳數探測數據包后，它只處理其中一個包而丟棄另外一個包，記錄區域內的當前代理節點為Mc，距離代理節點跳數H=2。M3可能會收到M2或M7發出的跳數探測數據包，此時它記錄區域內的當前代理節點為Mc，距離代理節點跳數H=2，同時把H=3作為其備用跳數。至此區域內所有節點均學習到了代理節點是誰及其距離代理節點跳數是多少。

3路由學習

在網絡開通初期，代理節點不知道區域內存在哪些節點，更不知道其到各個節點的路徑是什么，在此也通過被動學習方式來獲取。在網絡運行起來之后，就可以從接收到的數據包中提取顯式路徑并動態更新。

如圖3所示，當普通節點學習到代理節點及距離代理節點跳數之后，主動生成一個路徑探測數據包向代理節點發送，這個數據包根據攜帶的跳數選擇下一跳并記錄下經過的節點，當該數據包到達代理節點后，代理節點即可從數據包中將該顯式路徑提取出來并保存。如果此時恰好有數據需要向代理節點發送，就不用發送路徑探測數據包了，因為它們都可以實現路徑探測的功能。為了避免多個節點同時生成這種數據包導致信道搶占，對這種特殊數據包的產生采用一定的退避機制。

圖3　代理節點顯式路由生成

為了減少路徑探測數據包的數量，限制跳數為1跳的節點不能發送該類數據包。如果有跳數大于1的節點的路徑探測數據包經過了某個節點，該節點就不用再生成自己的路徑探測數據包了，代理節點會從之前經過的那個路徑探測數據包中提取到該節點的顯式路徑。圖3中，M3發出的路徑探測數據包可將M3、M2、M1到代理節點的顯式路徑全部帶回去。

4業務轉發

4.1源節點發向代理節點

源節點向代理節點轉發的數據包采用探測轉發的方式。在移動ad hoc網絡中，由于一個節點發出的數據可以同時被多個節點接收到，因此需要對其進行控制，以免數據在無線網絡中出現同一數據循環發送的現象，造成無線信道被搶占和電池能量的耗費。數據包中所攜帶的本節點距離代理節點跳數，正是為了實現這個目的。

當本節點距離代理節點跳數小于數據包中所攜帶的跳數時，節點才將該數據包轉發出去，否則直接拋棄所接收的數據包。這種機制可以讓數據以最短跳數方式到達代理節點。數據包到達代理節點后，代理節點會從數據包中提取出本次經過的顯式路徑，并將其作為最新路徑保存下來，以供今后代理節點需要向源節點轉發數據時使用。

從圖4中可以看出，M3發送數據到Mc存在兩條路線：M3→M7→c和M3→M2→M1→Mc。M3在封裝數據包時，填寫距離代理節點跳數H=2，發送出去的數據包會同時被M2和M7接收到。當M7接收到數據包后，發現自己距代理節點跳數為1，它會更改跳數H=1并將數據轉發出去。當M2接收到數據包后，發現自己距離代理節點跳數也為2，它將直接丟棄該數據不再進行轉發。這種機制使得數據傳送選擇M3→M7→Mc路線。

圖4　源節點數據包探測轉發

4.2代理節點確認反饋

代理節點向源節點傳送的確認數據包，并標識該確認數據包是代理節點生成的。由于代理節點從接收到的源節點數據包內部提取出了數據包前向轉發時所經過的各個節點，代理節點回傳給源節點的確認數據包可以按照顯式路徑返回。

從圖5可以看出，在代理節點Mc向源節點M3返回確認數據包時，存在兩條路徑：Mc→M1→M2→M3和Mc→M7→M3。Mc在封裝確認數據包時填寫返程路徑為M7→M3，Mc發出的數據包會同時被M1、M4、M6和M7接收到。當M1、M4和M6接收到數據包后，發現自己不包含在顯式路徑中，就直接丟棄該數據包。當M7接收到數據包后，發現自己包含在顯式路徑中，它將數據包的顯式路徑中去掉自己，重新封裝確認數據包填寫返程路徑為M3并發送出去。M3在接收到確認數據包后釋放對原數據的管理。

圖5　代理節點確認反饋

4.3代理節點發向目標節點

由于代理節點上有到區域內任何一個節點的顯式路徑，所以代理節點在封裝數據時會將路徑攜帶上，向目標節點發送的數據包將按照顯式路徑進行傳遞，該過程與代理節點發向源節點的傳送方式相同。

4.4目標節點確認反饋

當目標節點接收到來自代理節點的數據包時，它需要向代理節點回傳確認數據包，并標識該確認數據包是由目標節點生成的，傳送過程與源節點發向代理節點的過程相同。這個確認數據包在帶回確認消息的同時，也帶回了從Mc到達目標節點的最新顯式路徑，Mc會將該顯式路徑更新到路由表中。

如圖6所示，之所以采用這種處理機制，是因為雖然可以讓M5知道數據是從Mc→M4→M5傳遞過來的，但是等到M5回傳數據時，有可能由于M4已關機或者中間障礙物的阻擋或者受到電磁干擾等因素，回程路徑已經不可達。而且采用顯式路徑返回與采用回程探測路徑方式返回所占用的資源完全相同，還能獲得最新可用路徑。

圖6　目標節點確認反饋

4.5數據中途截獲

在無線鏈路上傳輸數據時，可能出現圖7所示的情況：M3需要向M1發送數據，由于M3不能直接與M1交互，需要將數據進行封裝發送給代理節點Mc，由Mc負責轉發，但是向Mc轉發的時候又會經過目標節點M1。這時就沒有必要再傳送到Mc節點去了，需要目標節點具備中途截獲數據的功能。

圖7　數據包中途截獲

當節點接收到發往代理節點的前向轉發數據包時，它需要查看封裝的數據內容，判斷目標節點是否為自己。如果不是自己，則繼續向外轉發；如果發現目標節點就是自己，說明數據已經到達目的端，它將該數據截獲下來，然后生成一個確認數據包返回給源節點，并標識該確認數據包是由目標節點生成。圖中的紅色虛線表示是目標節點直接向源節點返回的確認數據包。

4.6緩存時間動態化

當引入數據中途截獲機制后，可能會出現圖8所示的兩種情況。情況一：M3需要向M7發送數據，當數據到達M2時，就可以被M7接收到并返回確認數據包，而M1也會繼續將數據傳送到Mc上去，并由Mc向M3返回確認數據包，同時Mc還會將數據再一次的向M7轉發并要求M7返回確認數據包。情況二：M5需要向M6發送數據，M5不能直接與M6交互，當封裝好的數據包傳遞到M4后，M4發出的數據包會同時被M6和Mc接收到，Mc會向M5回傳確認數據包，M6也會向M5回傳確認數據包，而且Mc還會向M6轉發數據并要求M6返回確認數據包。

圖8　緩存時間動態化

通過對上述過程分析，目標節點可能會兩次收到同一個數據包，這可以在應用層通過數據內容過濾掉。源節點針對同一個數據包可能會接收到兩個確認數據包。針對第二個現象，我們引入數據包緩存時間動態化的機制。

源節點對需要發送出去的數據包的緩存時間可以很長，在收到確認數據包之后才將主動清除緩存的數據包；代理節點對需要中轉的數據包的緩存時間也可以很長，得到確認之后才主動刪除緩存的數據包；目標節點將收到的數據包直接交給應用層處理，不需要進行緩存。源節點只要接收到該數據的確認數據包后就可以撤銷對其的管理，而不管該確認數據包是由目標節點生成的還是由代理節點生成的。

4.7數據包多重利用

通過對上述思想及流程的分析，我們可以發現數據包可以歸納出兩個功能：傳遞數據和探測路由。為了減少無線網絡中發送的數據包的數量，需要將發送的數據充分的利用起來，在此提出兩種應用模式。

(1)距離代理節點跳數和顯式路徑的探測

距離代理節點跳數和顯式路徑的探測，通過專門設計的兩個TLV實現。

對于顯式路徑的探測，在普通節點發往代理節點的數據包中，封裝一個顯式路徑TLV來實現顯示路徑的搜集。

對于距離代理節點跳數的探測，除了在網絡開通初期發送出去的跳數探測數據包中封裝距離跳數TLV之外，在代理節點發往普通節點的數據包中也封裝一個距離跳數TLV進去。中間節點可以對距離跳數TLV進行動態調整，這樣各節點收到數據包的同時也學習到了當前距離代理節點的最短跳數。距離代理節點跳數的動態調整過程通過圖9的示例進行說明。

圖9　距離跳數動態調整

如圖9左邊所示，假設代理節點Mc當前路由表中保存的到達M3顯式路徑為Mc→M1→M2→M3，而此時M2已經轉移到了新的位置，使得M3距離代理節點跳數變成了2。Mc根據該顯式路徑封裝數據包并設置距離代理節點跳數H=0，發出的數據包可以被M1和M2接收到。M1接收到該數據包后進行處理，它轉發的數據包已經不能到達目標節點M3了。M2接收到該數據包后進行處理，它將距離跳數改為H=1，并將顯示路徑中的M1、M2去除，直接向M3轉發。M3收到數據包后，通過跳數TLV即可學習到其最新距離跳數為2。

如圖9右邊所示，假設代理節點Mc當前路由表中保存的到達M5顯式路徑為Mc→M6→M7→M4→M5，而此時M4已經轉移到了新的位置，使得M5距離代理節點跳數變成了2。Mc根據該顯式路徑封裝數據包并設置距離代理節點跳數H=0，發出的數據包可以被M6和M4接收到。M4接收到該數據包后進行處理，將距離跳數改為H=1，并將顯示路徑中的M6、M7、M4去除，直接向M5轉發。M6接收到該數據包后進行處理，將距離跳數改為H=1，并將顯式路徑中的M6去除，向M4和M7轉發。M7接收到該數據包后進行處理，將距離跳數改為H=2，并將顯式路徑中的M7去除，它轉發出來的數據將不能到達目標節點M5了。這樣目標節點M5會收到M4發送過來的兩條相同的數據包，但是距離代理節點跳數分別為2和3，M5會選擇H=2作為自己的距離代理節點跳數。M5在返回確認數據包的時候就可以將最新的顯式路徑送回代理節點并更新。

(2)多數據包組合

在圖10所示中，①為源節點向代理節點發送的數據包；②為代理節點發往目標節點的數據包；③為代理節點向源節點回傳的確認數據包；④為目標節點向代理節點發送的確認數據包；⑤為代理節點向源節點發送的數據包；⑥為代理節點向目標節點發送的數據包。

圖10　多數據包組合

可以看出，③和⑤、④和⑥的傳送方式一致，如果它們發送的間隔很短，那么它們走的路徑是完全相同的，因此為了減少無線網絡中傳遞數據包的數量，可以將這樣的數據包組合成一個數據包進行傳遞。也就是說，源節點和目標節點相同的數據在短時間內所經過的路徑是相同的，可以將短時間內兩個或多個這樣的數據包組合成一個數據包進行轉發，可以有效節省鏈路開銷，提供數據傳送效率。

5結語

本文利用選舉出的代理節點來實現間歇性連通網絡中的消息擺渡，提升稀疏環境下網絡的數據傳輸的性能和擴展性。數據源在首次發送數據報文時采用了探測發送機制，其本質還是泛洪，利用跳數和攜帶顯示路徑等機制來限制洪泛的范圍。基于泛洪的路由算法具有較好健壯性和較低的數據傳輸時延等特點，但該算法在數據傳輸過程中也會消耗較多能量，占用較多的帶寬資源和存儲空間。如果網絡規模較大或者節點的存儲空間或帶寬有限時，本算法就會呈現出不足的一面來。在未來的工作中，我們會考慮引入跨層機制[5]、增強對鄰居信息的感知等手段來減少首次報文投遞的盲目性，并進一步減少報文傳輸開銷。

參考文獻：

[1]錢雁斌,陳性元,杜學繪等. 無線多跳空間網絡間歇連通性問題研究[J]. 計算機科學,2009,36(11):52-55.

QIAN Yan-bin,CHEN Xing-yuan,DU Xue-hui,et al. Research on Intermittent Connectivity for Wireless Multiple-hop Space Network [J]. Computer Science,2009,36(11):52-55.

[2]楊勇. 基于地理位置信息的機會網絡路由算法研究[D]. 重慶：重慶郵電大學,2013.

YANG Yong. A Study on Location-based Routing Algorithms for Opportunistic Networks. Chongqing University of Posts and Telecommunications, 2013.

[3]沈亮光,汪學明. 移動 Ad hoc 網絡ZRP 路由協議的仿真分析[J].通信技術,2013, 46(08):71-73.SHENG Liang-guang, WANG Xue-ming. Simulation Analysis of ZRP Routing Protocol in Mobile Ad hoc Network[J]. Communications Technology,2013,46(08):71-73.

[4]Newman M E J. A Measure of Betweenness Centrality based on Random Walks[J]. Social Networks, 2005,27(5):39-54.

[5]LIU C, WU J. On Multicopy Opportunistic Forwarding Protocols in Nondeterministic Delay Tolerant Networks[J]．IEEE Transactions On Parallel and Dislributed Systems,2012,23(6):1121-1128．

Service Transfer and Routing Algorithm for Intermittent Connectivity Network

KANG Zong-xu1, LEI Wen-hu1，LI Guang-zhi2,SU Ling-xu1

(1.Chongqing Jinmei Communication Co.,Ltd., Chongqing 400030, China；2.PLA Military Representative Office Posted in Chongqing Gas Compressor Co., Ltd., Chongqing 400030,China)

Abstract：Mobile network is required to adapt various complex application environments. In the scene of low node density and high mobility, it is difficult for the sparse node to guarantee the stability and full connectivity of network topology. In such a non-ideal network environment, traditional routing algorithm, for frequent network interruption, intermittent connection and fairly large network delay, could not establish a stable end-to-end routing path and finally would cease to be effective. In view of the intermittent connection for mobile network, and in combination with DTN ideology, the proposed algorithm could catch the opportunity for nodes to meet each other and effectively implement message interaction and by depending on the agent node, improve the success rate of message transmission and provide reliable message delivery.

Key words：mobile networks；disruption tolerant networks(DTN)；agent node；opportunistic networks

doi:10.3969/j.issn.1002-0802.2016.05.016

* 收稿日期：2015-12-12；修回日期：2016-03-25Received date:2015-12-12；Revised date：2016-03-25

中圖分類號：TP393.0

文獻標志碼：A

文章編號：1002-0802(2016)05-0593-06

作者簡介：

康宗緒(1972—)，男，碩士，高級工程師，主要研究方向為計算機網絡及通信技術；

雷文虎(1980—)，男，碩士，工程師，主要研究方向為計算機網絡技術；

李廣志(1978—)，男，學士，工程師，主要研究方向為網絡通信技術；

蘇凌旭(1977—)，男，碩士，工程師，主要研究方向為通信協議處理。