英文摘要:This paper examines network control processes and conflict in an Ad hoc network in ordinary mode and Mesh mode in Wide Area Network(WAN). Distributed network management is proposed with a back-off mechanism and algorithm. The process and performance of this algorithm is analyzed, and other key issues and trends in network management are discussed in conclusion.

英文關鍵字:network management; back-off algorithm; Ad hoc network; certification process

基金項目：國家高技術研究發(fā)展(“863”)計劃(2008AA011004)

目前,，公共安全機構和組織在應急處理和災害響應時，越來越多地采用無線技術提供高效的命令,、控制和通信保障,。近年來多次緊急事件和災害顯示，出現(xiàn)緊急事件和發(fā)生災害的時間,、地點和規(guī)模難以預測,。加之當有災害事件發(fā)生時,，既有的通信設施和手段往往遭到破壞，依賴既有的網絡基礎設施來進行應急通信的質量需求是無法保障的[1],。因此,，具有分布式、移動性,、擴充性,、自適應性和靈活性的無線自組織網絡成為進行應急通信組網的重要手段。

1 自組織應急通信網絡概述

自組織(Ad hoc)網絡是一種多跳的自治系統(tǒng),。1968年在美國建立的ALOHA網絡和在1973年提出的PR網絡就是自組織網絡的原型,。其實ALOHA是一種單跳網絡，需要固定的基站,，網絡中的每個節(jié)點之間都可直接連接互相通信,。而PR網絡的提出，才是真正意義上地實現(xiàn)了多跳網絡,。PR網絡中各節(jié)點無需直接連接,，在兩個距離遠而無法直接通信的節(jié)點之間，能夠通過中繼的方式傳送信息,。PR網絡之后改名為Ad hoc網絡,，即自組織網絡。還有一些與Ad hoc網絡技術相關的研究項目獲得資助,，包括可生存自適應網絡(SURAN),、低成本報文無線電(LCR)、可生存通信網絡(SCN),、戰(zhàn)術因特網和近期無線電(NTDR)等[2],，這些網絡的研究成果為自組織應急通信網絡的研究奠定了重要的基礎。

自組織應急通信網絡是應用自組織網絡技術構造滿足應急通信需求的網絡,。自組織應急通信網指在緊急情況下不需要依靠既有的網絡基礎設施,，利用具備自組織網絡能力的通信節(jié)點，快速地組建通信網絡,，提供應急通信能力的網絡,。這個網絡由一組帶有無線收發(fā)裝置的可移動節(jié)點組成無中心網絡；是可以不依賴人為操作的自組織,、自愈合的網絡,。網絡中的各個節(jié)點相互協(xié)作，實現(xiàn)信息交換和服務共享,。由于自組織應急通信網絡獨特的組網方式,，網絡具有6個顯著特點：網絡拓撲結構動態(tài)變化、自組織無中心、多跳通信,、節(jié)點處理能力和能源受限,、無線傳輸帶寬受限、通信安全面臨挑戰(zhàn)[3],。

另一方面,，自組織應急通信網絡也具備了高可靠性、靈活性和低成本的特點,；網絡中多個通信路徑和自動路徑配置成為可能,。網絡中每個節(jié)點都兼有主機和路由器兩種功能：作為主機節(jié)點運行各種用戶程序，作為路由器節(jié)點運行網絡配置的路由協(xié)議,。在通信過程中,，如果網絡或環(huán)境發(fā)生變化，網絡中的節(jié)點則協(xié)同工作,，節(jié)點自動地重新配置,，為所傳遞的信息尋找最合適的有效路徑。因此,，自組織應急通信網絡重要的能力就是自動快速組網和通信,。

第三代移動通信協(xié)作項目(3GPP)、歐洲通信標準化組織(ETSI)和互聯(lián)網工程任務組(IETF)等標準化組織都在自組織應急通信網絡方面展開了研究,，并制訂了相關的標準[4-5],。IETF專門設立了一個移動自組織網絡研究課題組(MANET)，針對無線自組織多跳網絡開發(fā)基于IP的路由協(xié)議,，使IP協(xié)議擴展到自組織組網的無線網絡,；3GPP和IETF在自組織網絡節(jié)點接入和自優(yōu)化等方面制訂了標準。它們的區(qū)別在于,，3GPP規(guī)定標準的使用環(huán)境為全球無線接入網絡(UTRAN)和演進通用陸地無線接入網絡(E-UTRAN),，而ETSI標準適用環(huán)境為SP-42、SP-46,?？梢钥吹剑P于自組織應急通信網絡標準還沒有制訂出統(tǒng)一的,、協(xié)調一致的標準,。

本文為解決出現(xiàn)突發(fā)事件后無線自組織應急通信網絡的快速組網問題，提出使用“時間關鍵”組網技術,。“時間關鍵”源于軍用戰(zhàn)術通信網絡中從發(fā)現(xiàn)目標、定位目標,、直到攻擊目標的時間限制要素,。根據(jù)突發(fā)事件的等級，制訂從網絡建立需求提出，網絡組建,，網絡節(jié)點入網和認證,，網絡通信啟動，直至移動節(jié)點全部入網的時間限制,。本文針對時間關鍵的入網過程中的機制,、入網流程、入網協(xié)議和消息等方面,，對這個過程中出現(xiàn)的節(jié)點沖突問題進行分析,，提出相應的入網管理方法。

2 入網過程

入網過程是無線自組織網絡組網的重要環(huán)節(jié),，節(jié)點入網可能在網絡的初始化或新節(jié)點的加入兩種情況發(fā)生,。入網過程中入網流程和入網協(xié)議是兩個重要的內容。為了滿足“時間關鍵”組網的要求,，首要的任務是標準化入網流程,。下面通過一個新節(jié)點按照網絡的特性，快速加入到網絡中的控制過程,，認識入網算法和管理功能,。

2.1 標準入網流程

無線自組織網絡中的節(jié)點入網流程是數(shù)據(jù)鏈路層的MAC子層的一個流程。在GSM,、CDMA網絡中規(guī)定了標準入網流程,。在IEEE 802.16d[6]和MIL-STD-188-220[7]中，分別定義了Ad hoc模式下的入網流程,。入網流程主要包括：網絡同步,、能力交換、認證注冊等,。各個無線自組織網絡基本流程是相似的,，因此參考IEEE 802.16d中的Mesh模式，本文定義并且描述了一個新節(jié)點在無線自組織應急通信網絡中的入網流程,。

2.2 入網協(xié)議和消息

在入網過程中新節(jié)點入網需要用到的兩個消息：一個是MSH-NCFG,，另一個是MSH-NENT。MSH-NCFG消息由網絡中的節(jié)點發(fā)出,，為相鄰節(jié)點提供了基本的通信信息,，在網絡中的節(jié)點都應該按照一定方式轉發(fā)MSH-NCFG消息。MSH-NENT消息是為新節(jié)點獲取同步,、進行實體初始化,、加入網絡提供方法的。

2.3 入網過程

入網流程主要包括網絡同步,、能力交換,、認證注冊等,。每個無線Ad hoc網絡的入網流程基本一致。

一個新節(jié)點來到網絡時,，首先通過監(jiān)聽到的鄰居節(jié)點發(fā)送的MSH-NCFG消息來獲得大致的網絡同步及相關網絡參數(shù),；該新節(jié)點根據(jù)隨后監(jiān)聽到的鄰居節(jié)點的MSH-NCFG消息建立一個物理鄰居列表，此時完成了網絡的大致同步,；然后,，該新節(jié)點依據(jù)“最易進行精確同步”的原則，從建立的物理鄰居列表中選擇一個合適的候選代理節(jié)點作為入網請求轉發(fā)節(jié)點,；該新節(jié)點通過競爭獲得一個發(fā)送機會,，向候選節(jié)點發(fā)送包含候選節(jié)點ID的入網請求消息(MSH-NENT)。

當候選節(jié)點收到請求消息時,，判斷是否接受這個請求,。如果不接受，則回復MSH-NCFG: NetEntryReject消息,；如果接受,，則回復MSH-NCFG:NetEntryOpen消息，候選節(jié)點變?yōu)樾鹿?jié)點的代理節(jié)點,。新的代理節(jié)點所發(fā)送的MSH-NCFG:NetEntryOpen中包含時延信息用以幫助新節(jié)點完成精確同步,，并為新節(jié)點開放一個臨時的通信調度支持資源。新節(jié)點利用代理提供的調度資源進一步執(zhí)行能力交換,、認證程序和注冊程序,。完成上述程序后，新節(jié)點通知代理,；代理則釋放臨時調度支持資源,，并給新節(jié)點發(fā)送確認消息。以后新節(jié)點就可在網絡中正常工作,。

上述過程參考了IEEE 802.16標準的入網流程,，MIL-STD-188-220協(xié)議也規(guī)定了Ad hoc模式下的入網流程。IEEE 802.16WG下的標準IEEE 802.16e考慮了移動性管理[8],。TGm任務組已經發(fā)布了相應的需求文件SRD,，在802.16m PAR中還明確了要滿足IMT-Advanced需求?？梢灶A期,，IEEE 802.16m標準一旦完成，將對自組織應急通信網絡的發(fā)展和研究起到很大的促進作用,。

2.4 需要解決的問題

從無線自組織應急通信網絡節(jié)點入網過程看,，存在幾個需要研究解決的問題。

(1)新節(jié)點為了加入到既有的網絡中,，首先要監(jiān)聽可以收到的相鄰節(jié)點的網絡配置消息,。而結束這個監(jiān)聽過程的條件是重復收到從一個相鄰節(jié)點發(fā)來的網絡配置消息,。由此，結束這個監(jiān)聽過程取決于可能的相鄰節(jié)點重復發(fā)送網絡配置消息的間隔時間,。

(2)新節(jié)點在選擇候選擔保節(jié)點時，選擇最容易與新節(jié)點進行精確同步的節(jié)點,。這僅僅考慮了物理時間同步關系,，沒有對節(jié)點的通信能力給與足夠的考慮。

(3)IEEE 802.16d的Mesh網絡,，存在著基站設備,。新節(jié)點通信能力、認證程序和注冊程序都通過基站完成,。MIL-STD-188-220B/C/D標準中定義了入網過程,，但是某些無線自組織網絡種中沒有給出節(jié)點入網過程的描述。在沒有基礎網絡結構的無線自組織應急通信網絡中,，由于新節(jié)點能力很不同,，認證過程和注冊程序應該有所不同。

(4)在新節(jié)點入網檢測的過程中,，引入認知無線網絡技術,，對新節(jié)點感知相鄰節(jié)點、選擇擔保節(jié)點,、選擇信息交換時機,，以及認證和注冊過程都可以產生影響。

3 入網管理

依據(jù)上述自組織應急通信網絡節(jié)點入網過程,，一個新節(jié)點加入網絡需要占用3個網絡接入時機發(fā)送MSH-NENT消息,，而候選/代理節(jié)點則需要占用3個網絡配置時機發(fā)送MSH-NCFG消息來響應。

新節(jié)點占用網絡接入時機是通過競爭的方式實現(xiàn)的,。在IEEE 802.16協(xié)議中沒有明確說明采用什么樣的競爭方法,。為保證候選/代理節(jié)點獲得一個網絡配置時機，在IEEE 802.16協(xié)議中給出了一個沖突避免的接入方法,，該方法可以保證在網的節(jié)點發(fā)送MSH-NCFG消息時不會產生沖突,。該方法的原理就是讓所有成員節(jié)點考慮自己兩跳以內節(jié)點的MSH-NCFG更新時間，選擇出一個網絡配置時機,，使之不會跟兩跳內所有節(jié)點有沖突,，再發(fā)送自己的MSH-NCFG消息。

在入網流程中上述兩個時機的占用方式,，對不同場景下的新節(jié)點接入性能會有很大的影響,。下面分兩種場景來說明問題，一種是在普通模式下,，即節(jié)點的通信范圍都比較小的時候,；另一種是在廣域模式下,，即節(jié)點的通信范圍比較大的時候。本文通過對兩種模式下的特性進行分析,，得出入網管理方法,。

 3.1 普通Mesh模式入網

雖然IEEE 802.16協(xié)議中沒有特別規(guī)定Mesh模式下節(jié)點的通信范圍，但是參照IEEE 802.16協(xié)議的PMP模式(小區(qū)模式)來估算,，節(jié)點的覆蓋范圍為十幾公里,。這種場景下，網絡的拓撲會比較復雜,，跳數(shù)會增加,。首先考慮以下情景，如圖1所示,。

假設節(jié)點A,、B都為成員節(jié)點，即已加入了網絡,，并且A,、B節(jié)點都不處于各自的通信范圍內，而且彼此也不是對方的兩跳鄰居節(jié)點,，因此節(jié)點A,、B可以選擇網絡控制子幀的同一個網絡配置時機來發(fā)送自己的MSH-NCFG消息，而彼此不會產生影響,。這時一個新的節(jié)點C要加入網絡,，如圖2所示。

由于節(jié)點C的到來,，使得原來沒有關系的節(jié)點A和B現(xiàn)在變成了兩跳鄰居,。這時假設節(jié)點C在某個網絡接入時機成功地向節(jié)點A發(fā)送MSH-NENT請求消息。節(jié)點A接受了這個請求消息后,，在自己的網絡配置時機發(fā)送MSH-NCFG消息進行應答,。但是，由于節(jié)點B不知道節(jié)點A已經變成了兩跳鄰居,，所以節(jié)點B也會在同一個網絡配置時機發(fā)送自己的MSH-NCFG消息,，這樣節(jié)點C就不能正確地接收到節(jié)點A的應答，所以節(jié)點C在超時后會重發(fā)請求消息,。在節(jié)點密度比較大的情況下,，這種類型的沖突會很多，造成很大的網絡接入延遲,。這個問題的解決方法很重要,，文獻[9]中給出了一種方法。

3.2 廣域Mesh模式入網

在廣域模式下,，節(jié)點的通信范圍比較大,，基本上不會產生普通Mesh模式下存在的問題,，可是會帶來新問題。新問題的描述如圖3所示,。

節(jié)點A是已有的網絡成員,，在某一時刻節(jié)點B和節(jié)點C同時到達網絡并完成了網絡信號同步。對3個節(jié)點而言,，他們通信范圍都比較大,，都處在彼此的通信范圍內。這時如果節(jié)點B和節(jié)點C同時向節(jié)點A發(fā)送入網請求MSH-NENT消息,，則會導致沖突。尤其在大量節(jié)點要加入網絡的時候,，這種沖突會更加頻繁,，問題更加明顯。

3.3 管理方法

由于無線自組織應急通信網絡的應用場景就是要求節(jié)點快速進入網絡,，所以在網絡節(jié)點入網發(fā)生沖突時,，需要有效的沖突解決算法，以保障快速解決沖突,，完成節(jié)點入網,。

在用于競爭/沖突的網絡資源管理中的應用中已經表明，退避算法是一種解決沖突的有效方法,。針對自組織應急通信網絡而言,，如果在已知有大量入網的節(jié)點加入網絡，并且已知這些節(jié)點信息的時候,，選用集中式的靜態(tài)配置的入網管理方法,，將能夠讓所有節(jié)點以完全無沖突的、最小時延的方式迅速加入網絡,。只是這種方式的條件太過苛刻,，因此本文提出大規(guī)模的節(jié)點分布式入網管理方法。

分布式入網的基本思想是基于窗口選擇的退避機制,，即給定一個隨機窗口,。在這個窗口中選擇一個隨機數(shù)，以這個隨機數(shù)為基礎,，每當檢測到網絡的一個空閑時隙,，則隨機數(shù)值減1。當隨機數(shù)減到0時,，節(jié)點就認為這時可以發(fā)送,。從這個過程中可以看到，如何選擇隨機窗口,，如何在隨機窗口中選擇出一個隨機數(shù),，當隨機數(shù)減為0,，進行發(fā)送時如何解決沖突是影響算法性能的幾個重要因素。

在退避算法中,，SW為選擇窗口,，WC為窗口計數(shù)器，RN為隨機數(shù)字,，F(xiàn)T為失敗次數(shù),，ST為成功次數(shù)。文獻[9-10]對算法性能進行了分析,。

假設初始節(jié)點總數(shù)為N,，窗口的選擇系數(shù)為x，則窗口的長度L=xN,，在xN長度內N個節(jié)點采用均勻隨機過程接入,，產生沖突的概率記為函數(shù)：Pc(x)=沖突的次數(shù)/窗口總數(shù)。在xN長度內N個節(jié)點采用均勻隨機分布過程接入,，成功傳遞的概率記為函數(shù)：Ps(x)=成功傳送次數(shù)/傳送總次數(shù),。設時隙長度為σ，節(jié)點的繁忙感應時間和沖突檢測時間都為σ,，節(jié)點入網請求的傳遞過程的服務時間長度假設為4σ,。則第n輪的入網時間=x(1+Pc(x))Nσ/Ps(x)+4Nσ+Δ。

T(x)為最優(yōu)窗口函數(shù),。將數(shù)值代入T(x)得到的量化結果如圖4所示,。

從圖4中看到，當x=1.4時,，T(x)取極小值,。其意義是當窗口系數(shù)選擇一個合適的數(shù)值時，可以保證節(jié)點加入到網絡所使用的時機數(shù)最小,。時機數(shù)小就意味著沖突的數(shù)量少,，節(jié)點加入到網絡的時延越小，節(jié)點入網的效率就越高,。所以,，面對不同規(guī)模的無線自組織網絡，應該選擇適合的參數(shù),，以優(yōu)化入網管理效率,。

4 自組織應急通信網現(xiàn)階段面臨的問題及未來發(fā)展趨勢

無線自組織應急通信網絡相關技術發(fā)展到今天仍然存在許多問題，包括：網絡設備,、網絡安全以及網絡管理等,；其中入網過程管理是基礎也是關鍵，有關入網問題將成為今后自組織應急通信網絡研究的重要方向。

由于無線自組織應急通信網絡自身的特點使得網絡具有很大的特殊性,，也就面臨普通網絡所不存在的很多問題,，諸如終端能量受限、CPU能力受限,、資源受限等使得網絡節(jié)點不選擇或者無法執(zhí)行復雜的算法,。為了達到自組織網絡安全要求和實現(xiàn)入網過程的快速認證，需要一種算法簡單而安全的加密算法,。因此,，適用于自組織應急通信網絡的快速安全的認證機制將成為今后的重要研究方向。

在不同的應急網絡中對節(jié)點的安全性,、入網的快速與否要求不同,。如戰(zhàn)場環(huán)境在節(jié)點入網時必須要保障節(jié)點的可信，否則將影響整個網絡的安全,，這就要求保障入網節(jié)點的高可信度,。對于災難現(xiàn)場，多數(shù)是為了搜集現(xiàn)場信息,，只要能保障數(shù)據(jù)的正常傳送即可，對安全性要求次之,，對入網節(jié)點的可信度要求相對較低,。由此可以看到，針對自組織應急通信網絡需要一套標準,，對不同的應急通信場景,，定義相應的可信等級，統(tǒng)一地劃分入網節(jié)點的可信等級,。這些將成為標準化組網的重要課題,。

5 參考文獻
[1] 魏更宇, 張冬梅, 王樅, 等. 時間關鍵組網技術分析 [J]. 電信技術, 2009(12):24-26.
[2] 方旭明. 移動Ad hoc網絡研究與發(fā)展現(xiàn)狀 [J]. 數(shù)據(jù)通信, 2003(4):15-18.
[3] 劉勇, 陳劍波, 齊開悅. Ad hoc網絡的安全機制 [J]. 信息安全與通信保密, 2005(9):66-69.
[4] 王海濤. Ad hoc網絡的應用現(xiàn)狀和發(fā)展趨勢 [J]. 通信技術政策研究, 2010(1):32-42.
[5] 焦慧穎, 董曉魯. IEEE802.16m標準的最新進展 [J]. 世界電信, 2007 (11):52-55.
[6] IEEE 802.16d. IEEE Standard for Local and Metropolitan Area Networks, Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems [S]. 2004.
[7] MIL-STD-188-220D. Department of Defense Interface Standard Digital Message Transfer Device Subsystems [S]. 2005.
[8] IEEE 802.16e. IEEE Standard for Local and Metropolitan Area Networks, Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems [S]. 2006.
[9] WANG Shieyuan, LIN Chihche, FANG Kuhan. Facilitating the Network Entry and Link Establishment Processes of IEEE 802.16 Mesh Networks [C]//Proceedings of the IEEE Wireless Communications and Networking Conference(WCNC’07), Mar 11-15, 2007, Hong Kong, China. Piscataway, NJ, USA: IEEE, 2007: 1842-1847.
[10] BIANCHI G. Performance Analysis of the IEEE 802.11 Distributed Coordination Function [J]. IEEE Journal on Selected Areas in Communications, 2000,18(3): 535-547.

魏更宇，日本東北學院大學工學博士,，北京郵電大學計算機學院副教授,，長期從事網絡與軟件安全、自組織網絡,、應急通信,、P2P技術等方面的研究，已發(fā)表SCI/EI檢索論文20余篇,。

楊茗名,，北京郵電大學計算機學院在讀碩士研究生。