數據鏈時隙分配算法設計與仿真

楊 恩， 張有光， 唐積強

（北京航空航天大學 電子信息工程學院，北京 100191）

0 引言

數據鏈是采用網絡通信技術和應用協議,實現機載、陸地和艦船系統之間的高效的數據信息交換的通信系統[1]?，F代空空通信環境下，節點之間的信息交互較多，網絡通信業務需求較大，實時性要求強?；谧越M織時分多址技術（STDMA）的數據鏈系統[2]是以時隙為基本單位，將時間軸劃分為若干個時隙，由多個時隙組成時幀，網絡中的每個作戰單元在每個時幀中都占有時隙，為信息交互提供了實時性保證。

現通過使用OPNET軟件對自組織預約STDMA算法[3]進行仿真，對仿真結果進行分析，提出了改進的動態自組織時隙分配算法（DSTDMA），該算法可以有效的保證網絡的實時性要求，能夠更好的適應網絡規模的變化。

1 預約STDMA算法簡介

預約 STDMA算法由固定分配和預約分配兩種方式組成，其幀結構組成如圖1所示，每個超幀有n個時幀組成，每個時幀由m個時隙組成[4]。在該算法中，每個時幀由固定時隙和可預約時隙組成。固定時隙固定分配給網絡內的節點，其余節點不能使用；預約時隙可以由網絡內的時隙共同競爭使用。

圖1 時幀結構

該算法提出了動態的時隙預約思想，為網絡內的數據包通信提供了QoS保證機制，并且提供了完成的網絡調整的機制，整個算法具有較高的穩定性。

在網絡規模穩定的情況下，該算法能夠獲得更好的穩定執行效果，但是當節點較少時，由于整個時幀長度已經固定為m，將會導致部分時隙的浪費，并且當網絡規模不斷增加之后，由于網絡的時隙數有限，將導致網絡所有空閑時隙都被分配出去，無法為新節點分配時隙，節點不能加入網絡。

在針對STDMA算法的在以上環境下的不適應性，所以提出一種可以動態調整時幀長度的時隙分配算法（DSTDMA），在網絡規模變化較快環境下，算法能夠更好的利用時隙，減小數據包時延，并且具有良好的可擴展性。

2 DSTDMA算法簡介

2.1 時幀結構

DSTDMA算法的幀長度為2的冪次方，在網絡運行的整個期間，時幀的長度可變，其幀結構如圖2所示。當網絡內節點較少時，網絡內的幀長度較小，每個節點占用一個時隙，當節點數增加之后，由于原來的時隙數無法滿足當前的節點數，則幀長度進行加倍，為新入網節點分配時隙。下面將具體的介紹整個算法的流程。

圖2 時隙分配算法的時幀結構

2.2 時隙分配

新的節點在加入網絡時，需要獲取網絡中的可用時隙，來進行數據包的發送，其主要過程為如下幾個步驟：

（1）發送入網申請

當一個新的節點加入網絡之前，節點不知道網絡內的任何時隙分配信息，首先需要偵聽網絡的幀長度，確定0號時隙的位置，發送入網申請信息。

（2）獲取時隙分配信息

當網絡內的節點接收到新節點的入網申請之后，各個節點在自己占有的時隙發送其時隙占用情況以及其鄰居節點的時隙占用情況。新節點記錄下其所有鄰居節點發送來的時隙分配信息，首先將自己的時幀長度設置成與獲取到的最大時幀長度相等。

（3）選擇時隙

節點根據上一個階段所記錄的時隙信息，按照下面三個步驟進行時隙的選擇。

①選擇空閑時隙。節點根據在上一階段獲取的各個鄰居的時隙信息情況，選擇沒有被任何節點占用的時隙；

社會發展至今，包容度越來越高?！半p十一”呼嘯而至，碼商百舸爭流，無論是否買家，都應該放下一切與這個時代不再契合的觀念，用自身的體驗來打量“雙十一”，尋找它的意義。

②釋放節點多占的時隙。當新節點在查找獲得的時隙信息之后，發現沒有空余時隙，那么新節點將查找所獲得的時隙信息中，是否存在一個節點占有多個時隙的情況，如果存在一個節點占有了多個時隙，那么將從占有時隙做多的節點所占有的時隙中，選擇一個時隙，作為新節點的時隙；

③調整幀長。當新節點查找時隙信息時，如果沒有能夠滿足上面兩個情況，新節點將主動將時幀長度加倍，由于每個幀中的第一個時隙是預留時隙，所以，幀長加倍之后，新節點可以占用后面半個幀中的第一個時隙。時幀長度加倍之后，后半幀的時隙占用除了后半幀中第一幀外，其余各個時隙均與前半幀相同。

（4）更新時隙信息

完成了上面三個階段之后，一個新節點就加入到了網路之中。新節點將其選擇的時隙信息在一下個0號時隙進行播報，網絡內節點接收到新的時隙分配信息之后，將自己所記錄的時隙表進行更新；并且將更新后的時隙信息再次進行播報，使得其鄰居節點也更新時隙表信息，保證新入網節點兩跳范圍內實現無沖突的時隙分配。

3 OPNET仿真建模

OPNET軟件作為一種主流網絡仿真軟件，為通信網絡和分布式系統的建模提供了全面的模擬仿真開發環境。OPNET采用三層建模機制：進程模型、節點模型、網絡模型。三層模型與實際的協議、設備、網絡完全對應，能夠全面的反映出網絡的相關特性[5]。

3.1 進程模型

進程模型使用有限狀態機來描述進程的邏輯行為，它位于OPNET三層模型中的最底層。DSTDMA狀態機設計共由8個狀態構成。

①init狀態機完成算法的初始化過程，設置節點的時隙長度，業務信息，節點類型等；

②listen、backoff、wait狀態機完成發送入網申請，以及根據獲得的時隙信息，進行時隙的選擇；

③control狀態完成網絡內節點的時隙信息發送和時隙分配調整過程。

3.2 節點模型

OPNET中節點模型定義了每一個節點的行為，一個節點通常由多個模塊組成，節點的行為有組成它的模塊所決定，每個模塊完成節點的一部分行為。DSTDMA的節點模型包含三層，最上層為sink模塊和src模塊，用來產生數據包和處理、銷毀本節點接收的數據包；中間是mac模塊，算法的核心模塊，完成整個時隙分配算法；最下層是OPNET軟件提供的無線收發機模塊，用來完成數據的收發。

4 仿真結果分析

4.1 仿真場景

對預約STDMA算法和DSTDMA算法分別進行了建模分析，下面給出仿真分析的網絡場景模型。在高動態空空數據鏈網絡中，節點具有通信距離遠，運行時間較長等，網絡內節點數目有限等特點。整個場景的由 16個節點組成，網絡中時隙長度為50 ms，仿真時間為1 h。

4.2 結果分析

仿真過程中，網絡內各個節點發送的數據包大小為200 bit，下面三幅圖（圖3、圖4和圖5）給出了在不同業務量下，兩種算法的時延性能曲線。

由這三組結果可以得出以下結論：

①算法有效性：通過仿真，驗證了DSTDMA算法的有效性，網絡中各個節點能夠按照算法組成網絡，并完成時隙分配過程，實現無沖突的數據包發送，顯示出了算法的可實現性；

②實時性：由三組仿真結果可以看出，DSTDMA算法有效的減小數據鏈的數據包端到端傳輸時延。從上面三幅曲線中,可以看出,在網絡形成初期,由于節點數量較少,數據傳播時延較小,隨著節點不斷加入網絡之后,數據時延開始增加，最終全網的時延保持穩定。當業務量升至每秒1個數據包的情況下,DSTDMA算法的時延性能明顯優于STDMA算法，平均數據時延穩定在1 s，這主要是由于DSTDMA算法采用了監聽的方式完成整個時隙分配的過程，減少了網絡為節點入網過程所預留的控制數據交互的時隙，有效提高了時隙的利用率，降低了數據包時延；

圖3 1 packets/s

圖4 0.5 packets/s

圖5 0.2 packets/s

③可擴展性：DSTDMA算法的幀長度可以動態變化，隨著網絡規模的不斷變化，幀長度進行自適應調整，以容納下新加入的節點，與 STDMA算法相比，提高了網絡的可擴展性。

5 結語

通過對STDMA算法的分析，提出了一種可變幀長的動態自組織時隙分配算法，在網絡環境變化較快的情況下，能夠容納更多節點，網絡規模具有更好的可擴展性；同時，算法提高了網絡數據包的端到端時延，有效提高了高動態環境下的信息通信。最后，通過OPNET軟件對其進行建模分析，對算法的實時性和可擴展性進行了仿真論證。

[1] 孫義明，楊麗萍.信息化戰爭中的戰術數據鏈[M].北京：北京郵電大學出版社，2005：5-17.

[2] 張軍,張其善,鄧秋林.S-TDMA 數據鏈系統時隙預約選擇算法分析[J].北京航空航天大學學報,2001(05)：514-517.

[3] 張昱暉,張有光,唐積強.一種新型 STDMA 數據鏈系統時隙分配模型[J].通信技術,2009,42(06)：59-61.

[4] 李楠,陳穎,夏毅強.VDL4：一種新型航空VHF 數據鏈[J].電訊技術,2003(06)：90-94.

[5] 陳敏.1OPNET網絡仿真[M].北京：清華大學出版社,2004.