定向通信網絡資源分配算法設計及仿真

李瑩 李婥

【摘要】 為了提高定向網絡中的資源利用率，以及增強資源隨著業務需求及網絡狀態變化的快速調整能力，研究了定向通信網絡特點以及資源分配算法的基本思想及關鍵設計要點，設計了一種分布式資源分配算法。該算法合理調度時間、頻率、空間和硬件通道等資源，使得分配結果能夠實時的滿足不同鏈路的傳輸速率需求以及時延需求。最后，通過仿真測試的方法驗證了算法可以實現在多變網絡狀態下的資源動態調整，滿足定向網絡中多種業務的傳輸需求，適合應用在需求多變的定向網絡中。關鍵詞：定向網絡；資源分配；分布式；多業務需求

RESOURCE ASSIGN ALGORITHM DESIGN AND SIMULATION FOR DIRECTIONAL COMMUNICATION NETWORKS Li Ying①， Li Chuo②（①Southwest China Institute of Electronic Technology， Chengdu Sichuan 610036； ②China Academy of Electronics and Information Technology， Beijing 100041）

Abstract：In order to improve the resource utilization rate of the directional network， and enhance the ability to adjust the resources along with the service requirement and network state change， the characteristic of directional communication networks and the main principle of resource assign algorithm are studied. A distributed resource assign algorithm is designed. The algorithm can reasonably schedule the time， frequency， space and hardware resources， so that the assign results can meet the requirements of different link on transmission rate and time delay. Finally，the algorithm can realize the dynamic adjustment of resources in the changing network state by the method of simulation， which can meet the needs of multi service transmission in the network.

Key words：Directional networks； Resource assign； Distributed； Multi service requirement

由于定向天線具有波束窄、增益高、傳輸距離遠、隱蔽通信等諸多優點[1]，在無線通信網絡上的應用越來越廣泛，采用定向天線通信的網絡被稱為定向通信網絡。對于實時性要求比較高的通信網絡，一般優先考慮TDMA接入方式[2]。其中，動態時隙分配TDMA具有更好的信道利用率及不同業務類型的能力并支持QoS[3]。在選擇TDMA接入方式的定向通信網絡中，可以利用定向天線窄波束的輻射特性，多對節點之間在同一個時隙內同時進行數據收發，實現時隙資源在空間維度的復用，即空分復用，提高網絡的吞吐量和時隙的利用率。由于網絡中的拓撲以及業務的QoS需求在不斷變化，因此，如何動態的高效分配網絡資源是定向通信網絡亟需解決的關鍵問題。本文主要針對TDMA定向通信網絡的動態資源分配算法展開研究。

一、資源分配算法設計原則

1.1 概述

TDMA網絡中，動態資源分配算法的基本思想是：各成員入網后，當業務量調整時能自動調整各資源占有狀態，從而提高了整個網絡的資源利用率[4]。本文描述的定向通信網絡中，可以進行動態分配的資源包括四類，分別是時隙資源、頻率資源、空間資源以及成員的硬件通道資源，同一時隙內多個成員之間的空分復用如圖1所示。

基于TDMA的定向通信網絡的動態資源分配算法中，網絡成員需要根據當前業務對傳輸速率以及通信時延的需求，在時隙資源的基礎上合理調度其他資源，獲得時隙頻率分配表，使得該分配表在滿足業務需求的前提下，最小化全網的資源消耗。資源分配算法原理圖如圖2所示。

1.2 設計目標

由于系統中存在四類可分配資源，每類資源的可用集合大小不同，因此每占用一個資源的消耗系數也不同。資源分配算法的求解目標總結為如下兩點：

分配結果誤差：定義分配結果誤差來表示分配結果與需求之間的差距。顯而易見，分配結果誤差越小越好，為0則為最優。分配結果誤差包含傳輸速率分配結果誤差和時延分配結果誤差兩部分。

全網資源消耗：為每類資源配置不同的資源消耗系數，該系數根據資源的緊缺程度來確定，緊缺資源的消耗系數高。顯然全網資源消耗越低越好。

綜上，資源分配算法的設計目標為在確保資源分配誤差最低的情況下，最小化全網資源消耗。算法計算流程以該目標為依據，進行資源分配計算。

1.3 控制策略

根據網絡中擔任資源分配計算職責的成員的不同，可以分為集中式動態資源分配算法和分布式動態資源分配算法。集中式算法通過中心控制節點收集全部成員的需求信息，再根據需求計算資源分配，最后將分配結果分發給每個成員。分布式算法中每個節點僅需評估本節點的需求信息，再根據局部的資源占用情況計算新的資源分配，新的資源分配結果與一跳鄰居進行局部干擾排除，最后完成資源占用確認[5]。由于僅需要在局部鄰居之間保持資源的互斥性，與全局的其他成員無關，而且分布式算法的抗毀性好，因此本文的算法選擇分布式的控制策略。

分布式的控制策略中，每個成員為自己的需求負責，進行資源分配計算，與局部鄰居協商完成資源分配確認，最后實現資源占用，流程如圖3所示。

二、資源分配算法流程

2.1 觸發條件

由資源分配算法原理圖可以看出，當網絡中的可用資源不變時，業務需求的變化將導致現有資源占用與新的業務需求無法匹配，即觸發進行新一輪的資源分配。資源分配的觸發條件如下：

網絡的拓撲結構變化：部分消息的發送路徑發生改變，使得某條鏈路上的業務需求變化，與原占用資源無法匹配；

節點的始發業務需求變化：消息發送路徑上業務需求變化，與原占用資源無法匹配；

節點間相對位置關系變化：空間復用條件發生變化，使得某條鏈路必須放棄部分資源占用，其可用資源減少，與原業務需求無法匹配；

因此，節點在網絡運行中僅需周期的評估需求與可用資源是否匹配，若不匹配，則啟動資源分配算法計算。

2.2 資源分配計算

當滿足資源分配的觸發條件時，成員將在本地啟動資源分配計算。

資源分配算法的輸入包含網絡拓撲、業務需求和節點位置三個部分。

網絡拓撲：網絡拓撲為節點兩跳范圍內的拓撲。假定網絡中的最大成員數為N，則網絡拓撲用3個維的矩陣topo表示。每個維的矩陣中，行號表示發送節點序號，列號表示接收節點序號，由于采用定向天線通信，每個節點配置多副定向天線。每個矩陣中的元素的含義如下：若矩陣中的元素為0，則表示發送節點與接收節點之間不存在鏈路，否則，第1個矩陣的元素表示發送節點使用的天線序號，第2個矩陣的元素表示接收節點使用的天線序號，第3個矩陣的元素表示發送節點與接收節點之間的通信速率。

業務需求：由于網絡中采用定向鏈路，因此需求為每條鏈路的業務需求。分為兩類，一類是業務傳輸速率需求，一類是業務傳輸時延需求。分別采用維矩陣和表示。行號表示發送節點序號，列號表示接收節點序號，矩陣中的元素表示發送節點到接收節點的鏈路上的速率需求和時延需求，單位均為時隙數。

節點位置：節點位置為兩跳范圍內節點的位置信息，用一個維的矩陣pos表示，行號表示節點序號，列號表示位置信息序號，其中第1列表示該節點的經度，第2列表示該節點的緯度，第3列表示該節點的高度。

資源分配算法的輸出為時隙頻率分配表，假定網絡的循環周期為M個時隙，則采用維的矩陣ts來表示，即M個維矩陣。第t個維矩陣表示時隙t內的頻率分配。行號表示發送節點序號，列號表示接收節點序號，矩陣中的元素表示發送節點到接收節點的鏈路上分配的頻率序號。

在以TDMA為基礎的定向通信系統中，節點僅考慮在同一個時隙內合理的調度頻率、空間和節點的收發通道，復用的多條鏈路需要避免如下三種沖突：

節點收發通道沖突：如果兩條鏈路之間存在一個共用的節點，且共用節點在兩條鏈路上使用相同的收發信道，則存在沖突；

頻率沖突：如果兩條鏈路之間存在一個共用的節點，且共用節點在兩條鏈路上使用不同的收發信道，但已無空閑頻率分配給新增鏈路，則存在沖突；

空間沖突（干擾沖突）：兩條鏈路之間不存在共用節點，根據節點位置，收發天線之間的角度以及定向天線增益等計算一條鏈路的發送信號對另外一條鏈路的接收節點的干擾，若干擾導致信噪比低于解調門限，則存在沖突。

按照實現目標，資源分配計算方法描述如下。

取出本節點的全部待分配資源的鏈路，根據每條鏈路的傳輸速率分配需求slot_cnt_require，把每個鏈路的分配機會按照需求均勻穿插排列，形成一個分配鏈路集合A。

確定鏈路（a，b）在時隙s內的可用頻率集合的方法：全部可用頻率集合，除掉時隙s內全部已分配鏈路占用的頻率后，剩余的全部頻率集合。

確定鏈路（a，b）在時隙s內是否可空分復用的計算方法：鏈路（a，b）選擇臨時頻率后，計算其與時隙s內全部已有鏈路（c，d）之間的相互接收信號干擾，接收信號電平均在解調門限之上，則認為（a，b）可以在時隙s內復用。

對于集合A中的某一條鏈路（a，b），資源分配流程如下：

確定鏈路（a，b）的分配時延delay：取slot_cnt/ slot_cnt_require和delay_require的最小值。其中slot_cnt為資源分配循環周期內時隙個數，delay_require為該鏈路的時延需求。

確定鏈路（a，b）的第一個分配時隙：選擇的優先順序為[1，delay]內的第一個空時隙，[1，delay]內第一個空分復用時隙，[delay+1，slot_cnt]內第一個空時隙，[delay+1，slot_ cnt]內第一個空分復用時隙。若分配失敗，則刪除集合A中全部鏈路（a，b），鏈路（a，b）本次資源分配結束。

確定鏈路（a，b）的后續分配時隙：

確定ts0，tsi：ts0為上一個已分配時隙，tsi為ts0在循環周期內后移delay個時隙；

查找第一個空時隙tsj：選擇的優先順序為：先從tsi向前選擇，再從tsi向后選擇；

查找第一個復用時隙tsk：選擇的優先順序為：先從tsi向前選擇，再從tsi向后選擇；

分配時隙：從tsj和tsk中選擇一個時隙分配給鏈路（a，b），首選滿足時延需求的，若沒有則選擇沒有滿足時延需求的；同樣條件下，首選空時隙，若沒有則選擇復用時隙。

集合A全部鏈路分配結束后，檢查每個鏈路的分配結果，若最后一個分配時隙和第一個分配時隙之間的時隙間隔大于時延需求，則繼續按照步驟（4）的c）的方法，繼續完成時隙分配，直至最后一個時隙與第一個時隙的時隙間隔滿足鏈路的時延需求或者無資源可分為止。

2.3 資源分配確認與占用

在資源分配節點完成資源分配計算后，進入資源分配確認及占用階段。

資源分配節點將分配結果分發給鄰居；

鄰居收到新的資源分配結果后，將其與本地的資源分配結果比較，并將發生沖突的資源回復給資源分配節點；

資源分配節點收到沖突資源后，將其刪除，確認最終的資源分配結果。并將該結果分發給全部鄰居。資源分配節點完成最終的資源分配結果確認；

資源分配節點與其鄰居同時完成對本次資源分配結果中資源的占用。

三、 仿真分析

為了驗證資源分配算法的合理性及算法性能，采用Matlab仿真軟件進行建模仿真。仿真采用固定拓撲結構，傳輸速率需求固定，如表1所示。拓撲結構如圖4所示。

在上述拓撲結構和傳輸速率需求的基礎上，本文仿真了10個場景，每個場景中時隙分配周期不同，以及時延需求不同，如表2所示。

為了驗證算法的性能，統計以下仿真指標：

時延需求滿足百分比：鏈路的滿足時延需求的時隙數除以該鏈路總分配時隙數

傳輸速率需求滿足百分比：鏈路已分配時隙個數除以總需求時隙數。

資源分配結果誤差：為每條鏈路的傳輸速率分配結果誤差和時延分配結果誤差之和的平均值。其中，傳輸速率分配結果誤差為需求速率與實際速率之差的絕對值；時延分配結果誤差為每兩個分配時隙之間的時隙間隔與時延需求之差再求和的平均值。

全網資源消耗：全網已分配資源的消耗系數之和。網絡中四個資源搭配的資源消耗系數如下：Cost_time =0.2；Cost_freq=0.4；Cost_space = 0.05；Cost_txrx=0.05。

10個仿真場景的統計結果如下所示。圖5和圖6給出了四個場景的傳輸速率需求滿足百分比和時延需求滿足于百分比。10個場景仿真結果中，除循環周期為50個時隙的場景之外，需求滿足百分比均在100%以上。若定義時隙需求數與循環周期內時隙數的倍數為時隙復用率需求，則循環周期為50個時隙的場景下，僅考慮傳輸速率需求，時隙復用率需求即達到6.86，再結合時延需求，時隙復用率需求更高。本文算法在考慮時延和復用條件等約束條件下，實際時隙復用率達到4.76，鏈路BF的資源分配結果未能完全滿足需求。

圖7和圖8分別給出了10個場景的資源分配結果誤差和全網資源消耗。本文算法設計中將資源分配結果誤差最小，全網資源消耗最小作為設計原則，通過仿真統計可以看出，算法在資源分配結果誤差和全網資源消耗方面的性能。

四、結語

本文設計的定向網絡資源分配算法為分布式算法，通過仿真結果可以看出，各成員僅需根據其本地及鄰居的資源分配狀態以及本地的業務需求作為輸入，進行資源分配計算，再與鄰居完成資源分配確認，最終實現資源占用， 全部采用局部信息交互，無需全網廣播，因此更適合于大型網絡中應用，可擴展性強，且開銷較低。此外，該算法的目標為確保資源分配誤差最低的情況下，最小化全網資源消耗，通過仿真表明，算法可以實現在多變網絡狀態下的資源動態調整，滿足定向網絡中多種業務的傳輸需求。

參 考 文 獻

[1]王錦江，王玉冰，尹忠海.航空作戰平臺定向天線通信網絡構型效能評估[J].空軍工程大學學報（自然科學版），2013， 14（2）：61-65

Wang Jin-jiang， Wang Yu-bing， Yin Zhong-hai， Combat Aircraft Directional Antenna Communication Network Formation Efficiency Evaluation[J].JOURNAL OF AIR FORCE ENGINEERING UNIVERSITY（NATURAL SCIENCE EDITION），Apr.2013，Vol.14 No.2：61-65.

[2] 閆魯生，王濤，李威.一種基于 多天線的動態TDMA協議仿真研究[J].通信技術，2011，44（12）：107-110YAN Lu-sheng， WANG Tao， LI Wei， Simulation Study of Multi-Channel Dynamic TDMA Protocol[J]， Communications Technology， 2011， Vol.44， No.12： 107-110.

[3] 郝東.無線AdHoc網絡定向接入與空間復用機制設計[D].北京郵電大學， 2012Hao Dong， Directional Access and Spatial Multiplexing Mechanism Design for Wireless Ad Hoc Networks[D]， Bejing University of Posts and Communications， 2012

[4] 任浩，毛玉泉，李波.適用于link22超網結構的時隙分配算法[J].火力與指揮控制，2011，36（12）：160-163REN Hao， MAO Yu-quan， LI B，A Time-Slot Assignment Scheme Suitable for Link22 Super Network[J]， Fire Control &Command; control，De c，2011，Vol.36，No.12：160-163

[5] 王文政.戰術數據鏈時隙分配協議及其仿真研究[D]，國防科學技術大學，2010Wang Wen-zheng， Study on Slot Assignment Protocol and Its Simulation for Tactical Data Links[D]， National University of Defense Technology，2010