李瑩 李婥

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

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

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

一、資源分配算法設(shè)計(jì)原則

1.1 概述

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

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

1.2 設(shè)計(jì)目標(biāo)

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

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

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

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

1.3 控制策略

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

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

二、資源分配算法流程

2.1 觸發(fā)條件

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

網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)變化：部分消息的發(fā)送路徑發(fā)生改變，使得某條鏈路上的業(yè)務(wù)需求變化，與原占用資源無(wú)法匹配；

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

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

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

2.2 資源分配計(jì)算

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

資源分配算法的輸入包含網(wǎng)絡(luò)拓?fù)洹I(yè)務(wù)需求和節(jié)點(diǎn)位置三個(gè)部分。

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

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

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

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

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

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

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

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

按照實(shí)現(xiàn)目標(biāo)，資源分配計(jì)算方法描述如下。

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

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

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

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

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

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

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

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

查找第一個(gè)空時(shí)隙tsj：選擇的優(yōu)先順序?yàn)椋合葟膖si向前選擇，再?gòu)膖si向后選擇；

查找第一個(gè)復(fù)用時(shí)隙tsk：選擇的優(yōu)先順序?yàn)椋合葟膖si向前選擇，再?gòu)膖si向后選擇；

分配時(shí)隙：從tsj和tsk中選擇一個(gè)時(shí)隙分配給鏈路（a，b），首選滿足時(shí)延需求的，若沒(méi)有則選擇沒(méi)有滿足時(shí)延需求的；同樣條件下，首選空時(shí)隙，若沒(méi)有則選擇復(fù)用時(shí)隙。

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

2.3 資源分配確認(rèn)與占用

在資源分配節(jié)點(diǎn)完成資源分配計(jì)算后，進(jìn)入資源分配確認(rèn)及占用階段。

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

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

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

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

三、 仿真分析

為了驗(yàn)證資源分配算法的合理性及算法性能，采用Matlab仿真軟件進(jìn)行建模仿真。仿真采用固定拓?fù)浣Y(jié)構(gòu)，傳輸速率需求固定，如表1所示。拓?fù)浣Y(jié)構(gòu)如圖4所示。

在上述拓?fù)浣Y(jié)構(gòu)和傳輸速率需求的基礎(chǔ)上，本文仿真了10個(gè)場(chǎng)景，每個(gè)場(chǎng)景中時(shí)隙分配周期不同，以及時(shí)延需求不同，如表2所示。

為了驗(yàn)證算法的性能，統(tǒng)計(jì)以下仿真指標(biāo)：

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

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

資源分配結(jié)果誤差：為每條鏈路的傳輸速率分配結(jié)果誤差和時(shí)延分配結(jié)果誤差之和的平均值。其中，傳輸速率分配結(jié)果誤差為需求速率與實(shí)際速率之差的絕對(duì)值；時(shí)延分配結(jié)果誤差為每?jī)蓚€(gè)分配時(shí)隙之間的時(shí)隙間隔與時(shí)延需求之差再求和的平均值。

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

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

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

四、結(jié)語(yǔ)

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

參 考 文 獻(xiàn)

[1]王錦江，王玉冰，尹忠海.航空作戰(zhàn)平臺(tái)定向天線通信網(wǎng)絡(luò)構(gòu)型效能評(píng)估[J].空軍工程大學(xué)學(xué)報(bào)（自然科學(xué)版），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] 閆魯生，王濤，李威.一種基于 多天線的動(dòng)態(tài)TDMA協(xié)議仿真研究[J].通信技術(shù)，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] 郝東.無(wú)線AdHoc網(wǎng)絡(luò)定向接入與空間復(fù)用機(jī)制設(shè)計(jì)[D].北京郵電大學(xué)， 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)結(jié)構(gòu)的時(shí)隙分配算法[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ù)數(shù)據(jù)鏈時(shí)隙分配協(xié)議及其仿真研究[D]，國(guó)防科學(xué)技術(shù)大學(xué)，2010Wang Wen-zheng， Study on Slot Assignment Protocol and Its Simulation for Tactical Data Links[D]， National University of Defense Technology，2010