定向通信網(wǎng)絡資源分配算法設計及仿真

李瑩 李婥

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

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

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

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

1.1 概述

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

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

1.2 設計目標

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

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

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

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

1.3 控制策略

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

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

二、資源分配算法流程

2.1 觸發(fā)條件

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

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

節(jié)點的始發(fā)業(yè)務需求變化：消息發(fā)送路徑上業(yè)務需求變化，與原占用資源無法匹配；

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

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

2.2 資源分配計算

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

資源分配算法的輸入包含網(wǎng)絡拓撲、業(yè)務需求和節(jié)點位置三個部分。

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

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

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

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

在以TDMA為基礎的定向通信系統(tǒng)中，節(jié)點僅考慮在同一個時隙內(nèi)合理的調(diào)度頻率、空間和節(jié)點的收發(fā)通道，復用的多條鏈路需要避免如下三種沖突：

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

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

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

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

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

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

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

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

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

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

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

確定ts0，tsi：ts0為上一個已分配時隙，tsi為ts0在循環(huán)周期內(nèi)后移delay個時隙；

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

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

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

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

2.3 資源分配確認與占用

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

資源分配節(jié)點將分配結果分發(fā)給鄰居；

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

資源分配節(jié)點收到?jīng)_突資源后，將其刪除，確認最終的資源分配結果。并將該結果分發(fā)給全部鄰居。資源分配節(jié)點完成最終的資源分配結果確認；

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

三、 仿真分析

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

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

為了驗證算法的性能，統(tǒng)計以下仿真指標：

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

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

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

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

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

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

四、結語

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

參 考 文 獻

[1]王錦江，王玉冰，尹忠海.航空作戰(zhàn)平臺定向天線通信網(wǎng)絡構型效能評估[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] 閆魯生，王濤，李威.一種基于 多天線的動態(tài)TDMA協(xié)議仿真研究[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網(wǎng)絡定向接入與空間復用機制設計[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超網(wǎng)結構的時隙分配算法[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] 王文政.戰(zhàn)術數(shù)據(jù)鏈時隙分配協(xié)議及其仿真研究[D]，國防科學技術大學，2010Wang Wen-zheng， Study on Slot Assignment Protocol and Its Simulation for Tactical Data Links[D]， National University of Defense Technology，2010