基于時隙泛洪的無路由移動無線自組網協議及其擴展方法*

賴增桂，蔡雪梅，李默嘉

0 引 言

移動無線自組網（MANET）可滿足無基礎設施情況下的通信需求，是無線通信領域中的熱點研究問題[1-2]，在應急、軍事等特殊領域具有廣泛的應用前景。但是，傳統的MANET網絡都具有復雜龐大的協議體系，尤其是其路由協議，給原本帶寬較窄、鏈路不穩定的無線傳輸鏈路造成了較大負擔。當網絡動態性較大（拓撲變化快）時，路由協議的控制開銷會急劇增加，從而增加網絡擁塞度，降低網絡工作效率，導致網絡不能夠較好地為用戶提供穩定可靠的通信服務。

針對龐大的自組網協議體系尤其是路由協議導致額外無線傳輸開銷的問題，本文提出一種無需單獨的路由協議，基于鏈路層時隙泛洪的移動無線自組網的網絡協議，提出了一種提升信道利用率、增加用戶容量的優化方法，以及基于該協議的通用自組網協議擴展方法。

1 協議基本原理

1.1 要求及假設

本文設計的協議適用的無線信道需要具備以下特點和能力：

（1）無線信道采用同步工作方式，其時鐘同步可采用外時鐘同步，如高精度高穩時鐘、衛星定位系統時鐘（如北斗、GPS）等，或者借助物理層方法進行互同步或主從同步，如基于同步頭和時間信息TOD的跳頻同步[3-4]；

（2）無線信道為全向廣播信道，在定向無線信道下的協議擴展需進一步研究；

（3）無線信道設備需具備足夠快的收發切換和收發處理能力，以確保網絡性能；

（4）無線信道設備需要具備能夠接收處理并利用多徑信號的能力。

為后續描述準確方便，對MANET網絡的性能進行如下假設：

（1）網絡支持的最大用戶數為M，每一個用戶均有一個[0，M-1]內唯一的標識ID；

（2）網絡支持的最大中繼跳數為N。

1.2 幀結構

網絡的最小時間單元為時隙，所有時隙的長度均一致且固定，N個時隙構成一個時幀，M個時幀構成一個時元。一個時元是網絡運行的一個基本周期，其幀結構如圖1所示。

圖1 幀結構

1.3 時幀/時隙的分配與使用

時幀采用固定為每個用戶分配的方式。網絡內的每個用戶節點都按照標識ID分別分配1個時幀作為自己的時幀，如標識ID為0的用戶分配0號時幀。用戶將自己時幀內的第0時隙作為自己的源信息（該用戶節點發起的信息）發送時隙。所有的用戶節點都按照如下方法使用時幀和時隙：

（1）當某用戶節點有源信息需要發送時，在該用戶節點的時幀的0時隙（也就是源信息發送時隙）對源信息進行發送，發送后該節點在本時幀周期內的后續時隙進入休眠狀態（不再接收處理和發送任何信息數據），直到下一時幀周期開始才喚醒（重新開始收發工作）；

（2）當一個節點在不屬于自己的時幀內的n（n＜N-1）時隙收到了信息，則需判斷該信息的目的節點是否為本節點。若為本節點，則進行接收處理；否則，該節點立即在該時幀內的n+1時隙轉發該信息。完成轉發后，該節點在本時幀周期內的后續時隙進入休眠狀態，直到下一時幀周期開始才喚醒；

（3）當一個節點在不屬于自己的時幀內的n（n＜N-1）時隙收到了信息，則判斷該信息的目的節點是否為本節點，若為本節點，則進行接收處理，否則丟棄該信息。

在上述時幀/時隙的使用過程中，信息的接收和轉發行為之間，涉及到無線信道的收發轉化時間、收發處理時延以及無線傳播時延等時延因素。為確保數據能夠正確收發和處理，需要在不同時隙間預留時隙間保護時間。時隙間保護時間越短，對網絡性能影響越小。所以，要求無線信道需具備足夠快的收發切換和收發處理能力，以確保網絡性能。

另外，在上述使用過程中會遇到如下類多徑情況。如圖2所示拓撲，當A節點有信息需要發送時，在某時隙進行了發送，B、C節點都會收到并進行轉發，D節點則會同時收到來自B、C節點轉發的信息，則D節點需要同時處理來自兩條不同路徑的相同信號，所以要求無線信道需要具備能夠接收處理并利用多徑信號的能力。

圖2 類多徑拓撲

1.4 協議總結

上述協議具有如下特點：

（1）一個時幀內每個節點最多只在某一個時隙內進行數據發送（包括源數據的發送和其他節點數據的轉發），其他時隙要么處于接收狀態要么處于休眠狀態；

（2）一個時元內某個節點只有一個時隙（也就是本節點時幀的0時隙）能夠進行本節點源數據的發送，所以在不考慮時隙間保護時間的情況下，每個節點的有效數據速率是信道速率的1/(M×N)；

（3）通過多跳基于時隙泛洪的方式，無需路由協議的支撐，任何節點發送的數據均能被N跳范圍內的目的節點正確接收。

1.5 協議性能分析計算及應用場景推薦

以信道速率R=4 Mb/s、用戶數M=16、最大支持跳數N=4計算，則單個用戶有效速率為4 Mb/s/(16×4)= 64 kb/s。假設網絡信息的傳輸時延要求為10 ms，則時元周期可設置為10 ms，時幀周期為10 ms/16= 625 μs，每個時隙為625 μs/4=156.25 μs，每個用戶節點一個時元周期內最多可傳遞4 Mb/s×156.25 μs≈640 bit（即80 Byte）數據（注：以上計算忽略時隙間保護時間）。

通過分析計算可以看出，該組網協議適用于節點分布較密集（轉發跳數少）、節點信息量較固定、節點移動性較強（網絡拓撲變化快）、對傳輸時延較敏感的場合，如分隊級別的火力協同網絡、區域范圍內的車聯網絡等。它最適合的應用業務是子網廣播，尤其是全子網的話音廣播。

2 協議性能優化措施

2.1 優化思路

前述協議的時幀/時隙的分配采用固定分配的方法，導致網絡對信道資源的利用率相對較低。同時，固定分配的方式直接限定了用戶數量，不利于網絡的擴展，無法實現少量臨時用戶的加入。此外，由于所有用戶的時幀分配都是相同的，無法滿足高優先級用戶的更高要求的通信需求。針對以上問題和不足，提出基于時隙CSMA/CA[5]方式接入的性能優化方法。

2.2 優化改進措施

時幀/時隙的分配不再針對每個用戶進行固定分配，而是所有的用戶共享所有時幀。需要使用時幀/時隙的用戶采用載波偵聽多址隨機接入/沖突避免（CSMA/CA）的方式競爭使用。當一個節點有源數據需要發送時，首先偵聽當前時幀0時隙是否空閑。若空閑，則占用該時隙發送源數據；若被占用，則隨機退避x個時幀重新偵聽0時隙進行接入發送。當一個節點在某時幀的y時隙有轉發數據需要發送時，則偵聽該時幀的y+1時隙是否空閑。如空閑，則轉發；若被占用，則監聽該時幀的y+1時隙。重復，直到占用某時隙轉發或直到該時幀的N-1時隙為止。

需要注意的是，采用時隙CSMA/CA接入方式后，CSMA接入協議固有的“隱藏終端”問題和“暴露終端”問題[6-7]將被引入。如圖2所示拓撲，若A、D節點同時發送，B、C節點均無法正確接收并轉發數據，即引入了“隱藏終端”問題。同樣，當C、D節點同時有數據發送時，則會引入“暴露終端”問題，原本可以同時發送的C、D節點由于“暴露終端”問題，導致必須進行相應的退避操作，降低信道利用率。另外，由于多跳泛洪轉發的原因，2跳甚至多跳外時幀復用后引入的“多跳隱藏終端”和“多跳暴露終端”問題也會隨之產生。但是，復雜拓撲下借助多跳泛洪轉發機制，可解決部分“隱藏終端”和“暴露終端”問題，如圖3所示拓撲。當A、D節點同時發送源數據時，雖然B、C由于沖突的原因無法在第一時間（當前時隙）正確接收并轉發，但是E節點收到A信息后進行轉發，C節點可以正確接收并轉發；D節點信息經G、F節點接收并轉發后，B節點能夠正確接收并轉發，C轉發A信息和B轉發D信息不在同一時隙，A、D的接收不會產生沖突，可以實現全網的正確傳輸。

圖3 “隱藏終端”問題解決方法

2.3 優化后性能分析

優化后，網絡開通后增加少量的用戶不再需要重新進行設計和規劃。新增加的用戶開機即可正常接入并使用網絡。同時，有更多業務傳輸需求的高優先級用戶可以占用更多的時幀用于源數據發送，提升了傳輸帶寬。

經Opnet仿真，網絡用戶數為16，每個用戶均以≤64 kb/s的速率產生業務。在協議未經優化時，網絡收發的業務量如圖4所示（“Traffic Sink.Traffic Sent(packets)”表示網絡發送的數據報文總數量，“Traffic Sink.Traffic Receibed(packets)”表示網絡接收的數據報文總數量，縱軸表示報文數量，橫軸表示仿真時間），網絡傳輸時延如圖5所示（縱軸表示每個報文的傳輸時延，橫軸表示仿真時間）。從圖4、圖5可以看出，在協議未經優化時，網絡的收發數據量保持一致，即網絡的業務遞交率達到100%，所有業務的傳輸時延均控制在10 ms以內。

圖4 固定用戶數量（16）的收發業務量

圖5 固定用戶數量（16）的傳輸時延

進行協議優化后，網絡用戶數分別設置為16、32、64、128。所有用戶以泊松分布的方式共產生≤4 Mb/s的業務。沖突時，隨機退避時間范圍固定為16個時幀周期，網絡的業務遞交率如圖6所示（不同線條表示不同用戶數情況下的業務遞交率，縱軸表示遞交概率，橫軸表示仿真時間），傳輸時延如圖7所示（四種用戶數量下的傳輸時延，縱軸表示傳輸時延，橫軸表示仿真時間）。從圖6、圖7可以看出，協議進行優化后，隨著用戶數的增加，其業務的遞交率沒有明顯變化，傳輸時延也基本保持不變（10 ms以內），即優化的協議通過犧牲較少的遞交率可以換取更多用戶的隨遇接入。

圖6 不同用戶數量的遞交率

圖7 不同用戶數量的傳輸時延

3 協議擴展

上述協議的使用范圍相對較固定，適用的場景局限于以時敏廣播通信為主的網絡。而對于業務傳輸需求較隨機的用戶組成的網絡，它的使用不夠靈活，網絡應用效率也不夠高。因此，可以針對以上協議進行擴展，以適應以隨機通信（通信的源和目的隨機、通信業務的大小隨機、通信的時間隨機）為主的網絡。將MANET網絡內較固定且時延要求敏感的組網控制信息（如路由信息、資源分配信息等）使用上述協議進行傳輸，其他資源進行靈活分配，以提升網絡應用的普適性和網絡的應用效率。

下文針對以上需求設計了一種典型的擴展協議。將第2節設計的時元作為網絡的控制時隙用作組網控制信息的傳遞，后續緊跟K個業務時隙用做業務傳輸，形成如圖8所示的幀結構。

圖8 擴展超幀結構

其中，控制時隙中的時幀/時隙的使用方式如1.3節所述，業務時隙的分配使用根據后續組網控制協議和算法分配使用。

控制時隙中，每個節點需要廣播的源控制信息內容包括：源節點的唯一標識ID（長度為logM比特）和鄰居狀態（長度為M比特）。通過此協議，在兩個超幀周期內即可快速完成網絡的自組織收斂。

第一個超幀周期中，在本節點時幀的0時隙發起源控制信息泛洪，初始狀態僅攜帶本節點的ID，其余比特全為0；在X時幀的0時隙接收到泛洪，則置X節點為鄰居，鄰居狀態的相應比特位（X比特位）置為1。

第二個超幀周期中，在本節點時幀的0時隙發起控制信息泛洪。信息包含本節點ID和上一超幀周期內收集的鄰居狀態。通過全網泛洪鄰居狀態，網內所有節點均可以獲取全網拓撲。根據全網拓撲即可完成全網路由計算（推薦路由計算算法采用最短路徑算法[8-9]）；根據全網拓撲和業務時隙實際情況即可完成時隙分配（時隙分配算法可考慮采用著色算法[10]，更優時隙分配算法另文討論），從而完成網絡自組織。

4 結 語

本文設計了一種適用于業務傳輸時延敏感、用戶快速移動、用戶業務量較固定等應用需求的簡單無線自組網協議，采用基于時隙泛洪的方式屏蔽了對自組網路由協議的依賴，大大簡化了網絡協議體系，提升了網絡運行穩定度。此外，針對標準自組織網絡的組網控制信息特點，以此協議為基礎，對協議進行擴展，形成兩個超幀周期即可實現網絡收斂的自組網協議。

[1] Nieminen K.Introduction to Ad Hoc Networking [D].Helsinki:Networking Laboratory Helsinki University of Technology,2003.

[2] Colagrosso M D.Intelligent Broadcasting in Mobile ad Hoc Networks:Three Classes of Adaptive Protocols[J].EURASIP Journal on Wireless Communication and Networking,2007,2007(01):16.

[3] 張遠貴,向新,梅文華等.一種基于時間信息TOD的跳頻同步方法[J].現代電子技術.2009(02):82-84.ZHANG Yuan-gui,XIANG Xin,MEI Wen-hua,et al.Synchronization Scheme for Frequency Hopping Communication System Based on Time of Day[J].Modern Electronic Technology,2009(02):82-84.

[4] 劉雪峰.高速/變速跳頻同步技術[J].計算機與網絡,2009(09):38-40.LIU Xue-feng.Technique of High/Variable Speed Frequency Hopping Synchronization[J].Computer and Networks,2009(09):38-40.

[5] Koubaa A,Alves M,Nefzi B,et al.Improving the IEEE 802.15.4 Slotted CSMA/CA MAC for Time-critical Events in wireless sensor networks[C]//Proceedings of the Workshop of Real-Time Networks，2006：1-6.

[6] 任遠,董淑福,王耀國.數據鏈中隱藏終端問題的幾種解決方法[J].通信技術.2009,42(09):54-56.REN Yuan,DONG Shu-fu,WANG Yao-guo.Some Solutions for Problem of Hidden Terminal in Data Link[J].Communications Technology,2009,42(09):54-56.

[7] 蘭麗,單志龍.Ad Hoc網絡中隱藏終端和暴露終端相關問題研究[J].計算機與數字工程,2010,38(07):36-40.LAN Li,SHAN Zhi-long.Analysis on Relevant Problems of Hidden Terminal and Exposed Terminal in Ad Hoc Networks[J].Computer & Digital Engineering,2010,38(07):36-40.

[8] DEO N,PANG C Y.Shortest Path Algorithms:Taxonomy and Annotation[J].Networks,1984(14):275-323.

[9] CHERKASSKY B V,GOLDERG A V,RA DZIKT.Shortest Paths Algorithms:Theory and Experimental Evaluation[J].Mathematical Programming,1996(73):129-174.

[10] 孫彥贊,姜玉鳳,吳雅婷等.基于改進式隨機不完全著色算法的無線體域網干擾協調[J].電子與信息學報,2015,37(09):2204-2210.SUN Yan-zan,JIANG Yu-feng，WU Ya-ting，et al.Improved Random Incomplete Coloring for Interference Mitigation in Wireless Body Area Networks[J].Journal of Electronics & Information Techno logy,2015,37(09):2204-2210.