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

黃佳欣 鄭春勝

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

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

1 經(jīng)典USAP介紹

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

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

圖1 經(jīng)典USAP幀結(jié)構(gòu)

2 改進型USAP

2.1 幀結(jié)構(gòu)設(shè)計

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

改進后的協(xié)議幀結(jié)構(gòu)如圖2所示，其中，前N個時隙為引導(dǎo)時隙，引導(dǎo)子時隙長度為t1，在一個時幀內(nèi)，為每個節(jié)點都分配了一個引導(dǎo)子時隙。后M個時隙為數(shù)據(jù)時隙，時隙長度設(shè)置為t2，一個時幀長度為N*t1+M*t2。

圖2 改進USAP幀結(jié)構(gòu)

2.2 網(wǎng)絡(luò)控制分組中添加的信息

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

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

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

NMOP的長度取決于數(shù)據(jù)時隙的數(shù)量，對于一個最大容納16個節(jié)點的網(wǎng)絡(luò)，存儲單個時隙信息需要9bit，NMOP長度為9*Mbit的時候就能將以上信息全部存入。

2.3 協(xié)議工作流程

網(wǎng)絡(luò)中節(jié)點采用半雙工通信，對于從節(jié)點i到鄰節(jié)點j的單播，時隙分配滿足以下條件，可實現(xiàn)數(shù)據(jù)的無沖突傳輸：

1)在時隙s，節(jié)點i和其鄰節(jié)點j都沒有發(fā)送或接收數(shù)據(jù)；

2)在時隙s，i的所有鄰節(jié)點都沒有接收數(shù)據(jù)；

3)在時隙s，j的所有鄰節(jié)點都沒有發(fā)送數(shù)據(jù)。

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

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

圖3 接收端沖突1

圖4 接收端沖突2

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

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

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

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

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

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

3 仿真驗證

3.1 仿真工具介紹

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

圖6 節(jié)點構(gòu)造模型

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

3.2 仿真場景

圖7 10節(jié)點網(wǎng)絡(luò)拓撲圖

分別設(shè)置10節(jié)點與16節(jié)點網(wǎng)絡(luò)如圖7和8所示，網(wǎng)絡(luò)為分布式拓撲結(jié)構(gòu)，節(jié)點間的連線表示兩節(jié)點在一跳范圍內(nèi)，可實現(xiàn)直接通信，非一跳范圍內(nèi)節(jié)點數(shù)據(jù)的收發(fā)需要其它節(jié)點的轉(zhuǎn)發(fā)。

圖8 16節(jié)點網(wǎng)絡(luò)拓撲圖

3.3 仿真參數(shù)

表1 仿真場景參數(shù)配置

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

3.4 性能指標

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

2)成功收包數(shù)：仿真階段所有目的節(jié)點成功接收數(shù)據(jù)包的個數(shù)；

3)平均端到端時延：指數(shù)據(jù)分組從離開源節(jié)點開始到到達目的節(jié)點為止所經(jīng)過的平均時間；

4)總發(fā)包數(shù)：在仿真時間內(nèi)，所有節(jié)點產(chǎn)生的數(shù)據(jù)包的個數(shù)，用來體現(xiàn)網(wǎng)絡(luò)負載。

4 實驗、結(jié)果與分析

利用圖7所示的10節(jié)點網(wǎng)絡(luò)對改進USAP進行仿真，截取某一時幀數(shù)據(jù)時隙對應(yīng)時間段內(nèi)消息傳輸情況如圖9所示。在該時幀內(nèi)，host[4]和host[5]，host[7]和host[8]，host[6]和host[9]皆在同一數(shù)據(jù)時隙內(nèi)實現(xiàn)了消息的無沖突傳輸。

圖9 消息傳輸情況

圖10 協(xié)議時隙分配耗時統(tǒng)計

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

圖11 時隙占用狀態(tài)統(tǒng)計

圖12 協(xié)議成功收包總數(shù)統(tǒng)計

圖13 協(xié)議平均端到端時延統(tǒng)計

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

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

5 結(jié)論

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