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

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

?

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

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

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

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

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

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

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

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

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

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

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

定義1鏈路間距離。對(duì)于鏈路e=（u，v）與e′=(u′,v′)，其距離定義為鏈路兩端節(jié)點(diǎn)間的最小距離，可表示為：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é)點(diǎn)干擾范圍。而當(dāng)確定在鏈路e上分配信道c時(shí)，真正對(duì)鏈路e產(chǎn)生干擾的鏈路為L(zhǎng)e中與其采用同樣信道的鏈路，即：Lc,e={e′|ce′=c,e′∈Le}。

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

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

2　本文算法

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

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

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

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

表1　貪婪信道分配算法

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

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

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

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

圖1　鏈路e干擾范圍圖

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

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

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

對(duì)式（5）進(jìn)行變形，可得：

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

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

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

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

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

表2　隨機(jī)信道分配算法

表3　按序信道分配算法

3　仿真結(jié)果

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

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

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

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

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

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

4　總結(jié)

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

參考文獻(xiàn)：

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

［4］石小川，黃傳河，李楠.基于無(wú)線Mesh網(wǎng)絡(luò)的一種信道分配算法及路由協(xié)議［J］.武漢大學(xué)學(xué)報(bào)（理學(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ǎn)調(diào)度機(jī)制［J］.傳感技術(shù)學(xué)報(bào)，2015，28（2）：254-258.

［9］張龍妹，史浩山，陸偉. DTFMM：一種適應(yīng)于WMSNs的多信道MAC協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，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］.計(jì)算機(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-），男，漢族，河北樂(lè)亭人，碩士，唐山師范學(xué)院講師，研究方向：無(wú)線傳感性能優(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

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1004-1699（2016）03-0429-05