基于OMNeT++仿真平臺的改進型USAP仿真分析

黃佳欣 鄭春勝

北京航天自動控制研究所，北京 100854

飛行器間的協同作戰是未來空戰的重要形式，而協同作戰的前提是組建具有較強通信能力的網絡。不同于有線網絡和無線蜂窩網絡，移動Ad Hoc網絡MANET(Mobile Ad-hoc NETworks)是一類不依賴于基礎設施的由若干移動節點組成的自組織網絡，可以滿足飛行器組網的需求，具有廣泛的應用前景。但其特殊的網絡結構使得傳統的網絡協議不再適用，需要設計出專門的網絡協議。其中，MAC協議(介質訪問控制協議)作為Ad Hoc網絡協議的重要組成部分，對網絡的性能有非常大的影響。由David Young提出的USAP是針對Ad Hoc網絡設計的分布式TDMA時隙分配協議。本文針對經典USAP在節點密度大和拓撲變化迅速的時候無法快速組網的情況，對協議進行了分析和改進，設置仿真場景并利用OMNeT++仿真軟件仿真改進后的協議。結果表明，在多節點網絡中，當節點需要進行頻繁的時隙動態分配時，改進后的協議更符合實際場景的需要。

1 經典USAP介紹

作為一種移動多跳多信道無線網絡的分布式TDMA協議，USAP的核心在于相鄰節點間信息的及時交互，即節點根據接收到的信息更新自身消息表，發送節點根據自身消息表預約時隙池中滿足約束條件的數據時隙進行數據包的發送。與傳統TDMA協議在同一時隙只能有一個節點發送數據相比，USAP可以實現兩跳鄰域內時隙的無沖突分配，理論上一定程度增加了時隙利用率。

對于一個節點數為N，信道個數為F的網絡，USAP的幀結構如圖1所示。圖中一個時幀由M個時隙組成，其中M的數值由設計者根據網絡情況進行設計。每個時幀中的第一個時隙為引導時隙，用于分配給網絡中的某個特定的節點廣播其網絡控制分組NMOP(net manager operation packet)。N個時幀組成一個超幀，以一個超幀為周期，每個節點都能分配到一個引導時隙用于廣播自己的NMOP。

圖1 經典USAP幀結構

2 改進型USAP

2.1 幀結構設計

經典USAP需要經過一個超幀后網絡內的所有節點才能完成一次信息的交互，無法快速適應網絡拓撲結構的變化，并且當網絡中節點數量增多時，會因為信息交互不及時導致時隙分配沖突，浪費大量的數據時隙。為保證控制信息的及時交互，協議增加了每一幀中引導時隙的個數。為簡化協議的設計，本文只討論單信道情況下的時隙分配，以此為基礎不難設計出多信道情況下的協議。

改進后的協議幀結構如圖2所示，其中，前N個時隙為引導時隙，引導子時隙長度為t1，在一個時幀內，為每個節點都分配了一個引導子時隙。后M個時隙為數據時隙，時隙長度設置為t2，一個時幀長度為N*t1+M*t2。

圖2 改進USAP幀結構

2.2 網絡控制分組中添加的信息

STNi(s)：存儲了節點i作為源節點在時隙s的目的節點的編號，未占用時隙對應為0；

SRNi(s)：存儲了節點i作為目的節點在時隙s的源節點的編號，未占用時隙對應為0；

NTi(s)：節點i所有鄰節點的時隙占用情況，在時隙s，若存在鄰節點發送數據，NTi(s)為1，否則為0；

NMOP的長度取決于數據時隙的數量，對于一個最大容納16個節點的網絡，存儲單個時隙信息需要9bit，NMOP長度為9*Mbit的時候就能將以上信息全部存入。

2.3 協議工作流程

網絡中節點采用半雙工通信，對于從節點i到鄰節點j的單播，時隙分配滿足以下條件，可實現數據的無沖突傳輸：

1)在時隙s，節點i和其鄰節點j都沒有發送或接收數據；

2)在時隙s，i的所有鄰節點都沒有接收數據；

3)在時隙s，j的所有鄰節點都沒有發送數據。

問題是數學的“心臟”，數學的發展源自數學問題的衍生，因此數學教學是基于“問題解決”的教學[16]．在此意義下，數學教學的邏輯起點不是概念、原理和法則等知識本身，而是如何創設具有現實性和思考性的“問題”．基于此，首先編制了測試卷，具體包含兩類問題．

上述約束條件成立，則時隙可實現無沖突分配，這一假設是建立在所有節點的時隙分配情況都得到了及時交互的基礎上。但實際上，網絡中節點只能按順序發布自己的NMOP，存在節點間控制信息更新不及時的情況，加上傳輸過程中網絡控制分組的丟失，實際上都會使時隙分配存在沖突，因此，在協議中加入了沖突檢測部分，沖突檢測可分為接收端沖突檢測和發送端沖突檢測2類。

圖3 接收端沖突1

圖4 接收端沖突2

接收端沖突檢測指節點作為接收節點時可以檢測到的沖突，分為以下3種：

1)在時隙s，接收節點收到某一節點的接收請求，但是該接收節點存在另一鄰節點正在發送消息，且目的節點不是該接收節點，如圖3所示；

2)在時隙s，接收節點收到某一節點的接收請求，但該接收節點已被分配接收另一節點發送的消息，如圖4所示；

3)在時隙s，節點計劃向某一鄰節點接收數據，但該接收節點的本地時隙分配表顯示該鄰節點并未發送數據。

發送端沖突檢測指節點作為發送節點可以檢測到的沖突，主要用于判斷接收節點是否對自己的時隙申請進行了確認，沖突描述如下：目的接收節點發送來的NMOP中的SRNi顯示對方在此時沒有接收數據。

規定一個時幀中，每個節點能且只能選擇一個數據子時隙用于發送數據，當目的節點發生改變，則需要根據本地存儲的時隙分配表判斷當前數據子時隙是否繼續可用，若不能，則需放棄當前時隙并重新選擇可用時隙。引導階段協議工作流程如圖5所示，網絡中的節點在分配到的引導子時隙內進行時隙選擇并將結果存入NMOP發送出去，其一跳范圍內的節點在接收到NMOP后進行沖突檢測，若不存在沖突，則更新本地時隙分配表，等待自己的引導子時隙并發送網絡控制分組，完成對申請時隙的確認。如此，通過節點間信息的交互，完成了節點兩跳范圍內時隙的無沖突選擇和確認。每個節點在接收到NMOP后都要進行發送端沖突和接收端沖突3檢測，分別是為了判斷自己的接收請求是否被確認和判斷鄰節點中是否有節點放棄數據子時隙。當節點接收到其它節點的接收請求時，需要進行接收端沖突1、2的判斷。若未檢測到沖突，節點則根據NMOP中的信息對自身的時隙分配表進行更新。

3 仿真驗證

3.1 仿真工具介紹

OMNeT++(Objective Modular Network Testbed in C++)仿真平臺是一款面向對象的、基于組件的、模塊化的開源網絡仿真器，具有較好的組織性和靈活性。一個完整的OMNeT++仿真中一般包含拓撲描述語言NED文件、消息定義文件、簡單模塊源文件和OMNeT++配置文件4個部分，其中簡單模塊源文件用于為簡單模塊編寫仿真內核、實現模塊功能，是仿真中的核心部分。

圖6 節點構造模型

本文采用了支持在OMNeT++中進行移動無線網絡仿真的INET框架，INET協議棧的開發設計采用的是分層結構，只要定義好協議棧間接口不改變，就能獨立對各層協議棧進行研究。本次仿真中，節點構造模型如圖6所示，其中應用層模塊(Application)、網絡層模塊(Network)和網絡接口模塊(NIC)起到了數據傳輸的作用，Mobility模塊用于定義網絡中節點的移動，Routing Table和Interface Table模塊分別為路由表和網絡接口列表。

3.2 仿真場景

圖7 10節點網絡拓撲圖

分別設置10節點與16節點網絡如圖7和8所示，網絡為分布式拓撲結構，節點間的連線表示兩節點在一跳范圍內，可實現直接通信，非一跳范圍內節點數據的收發需要其它節點的轉發。

圖8 16節點網絡拓撲圖

3.3 仿真參數

表1 仿真場景參數配置

為存入2.2中描述的所有交互信息，10節點網絡的NMOP長度需大于78bit，16節點網絡的NMOP長度需大于128bit，NMOP長度受網絡節點個數影響較大，文中將NMOP長度設置為416bit以滿足更大規模網絡設計的需要。對應1Mbps的數據率，將引導子時隙t1長度設置為0.5ms，數據子時隙t2長度設置為6ms。10節點網絡對應時幀長度為47ms，引導時隙部分為5ms，16節點網絡對應時幀長度為56ms，引導時隙部分為8ms。

3.4 性能指標

1)時隙分配耗時：指開始時隙分配到每個有傳輸需求的節點都能在一個時幀內實現無沖突傳輸所用時間；

2)成功收包數：仿真階段所有目的節點成功接收數據包的個數；

3)平均端到端時延：指數據分組從離開源節點開始到到達目的節點為止所經過的平均時間；

4)總發包數：在仿真時間內，所有節點產生的數據包的個數，用來體現網絡負載。

4 實驗、結果與分析

利用圖7所示的10節點網絡對改進USAP進行仿真，截取某一時幀數據時隙對應時間段內消息傳輸情況如圖9所示。在該時幀內，host[4]和host[5]，host[7]和host[8]，host[6]和host[9]皆在同一數據時隙內實現了消息的無沖突傳輸。

圖9 消息傳輸情況

圖10 協議時隙分配耗時統計

分別在10節點和16節點的網絡中對經典USAP和改進USAP進行仿真，仿真參數見表1，記錄時隙分配耗時如圖10。由圖可知，改進USAP時隙分配耗時遠低于經典USAP，10節點網絡中耗時縮短了90.52%，16節點網絡中耗時縮短了93.59%。并且，在10節點網絡中，改進USAP耗時0.141ms，為3個時幀長度，經典USAP耗時1.4875ms，為35個時幀，而在16節點網絡中，改進USAP耗時仍為3個時幀，經典USAP耗時增加為54個時幀。由此可知，在10節點和16節點的網絡中，改進USAP都只經過了3個時幀便完成了時隙的無沖突分配，在網絡規模變化不大的情況下，耗時受節點個數變化影響不大，都可以快速地完成時隙的無沖突分配。然而，經典USAP在10節點網絡中經過35個時幀完成時隙分配，在16節點網絡中經過54個時幀完成時隙分配，受網絡規模影響大。

圖11 時隙占用狀態統計

圖12 協議成功收包總數統計

圖13 協議平均端到端時延統計

經典USAP無法適應拓撲結構快速變化網絡的直接原因是時隙動態分配時間長。USAP對時隙的分配與網絡拓撲結構有關，當網絡拓撲結構發生變化，節點需要重新選擇可用時隙，在這種情況下，節點間信息交互不及時會使得時隙分配耗時過長導致算法難以達到收斂。仿真中，為避免路由請求報文對實驗產生干擾，令網絡中節點靜止，使用靜態路由協議，設置每個節點交替地向不同目的節點發送數據包。由于本文規定在一個時幀中，網絡中每個節點能且僅能分配到一個數據子時隙，因此，當目的節點發生變化時，節點需要重新選擇可用時隙，如此，時隙隨著目的節點的變化動態分配，以達到考察不同協議時隙分配效率的目的。當改進后的協議能快速地完成時隙的動態分配這一假設得到驗證，則不難知道該協議可以適應動態變化的網絡。

利用圖7所示的10節點網絡分別對TDMA、經典USAP和改進USAP進行仿真，host[0]與host[2]為目的節點，其它節點產生向這兩節點傳輸的數據包。截取0～2s內host[3]對時隙的占用狀態如圖11所示，狀態量為1表示當前有可用時隙，狀態量為0表示節點放棄了當前時隙且需要重新選擇可用時隙。由圖可知，目的節點發生變化，網絡內節點不斷地對時隙進行動態選擇，且很快就能選擇到可用時隙。改變發包速度，得到各協議在不同負載下成功的收包數和平均端到端時延，分別如圖12和13。由圖12可知，改進USAP成功接收數據包的個數隨著負載量的增加而增加，直至達到穩定，且整體高于其它兩組，經典USAP成功接收數據包數量最低。由圖13可知，三者的平均端到端延時都隨著網絡負載量的增加而增加直至達到穩定。整體上，改進USAP時延最低，經典USAP時延隨負載量提高增加明顯，且為三者最高。若只從平均端到端時延和成功收包數這兩方面來對協議性能進行評估，性能由高到低分別為改進USAP、TDMA和經典USAP。在需要動態分配數據時隙的網絡中，經典USAP的性能要低于傳統TDMA，并沒有起到改善網絡性能的作用，這是因為實現時隙無沖突分配的前提是控制幀的及時交互使得每個節點都能及時獲取兩跳范圍內時隙分配情況，但經典USAP信息交互效率低，導致時隙分配算法難以達到收斂，網絡內節點無法及時得到可用的數據子時隙而造成了大量時隙浪費，使網絡性能降低。改進USAP通過增加一個時幀中引導時隙的個數，提升了節點間信息交互的效率，因此，協議性能得到改善。

5 結論

針對經典USAP在多節點網絡中因為時隙分配效率低造成大量時隙浪費，導致網絡性能較差的情況，設計了一種基于經典USAP的鏈路層協議。使用OMNeT++軟件進行仿真，分析比較不同協議在同一仿真場景下的性能。結果表明，改進后的USAP在時隙分配效率、時延和收包數3方面的性能較經典USAP有了較大的提升，更適用于多節點Ad Hoc網絡。但本文沒有在動態網絡下對改進USAP的性能進行考察，后續的研究中可結合網絡層動態路由對移動網絡進行仿真。并且，本實驗中使用固定分配的方式為網絡內節點分配引導時隙，未考慮節點動態入網的情況，這也將是后續研究的重點。