無線網(wǎng)絡(luò)中可靠的鏈路調(diào)度算法設(shè)計(jì)與分析

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

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

0 引 言

無線網(wǎng)絡(luò)通信技術(shù)中一些應(yīng)用領(lǐng)域?qū)νㄐ诺目煽啃砸蠛芨?，如無線網(wǎng)絡(luò)工業(yè)通信[1-2]、軍事通信等。但是信號(hào)傳輸衰落及信號(hào)之間的干擾通常會(huì)降低網(wǎng)絡(luò)容量，導(dǎo)致無線通信失敗?；赟INR(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]，即最大化單時(shí)隙內(nèi)可以并發(fā)調(diào)度的鏈路數(shù)目；2)最短鏈路調(diào)度[14-18]，即用最少的時(shí)隙調(diào)度所有鏈路。

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

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

假定一組通信請求為L={l1,l2,l3,…,ln},其中,lv=(sv,rv)(v=1,2,3,…,n)表示從發(fā)送端sv到接收端rv的一條通信鏈路。假設(shè)通信節(jié)點(diǎn)隨機(jī)分布在二維平面內(nèi)。節(jié)點(diǎn)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)同時(shí)調(diào)度，那么鏈路le對(duì)鏈路lv的干擾記為Ile(lv)=P/dα(lelv)。在SINR干擾模型中鏈路lv通信成功，當(dāng)且僅當(dāng)：

(1)

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

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

2 算法設(shè)計(jì)

2.1 鏈路分類及平面劃分

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

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

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中最中心的編號(hào)為1的正三角形。由算法1可知Tt中的其他鏈路位于其他編號(hào)為1的正三角形中(見圖2)。以A為中心，第一圈有6個(gè)編號(hào)為1的正三角形，第二圈有12個(gè)編號(hào)為1的正三角形，依次遞推，第n圈就會(huì)有6n個(gè)編號(hào)為1的正三角形。第一圈三角形中的鏈路與lv的最小距離為奇數(shù)圈的三角形中的鏈路距離lv的最小距離為偶數(shù)圈的三角形中的鏈路距離lv的最小距離為((3h/2)μ-1)2i+1。因?yàn)椋?/p>

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

Irv

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

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

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

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

4 實(shí)驗(yàn)比較

本文用C++編寫程序驗(yàn)證算法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。文獻(xiàn)[22]把平面劃分為正方形并用1、2、3、4編號(hào)，其算法記為Blough；文獻(xiàn)[20]把平面劃分為六邊形并用1、2、3編號(hào)，有2種功率分配策略，分別是與鏈路類相關(guān)的功率分配和一致功率分配。比較一致功率分配下的算法結(jié)果，記為YuUni。Blough和YuUni是2種典型的平面劃分方案。本文算法記為Zhang，這3種算法的實(shí)驗(yàn)結(jié)果如圖3所示。

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

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

5 結(jié)束語

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