英文摘要: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
基金項目：國家高技術研究發展(“863”)計劃(2008AA011004)
目前，公共安全機構和組織在應急處理和災害響應時，越來越多地采用無線技術提供高效的命令、控制和通信保障。近年來多次緊急事件和災害顯示，出現緊急事件和發生災害的時間、地點和規模難以預測。加之當有災害事件發生時，既有的通信設施和手段往往遭到破壞，依賴既有的網絡基礎設施來進行應急通信的質量需求是無法保障的[1]。因此，具有分布式、移動性、擴充性、自適應性和靈活性的無線自組織網絡成為進行應急通信組網的重要手段。
1 自組織應急通信網絡概述
自組織(Ad hoc)網絡是一種多跳的自治系統。1968年在美國建立的ALOHA網絡和在1973年提出的PR網絡就是自組織網絡的原型。其實ALOHA是一種單跳網絡，需要固定的基站，網絡中的每個節點之間都可直接連接互相通信。而PR網絡的提出，才是真正意義上地實現了多跳網絡。PR網絡中各節點無需直接連接，在兩個距離遠而無法直接通信的節點之間，能夠通過中繼的方式傳送信息。PR網絡之后改名為Ad hoc網絡，即自組織網絡。還有一些與Ad hoc網絡技術相關的研究項目獲得資助，包括可生存自適應網絡(SURAN)、低成本報文無線電(LCR)、可生存通信網絡(SCN)、戰術因特網和近期無線電(NTDR)等[2]，這些網絡的研究成果為自組織應急通信網絡的研究奠定了重要的基礎。
自組織應急通信網絡是應用自組織網絡技術構造滿足應急通信需求的網絡。自組織應急通信網指在緊急情況下不需要依靠既有的網絡基礎設施，利用具備自組織網絡能力的通信節點，快速地組建通信網絡，提供應急通信能力的網絡。這個網絡由一組帶有無線收發裝置的可移動節點組成無中心網絡；是可以不依賴人為操作的自組織、自愈合的網絡。網絡中的各個節點相互協作，實現信息交換和服務共享。由于自組織應急通信網絡獨特的組網方式，網絡具有6個顯著特點：網絡拓撲結構動態變化、自組織無中心、多跳通信、節點處理能力和能源受限、無線傳輸帶寬受限、通信安全面臨挑戰[3]。
另一方面，自組織應急通信網絡也具備了高可靠性、靈活性和低成本的特點；網絡中多個通信路徑和自動路徑配置成為可能。網絡中每個節點都兼有主機和路由器兩種功能：作為主機節點運行各種用戶程序，作為路由器節點運行網絡配置的路由協議。在通信過程中，如果網絡或環境發生變化，網絡中的節點則協同工作，節點自動地重新配置，為所傳遞的信息尋找最合適的有效路徑。因此，自組織應急通信網絡重要的能力就是自動快速組網和通信。
第三代移動通信協作項目(3GPP)、歐洲通信標準化組織(ETSI)和互聯網工程任務組(IETF)等標準化組織都在自組織應急通信網絡方面展開了研究，并制訂了相關的標準[4-5]。IETF專門設立了一個移動自組織網絡研究課題組(MANET)，針對無線自組織多跳網絡開發基于IP的路由協議，使IP協議擴展到自組織組網的無線網絡；3GPP和IETF在自組織網絡節點接入和自優化等方面制訂了標準。它們的區別在于，3GPP規定標準的使用環境為全球無線接入網絡(UTRAN)和演進通用陸地無線接入網絡(E-UTRAN)，而ETSI標準適用環境為SP-42、SP-46。可以看到，關于自組織應急通信網絡標準還沒有制訂出統一的、協調一致的標準。
本文為解決出現突發事件后無線自組織應急通信網絡的快速組網問題，提出使用“時間關鍵”組網技術。“時間關鍵”源于軍用戰術通信網絡中從發現目標、定位目標、直到攻擊目標的時間限制要素。根據突發事件的等級，制訂從網絡建立需求提出，網絡組建，網絡節點入網和認證，網絡通信啟動，直至移動節點全部入網的時間限制。本文針對時間關鍵的入網過程中的機制、入網流程、入網協議和消息等方面，對這個過程中出現的節點沖突問題進行分析，提出相應的入網管理方法。
2 入網過程
入網過程是無線自組織網絡組網的重要環節，節點入網可能在網絡的初始化或新節點的加入兩種情況發生。入網過程中入網流程和入網協議是兩個重要的內容。為了滿足“時間關鍵”組網的要求，首要的任務是標準化入網流程。下面通過一個新節點按照網絡的特性，快速加入到網絡中的控制過程，認識入網算法和管理功能。
2.1 標準入網流程
無線自組織網絡中的節點入網流程是數據鏈路層的MAC子層的一個流程。在GSM、CDMA網絡中規定了標準入網流程。在IEEE 802.16d[6]和MIL-STD-188-220[7]中，分別定義了Ad hoc模式下的入網流程。入網流程主要包括：網絡同步、能力交換、認證注冊等。各個無線自組織網絡基本流程是相似的，因此參考IEEE 802.16d中的Mesh模式，本文定義并且描述了一個新節點在無線自組織應急通信網絡中的入網流程。
2.2 入網協議和消息
在入網過程中新節點入網需要用到的兩個消息：一個是MSH-NCFG，另一個是MSH-NENT。MSH-NCFG消息由網絡中的節點發出，為相鄰節點提供了基本的通信信息，在網絡中的節點都應該按照一定方式轉發MSH-NCFG消息。MSH-NENT消息是為新節點獲取同步、進行實體初始化、加入網絡提供方法的。
2.3 入網過程
入網流程主要包括網絡同步、能力交換、認證注冊等。每個無線Ad hoc網絡的入網流程基本一致。
一個新節點來到網絡時，首先通過監聽到的鄰居節點發送的MSH-NCFG消息來獲得大致的網絡同步及相關網絡參數；該新節點根據隨后監聽到的鄰居節點的MSH-NCFG消息建立一個物理鄰居列表，此時完成了網絡的大致同步；然后，該新節點依據“最易進行精確同步”的原則，從建立的物理鄰居列表中選擇一個合適的候選代理節點作為入網請求轉發節點；該新節點通過競爭獲得一個發送機會，向候選節點發送包含候選節點ID的入網請求消息(MSH-NENT)。
當候選節點收到請求消息時，判斷是否接受這個請求。如果不接受，則回復MSH-NCFG: NetEntryReject消息；如果接受，則回復MSH-NCFG:NetEntryOpen消息，候選節點變為新節點的代理節點。新的代理節點所發送的MSH-NCFG:NetEntryOpen中包含時延信息用以幫助新節點完成精確同步，并為新節點開放一個臨時的通信調度支持資源。新節點利用代理提供的調度資源進一步執行能力交換、認證程序和注冊程序。完成上述程序后，新節點通知代理；代理則釋放臨時調度支持資源，并給新節點發送確認消息。以后新節點就可在網絡中正常工作。
上述過程參考了IEEE 802.16標準的入網流程，MIL-STD-188-220協議也規定了Ad hoc模式下的入網流程。IEEE 802.16WG下的標準IEEE 802.16e考慮了移動性管理[8]。TGm任務組已經發布了相應的需求文件SRD，在802.16m PAR中還明確了要滿足IMT-Advanced需求。可以預期，IEEE 802.16m標準一旦完成，將對自組織應急通信網絡的發展和研究起到很大的促進作用。
2.4 需要解決的問題
從無線自組織應急通信網絡節點入網過程看，存在幾個需要研究解決的問題。
(1)新節點為了加入到既有的網絡中，首先要監聽可以收到的相鄰節點的網絡配置消息。而結束這個監聽過程的條件是重復收到從一個相鄰節點發來的網絡配置消息。由此，結束這個監聽過程取決于可能的相鄰節點重復發送網絡配置消息的間隔時間。
(2)新節點在選擇候選擔保節點時，選擇最容易與新節點進行精確同步的節點。這僅僅考慮了物理時間同步關系，沒有對節點的通信能力給與足夠的考慮。
(3)IEEE 802.16d的Mesh網絡，存在著基站設備。新節點通信能力、認證程序和注冊程序都通過基站完成。MIL-STD-188-220B/C/D標準中定義了入網過程，但是某些無線自組織網絡種中沒有給出節點入網過程的描述。在沒有基礎網絡結構的無線自組織應急通信網絡中，由于新節點能力很不同，認證過程和注冊程序應該有所不同。
(4)在新節點入網檢測的過程中，引入認知無線網絡技術，對新節點感知相鄰節點、選擇擔保節點、選擇信息交換時機，以及認證和注冊過程都可以產生影響。
3 入網管理
依據上述自組織應急通信網絡節點入網過程，一個新節點加入網絡需要占用3個網絡接入時機發送MSH-NENT消息，而候選/代理節點則需要占用3個網絡配置時機發送MSH-NCFG消息來響應。
新節點占用網絡接入時機是通過競爭的方式實現的。在IEEE 802.16協議中沒有明確說明采用什么樣的競爭方法。為保證候選/代理節點獲得一個網絡配置時機，在IEEE 802.16協議中給出了一個沖突避免的接入方法，該方法可以保證在網的節點發送MSH-NCFG消息時不會產生沖突。該方法的原理就是讓所有成員節點考慮自己兩跳以內節點的MSH-NCFG更新時間，選擇出一個網絡配置時機，使之不會跟兩跳內所有節點有沖突，再發送自己的MSH-NCFG消息。
在入網流程中上述兩個時機的占用方式，對不同場景下的新節點接入性能會有很大的影響。下面分兩種場景來說明問題，一種是在普通模式下，即節點的通信范圍都比較小的時候；另一種是在廣域模式下，即節點的通信范圍比較大的時候。本文通過對兩種模式下的特性進行分析，得出入網管理方法。
3.1 普通Mesh模式入網
雖然IEEE 802.16協議中沒有特別規定Mesh模式下節點的通信范圍，但是參照IEEE 802.16協議的PMP模式(小區模式)來估算，節點的覆蓋范圍為十幾公里。這種場景下，網絡的拓撲會比較復雜，跳數會增加。首先考慮以下情景，如圖1所示。
假設節點A、B都為成員節點，即已加入了網絡，并且A、B節點都不處于各自的通信范圍內，而且彼此也不是對方的兩跳鄰居節點，因此節點A、B可以選擇網絡控制子幀的同一個網絡配置時機來發送自己的MSH-NCFG消息，而彼此不會產生影響。這時一個新的節點C要加入網絡，如圖2所示。
由于節點C的到來，使得原來沒有關系的節點A和B現在變成了兩跳鄰居。這時假設節點C在某個網絡接入時機成功地向節點A發送MSH-NENT請求消息。節點A接受了這個請求消息后，在自己的網絡配置時機發送MSH-NCFG消息進行應答。但是，由于節點B不知道節點A已經變成了兩跳鄰居，所以節點B也會在同一個網絡配置時機發送自己的MSH-NCFG消息，這樣節點C就不能正確地接收到節點A的應答，所以節點C在超時后會重發請求消息。在節點密度比較大的情況下，這種類型的沖突會很多，造成很大的網絡接入延遲。這個問題的解決方法很重要，文獻[9]中給出了一種方法。
3.2 廣域Mesh模式入網
在廣域模式下，節點的通信范圍比較大，基本上不會產生普通Mesh模式下存在的問題，可是會帶來新問題。新問題的描述如圖3所示。
節點A是已有的網絡成員，在某一時刻節點B和節點C同時到達網絡并完成了網絡信號同步。對3個節點而言，他們通信范圍都比較大，都處在彼此的通信范圍內。這時如果節點B和節點C同時向節點A發送入網請求MSH-NENT消息，則會導致沖突。尤其在大量節點要加入網絡的時候，這種沖突會更加頻繁，問題更加明顯。
3.3 管理方法
由于無線自組織應急通信網絡的應用場景就是要求節點快速進入網絡，所以在網絡節點入網發生沖突時，需要有效的沖突解決算法，以保障快速解決沖突，完成節點入網。
在用于競爭/沖突的網絡資源管理中的應用中已經表明，退避算法是一種解決沖突的有效方法。針對自組織應急通信網絡而言，如果在已知有大量入網的節點加入網絡，并且已知這些節點信息的時候，選用集中式的靜態配置的入網管理方法，將能夠讓所有節點以完全無沖突的、最小時延的方式迅速加入網絡。只是這種方式的條件太過苛刻，因此本文提出大規模的節點分布式入網管理方法。
分布式入網的基本思想是基于窗口選擇的退避機制，即給定一個隨機窗口。在這個窗口中選擇一個隨機數，以這個隨機數為基礎，每當檢測到網絡的一個空閑時隙，則隨機數值減1。當隨機數減到0時，節點就認為這時可以發送。從這個過程中可以看到，如何選擇隨機窗口，如何在隨機窗口中選擇出一個隨機數，當隨機數減為0，進行發送時如何解決沖突是影響算法性能的幾個重要因素。
在退避算法中，SW為選擇窗口，WC為窗口計數器，RN為隨機數字，FT為失敗次數，ST為成功次數。文獻[9-10]對算法性能進行了分析。
假設初始節點總數為N，窗口的選擇系數為x，則窗口的長度L=xN，在xN長度內N個節點采用均勻隨機過程接入，產生沖突的概率記為函數：Pc(x)=沖突的次數/窗口總數。在xN長度內N個節點采用均勻隨機分布過程接入，成功傳遞的概率記為函數：Ps(x)=成功傳送次數/傳送總次數。設時隙長度為σ，節點的繁忙感應時間和沖突檢測時間都為σ，節點入網請求的傳遞過程的服務時間長度假設為4σ。則第n輪的入網時間=x(1+Pc(x))Nσ/Ps(x)+4Nσ+Δ。
T(x)為最優窗口函數。將數值代入T(x)得到的量化結果如圖4所示。
從圖4中看到，當x=1.4時，T(x)取極小值。其意義是當窗口系數選擇一個合適的數值時，可以保證節點加入到網絡所使用的時機數最小。時機數小就意味著沖突的數量少，節點加入到網絡的時延越小，節點入網的效率就越高。所以，面對不同規模的無線自組織網絡，應該選擇適合的參數，以優化入網管理效率。
4 自組織應急通信網現階段面臨的問題及未來發展趨勢
無線自組織應急通信網絡相關技術發展到今天仍然存在許多問題，包括：網絡設備、網絡安全以及網絡管理等；其中入網過程管理是基礎也是關鍵，有關入網問題將成為今后自組織應急通信網絡研究的重要方向。
由于無線自組織應急通信網絡自身的特點使得網絡具有很大的特殊性，也就面臨普通網絡所不存在的很多問題，諸如終端能量受限、CPU能力受限、資源受限等使得網絡節點不選擇或者無法執行復雜的算法。為了達到自組織網絡安全要求和實現入網過程的快速認證，需要一種算法簡單而安全的加密算法。因此，適用于自組織應急通信網絡的快速安全的認證機制將成為今后的重要研究方向。
在不同的應急網絡中對節點的安全性、入網的快速與否要求不同。如戰場環境在節點入網時必須要保障節點的可信，否則將影響整個網絡的安全，這就要求保障入網節點的高可信度。對于災難現場，多數是為了搜集現場信息，只要能保障數據的正常傳送即可，對安全性要求次之，對入網節點的可信度要求相對較低。由此可以看到，針對自組織應急通信網絡需要一套標準，對不同的應急通信場景，定義相應的可信等級，統一地劃分入網節點的可信等級。這些將成為標準化組網的重要課題。
5 參考文獻
[1] 魏更宇, 張冬梅, 王樅, 等. 時間關鍵組網技術分析 [J]. 電信技術, 2009(12):24-26.
[2] 方旭明. 移動Ad hoc網絡研究與發展現狀 [J]. 數據通信, 2003(4):15-18.
[3] 劉勇, 陳劍波, 齊開悅. Ad hoc網絡的安全機制 [J]. 信息安全與通信保密, 2005(9):66-69.
[4] 王海濤. Ad hoc網絡的應用現狀和發展趨勢 [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技術等方面的研究，已發表SCI/EI檢索論文20余篇。
楊茗名，北京郵電大學計算機學院在讀碩士研究生。