張 鑫，張 旭，張入文，于琪琦，王玉霞，韋迎新，黃寶貴

(曲阜師范大學(xué)信息科學(xué)與工程學(xué)院，山東 日照 276800)

0 引 言

無線網(wǎng)絡(luò)通信技術(shù)中一些應(yīng)用領(lǐng)域?qū)νㄐ诺目煽啃砸蠛芨撸鐭o線網(wǎng)絡(luò)工業(yè)通信[1-2]、軍事通信等。但是信號傳輸衰落及信號之間的干擾通常會降低網(wǎng)絡(luò)容量，導(dǎo)致無線通信失敗。基于SINR(Signal to Interference plus Noise Ratio)的無線通信鏈路調(diào)度是目前無線網(wǎng)絡(luò)通信技術(shù)中最常用的一種空間復(fù)用技術(shù)[3-6]，可以解決網(wǎng)絡(luò)容量和延遲的問題[7-11]，提高空間利用率和通信可靠性。目前鏈路調(diào)度主要分為2大類：1)最大鏈路調(diào)度[12-13]，即最大化單時隙內(nèi)可以并發(fā)調(diào)度的鏈路數(shù)目；2)最短鏈路調(diào)度[14-18]，即用最少的時隙調(diào)度所有鏈路。

設(shè)計具有SINR約束的鏈路調(diào)度算法是NP難的，SINR干擾模型可以處理全局性干擾[19]，如何控制無線信號之間的干擾是個極具挑戰(zhàn)性的問題。基于平面劃分的SINR干擾控制是設(shè)計鏈路調(diào)度算法常用的一種思路[20-23]，其核心思想是：首先，把通信鏈路集劃分為子集，把網(wǎng)絡(luò)區(qū)域劃分為不相交的小區(qū)域；然后，從距離較遠(yuǎn)的小區(qū)域中選擇鏈路集合，采用TDMA運行機制，為鏈路集合分配不同的傳輸時隙，確保同一時隙中的通信鏈路在滿足SINR干擾約束的條件下同時傳輸。常用的平面劃分有正方形和正六邊形劃分。Yu等[20]和馬春梅等[21]采用了蜂窩移動通信系統(tǒng)的六邊形劃分法，把網(wǎng)絡(luò)區(qū)域劃分為正六邊形，從六邊形中選取鏈路集進行調(diào)度。文獻[20]根據(jù)鏈路長度把通信鏈路集劃分為log (lmax/lmin)個子集，其中l(wèi)max是最長鏈路長度，lmin是最短鏈路長度。文獻[21]則為保證QoS的公平性，不對鏈路進行分類，而是所有鏈路一起調(diào)度。Huang等[16]采用正方形劃分的方法劃分網(wǎng)絡(luò)區(qū)域。通常全局性功率分配有一致功率分配和線性功率分配。采用局部功率分配可以優(yōu)化全局功率分配導(dǎo)致的能量消耗，文獻[16]根據(jù)鏈路的長度為鏈路分配不同的傳輸功率，減少能量消耗。本文采用正三角形劃分的方法，把網(wǎng)絡(luò)區(qū)域劃分為不相交的正三角形，將鏈路放入正三角形中進行調(diào)度。首先根據(jù)鏈路的長度把鏈路集劃分為不同的子集，不同的子集把網(wǎng)絡(luò)區(qū)域劃分為邊長不同的正三角形，然后給正三角形有規(guī)律地進行編號，使相鄰的三角形具有不同的編號。從編號相同的每個正三角形中選擇其中的一條鏈路進行調(diào)度，這些正三角形中的鏈路就是一個可同時調(diào)度的鏈路集。

1 網(wǎng)絡(luò)模型及定義

假定一組通信請求為L={l1,l2,l3,…,ln},其中,lv=(sv,rv)(v=1,2,3,…,n)表示從發(fā)送端sv到接收端rv的一條通信鏈路。假設(shè)通信節(jié)點隨機分布在二維平面內(nèi)。節(jié)點sv到rv的歐幾里得距離記為d(lv)=d(sv,rv)。本文將最短鏈路長度歸一化，設(shè)為1。定義2條鏈路lv=(sv,rv)和le=(se,re)之間的距離是sv和re的歐幾里得距離，即d(lv,le)=d(sv,re)。本文使用一致功率分配，記為P，鏈路在rv處的接收功率為Prv=P/dα(lv)，α是路徑損耗指數(shù)(path loss exponent)。如果鏈路lv=(sv,rv)和鏈路le=(se,re)同時調(diào)度，那么鏈路le對鏈路lv的干擾記為Ile(lv)=P/dα(lelv)。在SINR干擾模型中鏈路lv通信成功，當(dāng)且僅當(dāng)：

(1)

成立。其中，N是環(huán)境噪聲，β是SINR約束條件成立的最小閾值，T為可同時調(diào)度的鏈路集合。如果集合T中任意一條鏈路都滿足式(1)，那么集合T就稱為SINR可行集。

本文提出一種基于SINR約束的最短鏈路調(diào)度算法，其目標(biāo)是：給定一組通信鏈路集合L={l1,l2,l3，…，ln}，把L劃分為數(shù)目最少的子集，使每個子集中的鏈路在SINR干擾約束條件下能夠通信成功。即，用最短的時間調(diào)度所有的鏈路。

2 算法設(shè)計

2.1 鏈路分類及平面劃分

然后對鏈路進行分類調(diào)度。對于子集Ai，把網(wǎng)絡(luò)區(qū)域劃分為邊長為μ2i+1(μ是常數(shù))的正三角形。按照如下規(guī)則對三角形進行編號：從左上角開始，第一行的編號為5,4,3,6,1,2的重復(fù)，第二行的編號為6,1,2,5,4,3的重復(fù)，然后重復(fù)第一二行的編號過程至平面劃分完畢。區(qū)域劃分及編號結(jié)果如圖1所示。這樣，子集Ai中的所有鏈路都分布在某個三角形中。如果一條鏈路的發(fā)送端在某個正三角形內(nèi)，那么這條鏈路就屬于該正三角形區(qū)域。

圖1 平面劃分為正三角形并用數(shù)字1到6進行有規(guī)則地編號

2.2 算法描述及偽代碼

算法1調(diào)度偽代碼

Input: A set of linksL;

Output:T1,T2,T3，…，Tt;

2:t=0;

3:for eachAi≠? do

4:Divide the network area into regular triangles with a side lengthμ2i+1;

5:Number the triangles with number 1, 2, …, 6, such that no neighboring triangles have the same number;

6:forj=1 to 6 do

7:t=t+1,Tt=?;

8:for each regular triangle B numbered j do

9:pick one linkl∈Aifrom B;

10:Tt=Tt∪{l};

11：Ai=Ai{l};

12:end for

13:end for

14:end for

15:returnT1,T2,T3,…,Tt;

3 理論分析

證明：不失一般性，假設(shè)可行集Tt?Ai(0i設(shè)lv=(sv,rv)∈Tt，rv在三角形A中，A是圖2中最中心的編號為1的正三角形。由算法1可知Tt中的其他鏈路位于其他編號為1的正三角形中(見圖2)。以A為中心，第一圈有6個編號為1的正三角形，第二圈有12個編號為1的正三角形，依次遞推，第n圈就會有6n個編號為1的正三角形。第一圈三角形中的鏈路與lv的最小距離為奇數(shù)圈的三角形中的鏈路距離lv的最小距離為偶數(shù)圈的三角形中的鏈路距離lv的最小距離為((3h/2)μ-1)2i+1。因為：

所以鏈路lv受到的累加干擾最大是：

Irv

圖2 可同時調(diào)度的鏈路集

證明：不失一般性，考慮鏈路的分類集Ai,并且給出發(fā)送端屬于同一編號的正三角形可以同時調(diào)度鏈路的上限值。假定lv=(sv,rv)∈Ai,最多有M個發(fā)送端與rv屬于同一正三角形。用OSA表示最佳鏈路調(diào)度算法，它最多可以同時調(diào)度一個三角形中的y條鏈路。接下來，證明y(2μ+1)α2α/β。

反證法:假設(shè)在一個正三角形中有超過(2μ+1)α2α/β鏈路同時調(diào)度，根據(jù)SINR模型有：

因此，OSA一次最多調(diào)度三角形中的(2μ+1)α2α/β條鏈路，要調(diào)度所有M條鏈路，OSA需要的時隙數(shù)(用TOSA表示)必須滿足TOSA≥(M/y)。另一方面，假設(shè)算法1在Talgorithm1個時隙中調(diào)度所有鏈路，則Talgorithm1所以，Talgorithm1/TOSA其中即，算法1的近似比為

4 實驗比較

本文用C++編寫程序驗證算法1的有效性。網(wǎng)絡(luò)區(qū)域設(shè)置為2000 m×2000 m的正方形，鏈路數(shù)目分別是200、400、600、800，最短鏈路長度歸一化為1，最長鏈路長度設(shè)置為30，環(huán)境噪聲為-70 dB，α=3，β=10 dB。文獻[22]把平面劃分為正方形并用1、2、3、4編號，其算法記為Blough；文獻[20]把平面劃分為六邊形并用1、2、3編號，有2種功率分配策略，分別是與鏈路類相關(guān)的功率分配和一致功率分配。比較一致功率分配下的算法結(jié)果，記為YuUni。Blough和YuUni是2種典型的平面劃分方案。本文算法記為Zhang，這3種算法的實驗結(jié)果如圖3所示。

圖3 3種典型平面劃分算法的比較結(jié)果

從圖3可以看出，與其它2種方法相比，本文算法的性能更優(yōu)。文獻[22]算法中的“灰黑鏈路”對鏈路調(diào)度的延遲有明顯的影響，平均調(diào)度次數(shù)最大。本文算法與文獻[20]性能相當(dāng)。雖然文獻[20]使用六邊形劃分，用3種不同的編號，但是六邊形的邊長較大；本文使用正三角形劃分，用6種不同的編號，三角形的邊長較小。對于相同的鏈路類來說，編號相同的三角形的數(shù)目是六邊形數(shù)目的1.14倍。所以，在同一時隙，從三角形中選擇的鏈路的數(shù)目是從六邊形中選擇的鏈路的數(shù)目的1.14倍，調(diào)度相同數(shù)目的鏈路時本文所用的時間更短。

5 結(jié)束語

SINR模型的全局干擾特性使得設(shè)計一個可靠性很強的低延遲鏈路調(diào)度是NP難的。本文首先根據(jù)鏈路長度劃分鏈路集，然后由正三角形劃分法進一步劃分子集，通過研究子集內(nèi)可同時調(diào)度的鏈路得到鏈路可行集。同時利用了SINR模型可累計干擾的特點，采用TDMA運行機制避免干擾。由于SINR模型適用于網(wǎng)絡(luò)中的動態(tài)鏈路，所以未來研究的方向可以根據(jù)鏈路的長度和數(shù)目，使鏈路的調(diào)度有一個動態(tài)變化，以在保證低耗的情況下解決鏈路內(nèi)部的干擾問題，從而有效提高功率分配及傳輸信號的可靠性。