劉玉賓（唐山師范學(xué)院計算機科學(xué)系，河北唐山063000）

?

基于任務(wù)調(diào)度的無線網(wǎng)貪婪信道分配算法*

劉玉賓*
（唐山師范學(xué)院計算機科學(xué)系，河北唐山063000）

摘要：針對無線網(wǎng)絡(luò)鏈路干擾問題，綜合借鑒多處理器任務(wù)調(diào)度算法提出了一種貪婪信道分配算法，為所訪問的無線網(wǎng)鏈路甄選出干擾最小的信道，并且證明了本算法的近似比率為2-1/k，其中為k為可用的正交信道數(shù)，算法復(fù)雜度為O（|E|2）。為了驗證本文算法的可行性和有效性，將本文所提出的貪婪算法與隨機信道分配算法和按序信道分配算法進行了實驗對比。仿真結(jié)果表明：本文所提出的貪婪算法的整體性能優(yōu)于其他兩種算法，并且貪婪算法得到的最大干擾和平均干擾歸一化值隨著可用正交信道數(shù)的變化趨勢較其他兩種算法穩(wěn)定。從而驗證了本文算法能有效的降低鏈路干擾，一定程度上可以提升網(wǎng)絡(luò)吞吐量。

關(guān)鍵詞：無線網(wǎng)絡(luò)鏈路；信道分配；貪婪算法；鏈路干擾；NP-hard；任務(wù)調(diào)度算法

項目來源：河北省高等學(xué)?？茖W(xué)研究計劃項目（Z2015075）；唐山市科學(xué)研究計劃項目（15130203a）；唐山師范學(xué)院團隊建設(shè)項目（2016C08）

隨著無線技術(shù)的發(fā)展，無線網(wǎng)絡(luò)在日常生活中的應(yīng)用越來越廣泛。無線網(wǎng)狀網(wǎng)WMN（Wireless Mesh Network）作為一種多跳無線接入網(wǎng)絡(luò)，可以降低布設(shè)有線接入網(wǎng)的成本，同時也提高了在惡劣環(huán)境中布設(shè)接入網(wǎng)的可能性。但在布設(shè)多跳無線網(wǎng)絡(luò)時需要考慮無線鏈路干擾問題，隨著數(shù)據(jù)傳輸路徑跳數(shù)的增加，鏈路受到干擾的可能性增大，導(dǎo)致網(wǎng)絡(luò)吞吐量降低?，F(xiàn)階段采用多接口多信道無線路由器可應(yīng)對此問題［1］，但需要考慮的一個關(guān)鍵問題就是信道分配。

為了解決無線網(wǎng)絡(luò)的信道分配問題，學(xué)者對此進行了大量的研究和分析。文獻［2］提出了一種分布式的信道分配算法和一種集中式的信道分配算法，貪婪算法的集中式實現(xiàn)復(fù)雜度為O（dK|Vc|3），分布式實現(xiàn)算法復(fù)雜度為O（|Vc|K），其中r為文中算法在循環(huán)過程中產(chǎn)生的近似解個數(shù)，d為沖突圖中節(jié)點度的最大值，Vc為沖突圖中節(jié)點數(shù)（原網(wǎng)絡(luò)中的鏈路）。其中K為可用信道數(shù)。從算法復(fù)雜度方面考慮，在網(wǎng)絡(luò)規(guī)模較大的情況下，該文所提的集中式信道算法并不占優(yōu)勢。文獻［3］中給出了一種負(fù)載感知的分布式靜態(tài)信道分配算法，其首先將鏈路按照負(fù)載由大到小排序。對負(fù)載大的鏈路優(yōu)先分配信道，在信道分配過程中，總是優(yōu)先選擇干擾小的信道。所給算法是一種針對樹形拓?fù)錂C構(gòu)的分層信道分配算法。文獻［4］給出的是一種分布式的信道分布算法，該分布式的信道分配算法需要周期性的更新各收發(fā)器的信道，維持該信道分配算法需占用網(wǎng)絡(luò)資源。文獻［5］給出一種動態(tài)信道分配算法，文章將所研究的信道分配問題映射為list-coloring問題，其信道分配由位于網(wǎng)關(guān)的專用信道分配服務(wù)器完成。文獻［6］通過拓?fù)淇刂频姆椒ɡ镁W(wǎng)絡(luò)信道，其信道分配的目標(biāo)為最小化信道干擾。在文獻［7］中的min-max著色圖問題已證明為NP-hard問題。文獻［8］結(jié)合多信道技術(shù)與時分多路訪問技術(shù)的節(jié)點調(diào)度算法，提出了信道分配與時隙調(diào)整機制，在可用無線信道有限的約束條件下，實現(xiàn)了時隙重用并最小化有限信道約束對優(yōu)化節(jié)點狀態(tài)切換次數(shù)的影響。文獻［9］基于分簇網(wǎng)絡(luò)拓，提出了一種無沖突的分布式時分/頻分多信道MAC協(xié)議，該協(xié)議在于充分復(fù)用了可用的多信道頻率資源，提高了網(wǎng)絡(luò)吞吐量。

文獻［2-9］已對信道分配做了大量研究，在這些研究中，信道分配需要達到的目標(biāo)不同，但所需解決的問題均為NP-hard問題。為了有效解決無線網(wǎng)絡(luò)鏈路干擾問題，本文借鑒多處理器任務(wù)調(diào)度算法的精髓，給出一種不同于現(xiàn)有算法的集中式貪婪信道分配算法以解決NP-hard問題，最終實現(xiàn)最小化最大鏈路干擾。

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

本文將全網(wǎng)看作一個無向圖，用G=（V，E）表示，其中V表示網(wǎng)絡(luò)中的所有節(jié)點，E表示網(wǎng)絡(luò)中的所有鏈路。對于任意節(jié)點v∈V，其鄰居節(jié)點的個數(shù)與節(jié)點上配備的無線接口數(shù)目一致。F={f1，f2，…，fn}表示全體數(shù)據(jù)流集合，用集合R={r1，r2，…，rn}表示各數(shù)據(jù)流在源節(jié)點的數(shù)據(jù)產(chǎn)生速率。每一數(shù)據(jù)流具有指定的路徑，用集合P={p1，p2，…，pn}表示相應(yīng)數(shù)據(jù)流的路徑。當(dāng)pi包含鏈路e時，令xie=1；否則。則鏈路e上的負(fù)載大小可表示為：

假設(shè)Le表示鏈路e的干擾范圍內(nèi)的所有鏈路（不包括鏈路e），ce表示鏈路e上分配的信道。并且d（u，v）表示節(jié)點u與節(jié)點v間的歐拉距離。通過定義1和定義2分別給出鏈路間距離和鏈路干擾范圍內(nèi)干擾鏈路的定義，通過定義3明確給出鏈路受到的干擾大小。

定義1鏈路間距離。對于鏈路e=（u，v）與e′=(u′,v′)，其距離定義為鏈路兩端節(jié)點間的最小距離，可表示為：d(e,e′)=min{d(u,u′),d(u,v′),d(v,u′),d(v,v′)}。

定義2干擾鏈路集合。鏈路e的干擾范圍內(nèi)的鏈路集合為其干擾域中所有鏈路，即：Le={e′|d(e,e′)≤RI,e′∈E}，其中RI為節(jié)點干擾范圍。而當(dāng)確定在鏈路e上分配信道c時，真正對鏈路e產(chǎn)生干擾的鏈路為Le中與其采用同樣信道的鏈路，即：Lc,e={e′|ce′=c,e′∈Le}。

定義3鏈路干擾大小。若鏈路e上分配信道c，則其受到的干擾大小為其自身流量與其所有干擾鏈路的流量之和，即。此值實際上也可表示鏈路e干擾域中信道c上流量干擾值或負(fù)載值。

令I(lǐng)max為網(wǎng)絡(luò)中各鏈路干擾的最大值，即Imax= me∈aEx {Ice,e}。本文的目的旨在尋找一種信道分配算法，將特定的信道C={c1，c2，…，ck}分配給網(wǎng)絡(luò)中的鏈路，每個鏈路獲得唯一的信道，最終使Imax的值最小。

2　本文算法

最小化最大鏈路干擾問題即為NP-hard問題［10］，為了解決NP-hard問題，本文綜合借鑒多處理器任務(wù)調(diào)度算法［11］，給出了一個簡單有效的貪婪信道分配算法，并詳細(xì)分析其近似比率。在具體介紹貪婪信道分配算法之前，先給出多處理器任務(wù)調(diào)度問題的一般表述。

多處理器任務(wù)調(diào)度問題可描述為［12］：給定一個任務(wù)集合J={j1，j2，…，ja}，各任務(wù)彼此獨立，并且任務(wù)ji的執(zhí)行時間為ti，共有M個處理器，要使完成所有任務(wù)的總時長開銷最短，其實就是解決典型的NP-hard問題［13］。

若將信道視為處理器，將每條鏈路視為一個任務(wù)，網(wǎng)絡(luò)中的m條鏈路映射為調(diào)度問題中的m個任務(wù)，鏈路負(fù)載視為任務(wù)處理時間，則本文考慮的最小化最大鏈路干擾信道分配問題類似于多處理器任務(wù)調(diào)度問題。兩者最大的區(qū)別在于：在信道分配問題中，鏈路受到的干擾并不是彼此獨立的；而在多處理器任務(wù)調(diào)度問題中，各任務(wù)彼此獨立。

針對鏈路彼此依賴的信道分配問題，本算法在考慮為鏈路e分配信道時，每次選擇le+Ice,e值最小的信道ce分配給鏈路e。表1中，給出了該貪婪信道分配算法的偽代碼。在定理1中，本文證明該貪婪算法的近似比率為2-1/k，其中k為可用的正交信道數(shù)。

表1　貪婪信道分配算法

定理1對于本文描述的最小化最大鏈路干擾信道分配問題，表1中所給出的貪婪信道分配算法為（2-1/k）-近似算法，并且該算法的時間復(fù)雜度為O（|E|2）。

證明假設(shè)η為任意最優(yōu)信道分配算法，該算法得到的最大鏈路干擾用Iη表示。此干擾值不小于網(wǎng)絡(luò)中任意單條鏈路的負(fù)載值，即：

假設(shè)de表示鏈路e干擾范圍內(nèi)的鏈路數(shù)，并且此de條鏈路共利用了k′(k′≤k)個信道（k為可用的正交信道數(shù)）。由于Iη為最大鏈路干擾值，則其大小至少不低于其干擾范圍內(nèi)所有鏈路負(fù)載值平均值與鏈路e負(fù)載∑值之和。鏈路e干擾范圍內(nèi)所有鏈路的流量值為le′，則可得：

為更清楚的說明（3）式，如圖1所示鏈路e及其干擾域中所有鏈路。

圖1　鏈路e干擾范圍圖

假設(shè)總共有c1，c2，c33個正交信道，將信道c1分配給鏈路e1和e2；將信道c2分配給鏈路e3，e4與e5；將信道c3分配給鏈路e，e6與e7。則有。此干擾域中，信道c1上的干擾，信道c2上的干擾為。由于Iη為干擾最大值，則有Iη≥I（c1）以及Iη≥I（c2），進而有Iη≥（1/3）（I（c1）+I（c2）+ Iη），即為式（3）在此例中的表示。

假設(shè)Ig表示由本文所給出的貪婪信道分配算法產(chǎn)生的鏈路干擾最大值，并且該干擾發(fā)生在鏈路e上，所分配給鏈路e的信道為c*。鏈路信道分配算法總是選擇干擾最小的信道分配給鏈路，則當(dāng)分配給鏈路c (c≠c*)時，鏈路e上受到的干擾將不小于Ig，即，

將式（4）左右兩邊的表達式在所有信道c∈C上累加，可得：

對式（5）進行變形，可得：

將式（2）和式（3）帶入式（6）可到：

至此，證明了對于本文描述的最小化最大鏈路干擾信道分配問題，表1中所給出的貪婪信道分配算法為（2-1/k）-近似算法。由于表1中算法第3行需循環(huán)執(zhí)行k次，而Ic，e值的計算需訪問鏈路e的干擾鏈路，在任意拓?fù)洵h(huán)境下，任一鏈路的干擾鏈路數(shù)小于全網(wǎng)鏈路數(shù)|E|，故而可認(rèn)為代碼中第2行至第4行最差情況下需執(zhí)行k|E|次。對每一鏈路e∈E，都需做同樣的操作，考慮到k為常數(shù)，故而算法時間復(fù)雜度為O（|E|2）。

目前以最小化最大鏈路為目標(biāo)的信道分配算法中，沒有公認(rèn)的最好算法，特別是針對任意網(wǎng)絡(luò)拓?fù)?，沒有相應(yīng)的算法，本文所提的信道分配算法可以應(yīng)用于任意網(wǎng)絡(luò)拓?fù)洵h(huán)境。為了進行對比分析，本文給出另外兩種信道分配算法：隨機信道分配算法與按序信道分配算法。

在隨機信道分配算法中，當(dāng)為鏈路e分配信道

則本文貪婪算法的近似比率為：時，從信道集合C中隨機選擇選擇一個信道分配給鏈路e。表2、表3分別為隨機信道分配算法與按序信道分配算法的偽代碼，在算法中，隨機給網(wǎng)絡(luò)中鏈路編號，對于編號為label的鏈路，分配的信道號為“l(fā)a?bel mode k”。本文不從理論上分析隨機信道分配算法和按序信道算法的性能，將通過仿真結(jié)果進行對比分析。

表2　隨機信道分配算法

表3　按序信道分配算法

3　仿真結(jié)果

本節(jié)利用Visual Studio 2013實現(xiàn)上述三種信道分配算法，通過仿真分析給出信道分配算法的性能。仿真中模擬兩種網(wǎng)絡(luò)拓?fù)洌焊裥尉W(wǎng)絡(luò)拓?fù)渑c隨機網(wǎng)絡(luò)拓?fù)?。網(wǎng)絡(luò)中共有100個節(jié)點，30個數(shù)據(jù)流，每一數(shù)據(jù)流具備唯一的源節(jié)點和目的節(jié)點。源節(jié)點和目的節(jié)點均從100個節(jié)點中隨機選擇，并且源節(jié)點和目的節(jié)點不為同一個節(jié)點。每一數(shù)據(jù)流采用的路徑為跳數(shù)最少路徑，數(shù)據(jù)流的速率為1 Mbit/s至10 Mbit/s之間選擇的隨機整數(shù)值。

由于在常用的IEEE 802.11a/b/g協(xié)議中，可支持的最大正交信道數(shù)位IEEE 802.11a提供的12個信道。故在仿真中，本文設(shè)置將可用正交信道值從1增加至12，觀察各信道分配算法的歸一化鏈路最大干擾和歸一化全網(wǎng)鏈路平均干擾值。所謂歸一化值即為仿真得到的干擾值對全網(wǎng)鏈路總負(fù)載進行的歸一化。為便于觀察，圖2與圖3中以歸一化干擾值0.1作為基準(zhǔn)值，給出了基準(zhǔn)線。

圖2　格形網(wǎng)絡(luò)拓?fù)滏溌犯蓴_對比圖

圖3　隨機網(wǎng)絡(luò)拓?fù)滏溌犯蓴_對比圖

圖2給出了在格形網(wǎng)絡(luò)拓?fù)鋱鼍跋碌慕Y(jié)果。從圖2（a）和圖2（b）中看出，隨著可用正交信道數(shù)的增加，最大鏈路干擾歸一化值和平均鏈路干擾歸一化值呈現(xiàn)下降趨勢，說明采用多接口多信道能有效降低無線網(wǎng)絡(luò)中的干擾。對比三種信道分配算法，可以看出：不管是最大鏈路干擾還是平均鏈路干擾，貪婪信道分配算法的性能都是三者中最優(yōu)的。并且從圖中曲線隨著信道數(shù)的變化趨勢來看，貪婪信道分配算法得到的最大鏈路干擾和平均鏈路干擾是隨著信道數(shù)值廣義遞減的，而隨機信道分配算法與按序信道分配算法并不是廣義遞減，其變化曲線呈現(xiàn)曲折狀態(tài)。

圖3給出的為隨機網(wǎng)絡(luò)拓?fù)鋱鼍跋骆溌纷畲蟾蓴_與平均干擾歸一化值隨信道數(shù)增加的變化趨勢。各曲線呈現(xiàn)的趨勢與圖2中曲線類似，但對應(yīng)于不同信道數(shù)值的干擾值要普遍高于圖2中的值。在圖3（a）中，當(dāng)可用正交信道數(shù)為3時，貪婪信道分配算法得到的最大鏈路干擾歸一化值要稍高于其他兩種算法，產(chǎn)生這一現(xiàn)象的原因在于對于最小化最大鏈路干擾值這一問題來說，貪婪信道算法也只是一種近似算法，而絕非最優(yōu)算法，在某些場景下，會存在其他算法得到的性能優(yōu)于該貪婪算法。通過對三種信道分配算法的對比來看，本文所提出的貪婪算法的整體性能優(yōu)于其他兩種算法，并且貪婪算法得到的最大干擾和平均干擾歸一化值隨著可用正交信道數(shù)的變化趨勢較其他兩種算法穩(wěn)定。當(dāng)網(wǎng)絡(luò)干擾較低時，網(wǎng)絡(luò)的吞吐量性能則會提高。故本文所給的貪婪信道分配算法，能有效的降低鏈路干擾，從而提升網(wǎng)絡(luò)吞吐量。

4　總結(jié)

最小化最大鏈路干擾信道分配問題歸根到底就是NP-hard問題，本文提出了一種貪婪信道分配算法，為所訪問鏈路選擇干擾最小的信道，該貪婪算法為（2-1/k）-近似算法，其算法復(fù)雜度為O（|E|2）。通過模擬格形網(wǎng)絡(luò)拓?fù)渑c隨機網(wǎng)絡(luò)拓兩種網(wǎng)絡(luò)拓?fù)?，可以得出：在格形網(wǎng)絡(luò)拓?fù)鋱鼍跋拢S著可用正交信道數(shù)的增加，婪信道分配算法得到的最大鏈路干擾和平均鏈路干擾是廣義遞減，而隨機信道分配算法與按序信道分配算法呈現(xiàn)曲折狀態(tài)，但與兩種對比算法相比，更能有效降低無線網(wǎng)絡(luò)中的干擾。而在隨機網(wǎng)絡(luò)拓?fù)鋱鼍跋拢m然在不同可用正交信道數(shù)下，本文算法的最大鏈路干擾歸一化值要稍高于其他兩種算法，但在整體性能上優(yōu)于其他兩種算法。通過對比不同拓?fù)淝闆r下的鏈路干擾值，表明在進行網(wǎng)絡(luò)部署時，規(guī)則的格形網(wǎng)絡(luò)拓?fù)湫阅芨鼉?yōu)。如何解決貪婪信道算法的最優(yōu)化問題將是以后信道分配研究的方向。

參考文獻：

［1］Ashish Raniwala，Kartik Gopalan，Tzi-cker Chiueh. Centralized Channel Assignment and Routing Algorithms for Multi-Channel Wireless Mesh Networks［J］. Mobile Computing and Communica?tions Review，2004，8（2）：50-55.

［2］Anand Prabhu Subramanian，Himanshu Gupta，Samir R. Das. Minimum-Interference Channel Assignment in Multi-Radio Wire?less Mesh Networks［J］. IEEE Transactions On Mobile Comput?ing，2008，7（12）：1459-1473.

［3］邱振謀.多接口多信道無線Mesh網(wǎng)絡(luò)中的信道分配研究［D］.南京:東南大學(xué)，2011.

［4］石小川，黃傳河，李楠.基于無線Mesh網(wǎng)絡(luò)的一種信道分配算法及路由協(xié)議［J］.武漢大學(xué)學(xué)報（理學(xué)版），2011，57（2）：155-164.

［5］Krishna N. Ramachandran，Elizabeth M. Belding，Kevin C. Alme?roth，Milind M. Buddhikot. Interference-Aware Channel Assign?ment in Multi-Radio Wireless Mesh Networks［C］. Infocom 2006，2006：1-12.

［6］Mahesh K. Marina a，Samir R. Das b，Anand Prabhu Subramani?an. A Topology Control Approach for Utilizing Multiple Channels in Multi-Radio Wireless Mesh Networks［C］. Broad Nets 2005，2005：381-390.

［7］Arunesh Mishra，Suman Banerjee，William Arbaugh. Weighted Coloring Based Channel Assignment in WLANs［J］. ACM Sigmo?bile Mobile Computing and Communications Review，2005，9（3）：19-31.

［8］曾波，李珊珊，王輝.一種基于有限信道的能量高效節(jié)點調(diào)度機制［J］.傳感技術(shù)學(xué)報，2015，28（2）：254-258.

［9］張龍妹，史浩山，陸偉. DTFMM：一種適應(yīng)于WMSNs的多信道MAC協(xié)議［J］.傳感技術(shù)學(xué)報，2011，24（3）：452-456.

［10］Mercedes Hidalgo-Herrero，Pablo Rabanal，Ismael Rodriguez，et al. Comparing Problem Solving Strategies for NP-hard Optimiza?tion Problems［J］. Fundamenta Informaticae，2013，124（2）：1-25.

［11］Garey，Michael R，Johnson，David S. Computers and Intractabili?ty：A Guide to the Theory of NP-Completeness［M］. W. H. Free?man and Company，238.

［12］楊輝華，張曉鳳，謝譜模，等.基于布谷鳥搜索的多處理器任務(wù)調(diào)度算法［J］.計算機科學(xué)，2015，42（1）：86-87.

［13］Graham R L. Bounds for Certain Multiprocessing Anomalies［J］. Bell System Technical Journal，1966，45：1563-1581.

劉玉賓（1981-），男，漢族，河北樂亭人，碩士，唐山師范學(xué)院講師，研究方向：無線傳感性能優(yōu)化與仿真、物聯(lián)網(wǎng)技術(shù)，liuyubing_81@126.com。

Greedy Channel Assignment Algorithm for Wireless Networks Based on Task Scheduling*

LIU Yubin*
（Department of Computer Science，Tangshan Normal University，Tangshan Hebei 063000，China）

Abstract：Aiming at the problem of link interference in wireless networks，this paper proposes a greedy channel al?location algorithm based on multi processor task scheduling algorithm，which is the minimum channel for the access link selection. At the same time，the approximate ratio of the proposed algorithm is 2-1/k，and the k is the available orthogonal channel number，and the complexity of the algorithm is O（|E|2）.In order to verify the feasibility and effec?tiveness of the proposed algorithm，the proposed algorithm is compared with the random channel assignment algo?rithm and the random channel assignment algorithm. The simulation results show that the overall performance of the proposed algorithm is better than the other two algorithms，and the maximum interference and average interference normalized values obtained by the greedy algorithm are more stable than the other two algorithms.So the algorithm can effectively reduce the link interference，and can improve the network throughput in acertain degree.

Key words：wireless network link；channel allocation；greedy algorithm；NP-hard；task scheduling

doi：EEACC：6250Z；7220；6150P10.3969/j.issn.1004-1699.2016.03.021

收稿日期：2015-10-10修改日期：2015-12-05

中圖分類號：TP393

文獻標(biāo)識碼：A

文章編號：1004-1699（2016）03-0429-05