無線Ａｄ ｈｏｃ網(wǎng)絡(luò)中分布式極大吞吐率調(diào)度算法研究

(電子科技大學(xué) 通信與信息工程學(xué)院， 成都 610054)



摘要：針對無線Ad hoc網(wǎng)絡(luò)廣播鏈路的特點，在更一般的鏈路干擾約束模型下，設(shè)計了一種分布式、貪婪的極大吞吐率調(diào)度算法。通過運用Laypunov定理，證明了該調(diào)度算法的穩(wěn)定區(qū)域是網(wǎng)絡(luò)最大穩(wěn)定區(qū)域的γ倍（0<γ<1）。通過仿真驗證了該算法性能接近集中式的GMM（貪婪極大匹配）調(diào)度算法。

關(guān)鍵詞：分布式極大調(diào)度；2跳鏈路干擾約束；穩(wěn)定區(qū)域；局部拓撲

中圖分類號：TP393文獻標(biāo)志碼：A

文章編號：1001-3695(2008)11-3440-05



Research on distributed maximal throughputscheduling algorithm in wireless Ad hoc network

WU Fan，MAO Yu-ming，MAO Jian-bing，LENG Su-peng

(School of Communication Information Engineering， University of Electronic Science Technology of China， Chengdu 610054， China)Abstract:Aiming at the broadcasting link characteristics in wireless Ad hoc， this paper designed a distributed greed maximal throughput scheduling algorithm which was under a more general link interference constraint model. By using Laypunov theorem， this paper proves that the scheduling algorithm can achieve the stability region which reduced the maximum stability region of the network by the factor of γ (0 <γ <1). The simulation results show that the algorithm performance get close to the centralized GMM (greed maximal match) scheduling algorithm.



Key words:distributed maximal scheduling;two-hop link interference constraint model;stability region;local topology



0引言

在無線Ad hoc網(wǎng)絡(luò)中，由于任意一條無線傳輸鏈路都可能和地理位置與其相鄰的其他無線鏈路相互干擾，從而使得無線鏈路間形成了某種約束關(guān)系，也即是在每一個時刻，網(wǎng)絡(luò)中只能有部分鏈路同時傳輸，而干擾這些鏈路的其他鏈路均不能被使用。所以，無線Ad hoc網(wǎng)絡(luò)鏈路調(diào)度是研究在某種特定無線鏈路干擾約束條件下，網(wǎng)絡(luò)中哪些鏈路能夠互不干擾地并行工作，進而達到某種網(wǎng)絡(luò)性能的優(yōu)化。

文獻[1]首先提出了一種基于最大權(quán)重的無線Ad hoc網(wǎng)絡(luò)鏈路調(diào)度算法，并證明了該調(diào)度算法可以達到網(wǎng)絡(luò)最大吞吐率。這一調(diào)度思想后來被廣泛地應(yīng)用于無線Ad hoc網(wǎng)絡(luò)資源分配的跨層優(yōu)化研究中^[2~5]。但是，這種最大權(quán)重調(diào)度算法是集中式的，計算較為復(fù)雜，而對于無中心的Ad hoc網(wǎng)絡(luò)，分布式、低計算復(fù)雜度的調(diào)度算法將更加適合。借鑒高速交換結(jié)構(gòu)中的調(diào)度思想^[6]，一類極大調(diào)度(maximal scheduling)算法被引入了無線Ad hoc網(wǎng)絡(luò)鏈路調(diào)度的研究^[7~9]，這類調(diào)度策略通過犧牲部分吞吐率，從而簡化計算復(fù)雜度。可以證明，這類調(diào)度算法所能達到的吞吐率能夠達到最大吞吐率某個下界區(qū)域。

GMM(greedy maximal matching，貪婪極大匹配)是一種簡單的集中式極大調(diào)度算法，在最簡單的無線鏈路干擾約束（即1跳無線鏈路干擾模型）下，該算法可以保證達到最大吞吐率的1/2。而本文在更一般的無線鏈路干擾約束下，結(jié)合無線Ad hoc網(wǎng)絡(luò)中鏈路的廣播特性，提出了一種分布式極大吞吐率調(diào)度算法。算法通過鄰居節(jié)點間相互交換2跳生成子圖，完成局部調(diào)度信息的搜集，各節(jié)點根據(jù)局部信息執(zhí)行貪婪調(diào)度算法完成鏈路調(diào)度。本文還運用Laypunov穩(wěn)定性定理證明了該算法至少能夠達到網(wǎng)絡(luò)最大吞吐率的某個確定下界。

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

本文將無線Ad hoc網(wǎng)絡(luò)抽象成有向圖G(V，E)。其中:V表示節(jié)點集合；E表示有向邊集合。并且假設(shè)|V| = N，|E|=L，即網(wǎng)絡(luò)中有N個節(jié)點，L條有向邊。l＝(i， j)∈E，表示從發(fā)送節(jié)點i到接收節(jié)點j間存在一條無線通信鏈路。用b(l)=i和e(l)=j分別表示鏈路l的發(fā)送節(jié)點和接收節(jié)點。假設(shè)系統(tǒng)是分時隙工作的，用t表示第t個時隙，t∈{0，1，2，…}。

隨機過程Al(t)表示在時隙t內(nèi)到達鏈路l的分組數(shù)，假設(shè)分組滿足1跳流量模型，即到達鏈路l的分組通過鏈路l離開網(wǎng)絡(luò)。如果到達過程Al(t)是平穩(wěn)的且各態(tài)歷經(jīng)，其平均到達率E[Al(t)] = λl。設(shè)向量λ=(λ1，λ2，…，λL)T為整個網(wǎng)絡(luò)的分組平均到達率。rl(t)表示第t時隙鏈路l的數(shù)據(jù)傳輸率（單位：packet/slot），其取值受到多種因素的制約。本文著重考慮鏈路間相互干擾對鏈路容量的影響，所以假設(shè)每條鏈路l的信道容量是固定值Cl，根據(jù)鏈路l是否被調(diào)度，其數(shù)據(jù)傳輸率在時隙t內(nèi)要么為rl(t)=Cl，要么為0。定義向量r(t)=(r1(t)，r2(t)，…，rL(t))T，表示在某種調(diào)度策略下時隙t內(nèi)一組可行的鏈路數(shù)據(jù)傳輸率。其中

rl(t)=Cl鏈路l 被調(diào)度

0鏈路l未被調(diào)度

R(t)={r(t)}表示在時隙t，網(wǎng)絡(luò)中所有可行的鏈路數(shù)據(jù)傳輸率向量的集合。定義r=(r1，r2，…，rL)是網(wǎng)絡(luò)鏈路的平均數(shù)據(jù)傳輸率。其中：ri=limt→∞ 1/tt-1τ=0ri(τ)， R={r}表示網(wǎng)絡(luò)中所有可行鏈路平均數(shù)據(jù)傳輸率向量的集合。

Ql(t)表示時隙t時，鏈路l上的分組隊列長度，并假設(shè)Q(t)=(Q1(t)，Q2(t)，…，QL(t))T。如果將每條無線鏈路看成是一個服務(wù)者，那么無線Ad hoc網(wǎng)絡(luò)可以被認為是一個約束排隊網(wǎng)絡(luò)^[1]。其中，每個隊列Ql的動態(tài)狀態(tài)可以通過下式給出：

Ql(t+1)=max[Ql(t)-rl(t)，0]+Al(t)

對于一個排隊系統(tǒng)，如果其時平均隊列長度是有限的，那么就稱該隊列是穩(wěn)定的，即鏈路l的隊列是穩(wěn)定的，如果滿足limt→∞ sup 1/tt-1τ=0E{Ql(τ)}＜∞。

如果一個排隊網(wǎng)絡(luò)內(nèi)所有排隊隊列長度始終都能保持有限的，那么就稱該網(wǎng)絡(luò)是穩(wěn)定的。

2鏈路調(diào)度算法及其穩(wěn)定區(qū)域

基于上述網(wǎng)絡(luò)模型的假設(shè)，無線Ad hoc網(wǎng)絡(luò)中鏈路調(diào)度的含義為：在每一個時隙t開始時刻，調(diào)度算法按照無線鏈路干擾約束條件，確定網(wǎng)絡(luò)中哪些鏈路工作，哪些鏈路不能工作，并且要求調(diào)度算法能夠保證網(wǎng)絡(luò)最終達到穩(wěn)定。

文獻[1]將在調(diào)度算法下，所有能夠通過網(wǎng)絡(luò)穩(wěn)定傳輸?shù)钠骄纸M到達率向量的集合Λ={λ}定義為調(diào)度算法的穩(wěn)定區(qū)域或者容量區(qū)域(capacity region)。而對于某一給定網(wǎng)絡(luò)，將所有調(diào)度算法穩(wěn)定區(qū)域的并集稱之為該網(wǎng)絡(luò)的最大穩(wěn)定區(qū)域Λ，或者稱為最優(yōu)容量區(qū)域(optimal capacity region)。那么，如果某種調(diào)度算法opt，其容量區(qū)域能夠達到Λ，就稱該調(diào)度策略為最大吞吐率調(diào)度或最優(yōu)調(diào)度。

根據(jù)文獻[1，3]，最優(yōu)容量區(qū)域Λ可以表示為Λ={λ|λ≤μ，μ∈Co(R)}。其中：Co(R)表示集合R的凸集；μ是Co(R)內(nèi)的一點，表示網(wǎng)絡(luò)鏈路的平均傳輸率。也就是說，如果某組λ′∈Λ，那么就一定存在某組μ′∈Co(R)，使得λ′=μ′。

文獻[1]提出了一種基于積壓隊列差的調(diào)度算法，并證明這是一類最大吞吐率調(diào)度算法。根據(jù)上述最優(yōu)調(diào)度算法，時隙t的鏈路調(diào)度問題被轉(zhuǎn)換為以下形式的優(yōu)化問題：

r(t)=arg maxr(t)∈R(t)Ll=1Ql(t)rl(t)

求解該優(yōu)化問題的計算復(fù)雜度與可行域R緊密相關(guān)，而根據(jù)模型假設(shè)可知，R的取值空間直接由無線鏈路干擾約束模型確定。在不同的鏈路干擾約束模型下，問題求解的復(fù)雜度是不同的。

21無線鏈路干擾約束模型

無線鏈路干擾約束的一般模型是：對于任意一條無線鏈路l，存在一組相應(yīng)的干擾鏈路集合I(l)E，I(l)中任意一條鏈路k都與鏈路l相互干擾，不能同時傳輸，即鏈路l與集合I(l)中的鏈路不能同時被調(diào)度。

典型的無線鏈路干擾約束模型有兩類，即1跳無線鏈路干擾約束和2跳無線鏈路干擾約束。

1跳無線鏈路干擾約束又被稱為節(jié)點排斥干擾模型(node-exclusive interference model)。該模型對鏈路調(diào)度的約束是在被調(diào)度的工作鏈路中，任意兩條鏈路都沒有公共節(jié)點，即對于鏈路l，其I(l)就是鏈路l的1跳范圍內(nèi)的所有鄰居鏈路。以圖1(a)為例，如果有向鏈路l工作，那么在該鏈路1跳范圍內(nèi)的鏈路均不能工作。這種干擾模型適用于類似于藍牙或者FH-CDMA等具有多個可以獨立信道的通信系統(tǒng)。實質(zhì)上，根據(jù)圖論理論，被調(diào)度的無線鏈路集合就是圖G中的一個匹配。所以優(yōu)化問題就轉(zhuǎn)換為最大權(quán)重匹配(maximum weighted matching，MWM)問題，其中鏈路l的權(quán)重Wl=Ql(t)rl(t)。對于MWM問題，存在計算復(fù)雜度為O(N3)的集中式算法^[10]。

2跳無線鏈路干擾約束用來描述類似采用IEEE 802.11 MAC技術(shù)的Ad hoc網(wǎng)絡(luò)，通信節(jié)點間在數(shù)據(jù)通信前后，需要通過握手交互控制信息（數(shù)據(jù)傳輸前的RTS-CTS；數(shù)據(jù)傳輸中的DATA-ACK）。所以這類網(wǎng)絡(luò)中鏈路干擾對調(diào)度的約束是任意被調(diào)度的無線鏈路，在其收、發(fā)節(jié)點的通信范圍內(nèi)不允許其他節(jié)點同時被調(diào)度。也就是說鏈路l的干擾鏈路集合I(l)就是所有的1跳相鄰鏈路，以及所有與鏈路l的頂點b(l)，e(l)相鄰的2跳鏈路。以圖1(b)為例，如果有向鏈路l工作，那么在該鏈路2跳范圍內(nèi)的鏈路均不能工作。文獻[7]指出，在這種約束模型下，最優(yōu)調(diào)度算法是一個NP-hard問題。

22無線鏈路次優(yōu)吞吐率調(diào)度算法

在鏈路干擾約束下，求解鏈路調(diào)度問題的最優(yōu)解是十分困難的，文獻[4]提出一種調(diào)度研究思路：設(shè)法尋找鏈路調(diào)度問題的次優(yōu)解(suboptimal solution)。這類調(diào)度算法的容量區(qū)域只能達到網(wǎng)絡(luò)最優(yōu)容量區(qū)域的γ倍（γ稱為效用比例，γ∈(0， 1)）。也就是說，如果某種調(diào)度算法對于任何λ∈γΛ的數(shù)據(jù)流都能保證網(wǎng)絡(luò)是穩(wěn)定的，那么就稱該調(diào)度算法是次優(yōu)吞吐率調(diào)度算法或者非完美調(diào)度算法。

在1跳無線鏈路干擾約束下，GMM算法^[4，6]是一種較為簡單的次優(yōu)調(diào)度算法。該算法的基本思想是：首先從鏈路集合E中選出權(quán)重最大的邊e加入到調(diào)度集合，然后從E中去掉所有與e相鄰的邊，在剩下邊中重復(fù)執(zhí)行上述操作，直到集合E為空。該算法是一種集中式算法，其計算復(fù)雜度為O(L log L)，其中L為鏈路數(shù)目。可以證明GMM能夠保證γ≥1/2^[6]。MM(maximal-matching )算法^[4]是一種分布式的次優(yōu)調(diào)度算法，效用比例γ≥1/2，計算復(fù)雜度為O(log4 N)。

3分布式貪婪極大調(diào)度算法設(shè)計

本文借鑒GMM算法的思想，并且采用2跳無線鏈路干擾約束，提出一種分布式的貪婪極大調(diào)度(distributed greedy maxi-mal scheduling，DGMS)算法。

分析GMM算法可以發(fā)現(xiàn)，鏈路干擾約束實質(zhì)體現(xiàn)在：對于任意一條鏈路l，在l本身和其相應(yīng)的鏈路干擾集合I(l)中，有且僅有一條鏈路被調(diào)度。而如果充分利用無線Ad hoc網(wǎng)絡(luò)鏈路的廣播特性，使得每個節(jié)點都能掌握所有以自己為頂點的鏈路的干擾鏈路集合以及相應(yīng)權(quán)重，那么就可以設(shè)計出分布式的極大調(diào)度算法。其基本思想是，如果鏈路l在{l}∪I(l)中具有最大的權(quán)重，那么鏈路l就成為調(diào)度鏈路，I(l)中的其他鏈路成為非調(diào)度鏈路，網(wǎng)絡(luò)中其余調(diào)度狀態(tài)未確定的鏈路修正各自的鏈路干擾集合；重復(fù)執(zhí)行算法，直至所有鏈路的調(diào)度狀態(tài)都被確定。

31構(gòu)造調(diào)度局部拓撲圖

分布式貪婪極大調(diào)度算法要求網(wǎng)絡(luò)中任意一個節(jié)點i都必須要掌握充足的局部拓撲信息，使得該節(jié)點可以計算出任意一條以自己為頂點的邊l＝(i， j)的干擾鏈路集I(l)。本文把每個節(jié)點必須掌握的這部分拓撲信息稱為調(diào)度局部拓撲。

定義鏈路l的相鄰鏈路集合NE(l)＝{k∈E:{b(k)，e(k)}∩{b(l)，e(l)｝≠}，那么在2跳鏈路約束條件下，鏈路l的干擾鏈路集合I(l)=NE(NE(l))={k∈E:NE(k)∩NE(l)≠}。

在無線網(wǎng)絡(luò)中，通過鏈路發(fā)現(xiàn)協(xié)議（如Hello協(xié)議等）節(jié)點i可以獲取1跳鄰居節(jié)點集V1(i)={j∈V:(i， j)∈E}，并且可以進一步直接計算得到節(jié)點i的1跳鄰居鏈路集E1(i)={(i， j)∈E:j∈V1(i)}。如果每個節(jié)點周期性地廣播1跳鄰居節(jié)點集合，那么節(jié)點i可以計算出2跳鄰居節(jié)點集合V2(i)=∪j∈V1(i)V1(j)。同理也可以計算得到2跳鄰居鏈路集合E2(i)＝∪j∈V1(i)E1(j)。從而每個節(jié)點i可以得到2跳生成子圖G2i(V2(i)，E2(i))。

定理1如果每個節(jié)點i都周期性地向直接鄰居廣播2跳生成子圖G2i(V2(i)，E2(i))，那么任意節(jié)點i通過收集鄰居節(jié)點通告，可以構(gòu)造其調(diào)度局部拓撲圖Gs_local(i)=∪j∈V1(i)G2j(V2(j)，E2(j))，即節(jié)點i可以計算出任意一條以i為頂點的邊l(i， j)的干擾鏈路集I(l)。

證明I(l)={k∈E:NE(l)∩NE(k)≠}=

(∪u∈V1(b(l))E1(u))∪(∪v∈V1(e(l))E1(v))=E2(b(l))∪E2(e(l))

E2(b(l))∪E2(e(l))∪j∈V1(i)∪k∈V1(j)E1(k)=∪j∈V1(i)E2(j)

所以I(l=(i， j))包含于Gs_local(i)的邊集。

上述定理的意義在于，通過局部信息擴散，任意一個節(jié)點都可以掌握每一條以該節(jié)點為頂點的無線鏈路的鏈路干擾集合；如果在拓撲建立過程，節(jié)點同時宣告與鏈路權(quán)重相關(guān)的參數(shù)集，那么節(jié)點可以進一步獲得每個鄰居鏈路干擾集合的權(quán)重。所以當(dāng)節(jié)點建立起調(diào)度局部拓撲圖，該節(jié)點就可以判斷任意一條鄰居鏈路是否是該鏈路所在干擾集合中的最大權(quán)重鏈路。

以圖2中節(jié)點i為例，計算鏈路(i， j)的鏈路干擾集合，其1跳鄰居節(jié)點集V1(i)={a，b， j，k}，節(jié)點i通過學(xué)習(xí)其鄰居節(jié)點的1跳鄰居節(jié)點通告可以計算出自己的2跳生成子圖G2i(V2(i)，E2(i))。其中V2(i)={a，b， j，k，d，c，f，h，m}，E2(i)={(i，a)，(i，b)，(i， j)，(i，k)，(a，d)，(a，b)，(b，c)，(b，f)，(j，h)，(j，k)，(k，m)}。通過學(xué)習(xí)鄰居節(jié)點的2跳生成子圖，節(jié)點i可以形成自己調(diào)度局部拓撲圖Gs_local(i)。而根據(jù)調(diào)度局部拓撲圖，節(jié)點i可以計算出(i， j)的干擾鏈路集合為I(i， j)={(i，a)，(i，b)，(i，k)，(j，k)(j，h)，(a，d)，(a，b)，(b，c)，(b，f)，(h，g)，(k，m)}。

32分布式貪婪極大調(diào)度算法

假設(shè)所有節(jié)點已掌握帶權(quán)重的調(diào)度局部拓撲圖，在每個時隙的開始時刻，節(jié)點狀態(tài)都設(shè)置為未確定狀態(tài)。

a)若節(jié)點i的狀態(tài)為未確定，那么從E1(i)中找出權(quán)重最大的一條邊l=(i， j)。其中 j=arg maxk∈V1(i)Qik(t)Cik。

b)判斷鏈路l=(i， j*)是否是在其鏈路干擾集合I(l)中是權(quán)重最大的邊。如果l是最大權(quán)重邊，那么l是調(diào)度鏈路，改變節(jié)點i的狀態(tài)設(shè)置為調(diào)度，并且向鄰居節(jié)點廣播鏈路調(diào)度通告，宣告鏈路l=(i， j*)已被調(diào)度；否則，節(jié)點i保持狀態(tài)為未確定。

c)若節(jié)點j收到鏈路調(diào)度通告，如果節(jié)點j狀態(tài)為未確定，并且節(jié)點j=j*，那么改變狀態(tài)為調(diào)度，同時向鄰居節(jié)點廣播鏈路調(diào)度通告，鏈路l=(i， j*)已被調(diào)度；如果節(jié)點j狀態(tài)為未確定，并且節(jié)點j ≠ j*，那么改變狀態(tài)為不調(diào)度，同時向鄰居節(jié)點廣播不調(diào)度節(jié)點通告，宣告自己狀態(tài)為不調(diào)度。否則，忽略之。

d)若節(jié)點i收到節(jié)點j的不調(diào)度通告，如果節(jié)點i狀態(tài)為未確定，那么將節(jié)點j以及以j為頂點的邊從節(jié)點i的調(diào)度局部拓撲圖Gs-local(i)中去掉，在包含有自己的子圖中重復(fù)執(zhí)行a)b)；否則，忽略之。

e)當(dāng)網(wǎng)絡(luò)中不存在未確定狀態(tài)的節(jié)點時，算法執(zhí)行完畢，所有狀態(tài)為調(diào)度的節(jié)點將被調(diào)度，執(zhí)行數(shù)據(jù)發(fā)送。

根據(jù)算法，節(jié)點的狀態(tài)被分為三類，即調(diào)度、不調(diào)度和未確定。每個時隙開始時刻，節(jié)點狀態(tài)都設(shè)置為未確定；每當(dāng)一條在局部（2跳鏈路范圍內(nèi)）具有最大權(quán)重鏈路被確定之后，對應(yīng)的發(fā)送、接收節(jié)點的狀態(tài)就被設(shè)置為調(diào)度，并通過廣播鏈路調(diào)度通告，將各自的1跳鄰居節(jié)點的狀態(tài)設(shè)置為不調(diào)度；這些不被調(diào)度的節(jié)點再通過廣播不調(diào)度通告，通知各自1跳鄰居節(jié)點，這些節(jié)點中狀態(tài)為未確定的節(jié)點會將所有與不調(diào)度節(jié)點相關(guān)的鏈路從自己的調(diào)度局部拓撲圖中刪除，并繼續(xù)執(zhí)行算法。

4算法性能分析

本章采用Laypunov穩(wěn)定性定理^[3，5]證明DGMS（分布式貪婪極大調(diào)度）算法在2跳無線鏈路干擾約束下，是一種次優(yōu)的吞吐率調(diào)度算法。為此，本章首先通過引理1證明在穩(wěn)定區(qū)域Λ內(nèi)的任意一組平均數(shù)據(jù)到達率λ，都存在一種理想化的隨機調(diào)度算法，使得網(wǎng)絡(luò)能夠穩(wěn)定工作，為后續(xù)證明提供一個參照算法；然后，定理2證明了在每個時隙里，通過DGMS算法計算的權(quán)重值是最大權(quán)重值的γ倍，其中γ是一個確定值，且0＜γ＜1；最后，定理3采用Laypunov穩(wěn)定性定理，并通過與隨機調(diào)度算法的比較，證明了當(dāng)數(shù)據(jù)到達率在某個確定范圍內(nèi)時，DGMS能夠保證網(wǎng)絡(luò)穩(wěn)定。

引理1對于任何λ∈Λ的數(shù)據(jù)到達率，一定存在隨機調(diào)度算法，使得E{rl(t)}=λl。

證明由Λ定義可知，如果λ∈Λ，那么存在μ∈Co(R)，滿足λ=μ。由于Co(R)是凸集，根據(jù)Caratheodory定理一定有

μ=P1r1+P2r2+…+PL+1rL+1

其中:ri(i=1，2，…，L+1)∈R，L+1i=1Pi=1。所以存在以下隨機調(diào)度算法：在每個時隙t，隨機地從{r1，r2，…，rL}中按照概率Pi選出ri進行鏈路調(diào)度，并且有E｛r(t)}=L+1i=1Piri=λ。

定理2證明了DGMS算法在每個時隙t中所選出的調(diào)度鏈路集合，其權(quán)重值總是滿足大于等于在t時隙網(wǎng)絡(luò)鏈路的最大權(quán)重值的γ(0＜γ＜1)倍。

定理2在2跳無線鏈路干擾約束下，DGMS算法滿足不等式l∈EQl(t)rl(t)≥γmaxr(t)∈R(t)l∈EQl(t)rl(t)，并且γ≥1/κmax。其中：κmax=maxl∈Eκ(l)，κ(l)表示在鏈路l的干擾集合I(l)中，能夠同時傳輸而互不干擾的鏈路數(shù)目的最大值。

證明設(shè)最優(yōu)調(diào)度鏈路集合為SO，分布式貪婪調(diào)度鏈路集合為SM。對于l(wèi)∈SO，lSM，那么一定存在一個邊集Es(l)SM，且Es(l)I(l)。在Es(l)中，一定存在一條邊l′，有Ql(t)rl(t)≤Ql′(t)rl′(t)。所以對于SO一定存在集合S′M={l′i∈SM，i=1，2，…，|SO|}SM，并且有|SO|i=1，li∈SOQli(t)rli(t)≤|SM|i=1，l′i∈SMQl′i(t)rl′i(t)。

在集合S′M中存在多組相同的邊。假設(shè)S′M總共有p組不同的邊S′Mp={l′i∈S′M，i=1，2，…，p}。假設(shè)S′M中任意一組相同邊是l′p1=l′p2=…=l′pn，共有n條，那么在SO中，一定對應(yīng)存在n條互不相同的邊{lp1，lp2，…，lpn∈SO}，并且{lp1，lp2，…，lpn｝∈I(l′p1)。

κmax=maxl∈Eκ(l)表示鏈路l的鏈路干擾集合中，可以互不干擾并行工作的最大鏈路數(shù)目。顯然有n≤κmax。因為

|SO|i=1，li∈SOQli(t)rli(t)≤

κmaxl∈S′MpQl(t)rl(t)≤κmax

|SM|i=1，li∈SMQli(t)rli(t)

所以l∈EQl(t)rl(t)≥γ maxr∈Rl∈EQl(t)rl(t)，且γ≥1/κmax

定理3在2跳無線鏈路干擾約束下，DGMS算法是一種次優(yōu)調(diào)度算法，即對于任何數(shù)據(jù)到達率向量λ，如果滿足λ+ε∈γΛ(其中L維向量ε=(ε，ε，…，ε)T，ε＞0），那么DGMS算法都能保證網(wǎng)絡(luò)是穩(wěn)定的，且limt→∞ sup 1/tt-1τ=0E{Ql(τ)}＜B/ε。其中B是一個常量。

證明在時隙t，任意鏈路l都有Ql(t+1)=max[Ql(t)-rl(t)，0]+Al(t)。易驗證有Q2l(t+1)-Q2l(t)

5數(shù)值仿真

本文采用了文獻[11]的實驗拓撲和相關(guān)網(wǎng)絡(luò)參數(shù)設(shè)置。如圖 3所示，網(wǎng)絡(luò)由16個節(jié)點、24條無線鏈路按照4行4列方式排列成柵格拓撲。圖中節(jié)點間的虛線表示存在一條無線鏈路，虛線上方的數(shù)值代表鏈路的容量(packet/slot)。為了簡化仿真，網(wǎng)絡(luò)中鏈路容量取值不盡相同。節(jié)點間的1跳數(shù)據(jù)流用箭頭表示，假定每條數(shù)據(jù)流的平均到達率均為λ(packet/slot)。每個源節(jié)點為每一條待發(fā)送的數(shù)據(jù)流分配一個獨立的緩存隊列，網(wǎng)絡(luò)按時隙工作，在每一個時隙開始時執(zhí)行調(diào)度算法、數(shù)據(jù)發(fā)送，在時隙結(jié)束時數(shù)據(jù)流到達。

圖4記錄了在2跳鏈路干擾約束下，網(wǎng)絡(luò)中所有鏈路的緩存長度總和隨著數(shù)據(jù)流到達率向量λ（網(wǎng)絡(luò)負載）增長的變化規(guī)律。仿真結(jié)果表明GMM和DGMS這兩種調(diào)度算法都具有以下特點：當(dāng)?shù)竭_率在某一個范圍內(nèi)遞增時，網(wǎng)絡(luò)緩存隊列長度隨著負載的增加而相對緩慢增加，網(wǎng)絡(luò)穩(wěn)定運行；而當(dāng)?shù)竭_率超過某個特定值以后，網(wǎng)絡(luò)緩存隊列長度將急劇增加，直至無窮，最終導(dǎo)致網(wǎng)絡(luò)不穩(wěn)定。仿真表明DGMS算法的穩(wěn)定區(qū)域略小于GMM算法的穩(wěn)定區(qū)域。

仿真數(shù)據(jù)圖 5和6記錄了在不同網(wǎng)絡(luò)負載下，DGMS和GMM調(diào)度算法瞬時隊列總長度的變化情況。仿真結(jié)果表明，當(dāng)數(shù)據(jù)流的平均到達率均在各自算法的穩(wěn)定區(qū)域時，DGMS算法的收斂時間與GMM算法比較接近。

6結(jié)束語

本文在2跳無線鏈路干擾約束下，提出了一種分布式的次優(yōu)吞吐率調(diào)度算法DGMS。DGMS算法充分利用節(jié)點通信時采用廣播方式這一重要特點，通過相鄰節(jié)點間局部鏈路信息擴散，從而使每個節(jié)點都能掌握自身所有鏈路的干擾集。節(jié)點使用局部信息分布式地執(zhí)行調(diào)度決策。本文利用Laypunov穩(wěn)定性定理證明了DGMS算法是一種次優(yōu)吞吐率調(diào)度算法，其穩(wěn)定區(qū)域至少是最大吞吐率調(diào)度算法穩(wěn)定區(qū)域的1/κmax倍，而在2跳無線鏈路干擾約束下，理論上可以證明κmax=8^[8]；同時還得到了網(wǎng)絡(luò)總體排隊長度的上界。

在無線Ad hoc網(wǎng)絡(luò)中，分布式的網(wǎng)絡(luò)控制機制是目前研究的熱點之一。而分布式控制所引入的開銷對網(wǎng)絡(luò)性能的影響需要進一步研究。所以，DGMS算法開銷的規(guī)模、算法開銷對網(wǎng)絡(luò)吞吐率的影響，以及減小開銷的協(xié)議優(yōu)化技術(shù)等問題是需要進一步深入研究的內(nèi)容。

參考文獻：

［1］

TASSIULASL，EPHREMIDES A.Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks[J].IEEE Trans on Automatic Control，1992，37(12):1936-1949.

[2]NEELY M，MODIANO E.Fairness and optimal stochastic control for heterogeneous networks[C]//Proc of IEEE INFOCOM.Piscataway:IEEE Press，2005:1723-1734.

[3]LIN X，SHROFF N B.Joint rate control and scheduling in multihop wireless networks[C]//Proc of IEEE Conf on Decision and Control.[S.l.]:IEEE，2004:1484-1489.

[4]LIN X，SHROFF N B.The impact of imperfect scheduling on cross-layer congestion control in wireless networks[J].IEEE/ACM Trans on Netw，2006，14(2):302-315.

[5]GEORGIADIS L，NEELY M J，TASSIULAS L.Resource allocation and cross-layer control in wireless networks[J].Foundations and Trends in Networking，2006，1(1):1-149.

[6]LEONARDI E，MELLIA M，NERI F，et al.On the stability of input-queued switches with speed-up[J].IEEE/ACM Trans on Networking，2001，9(1):104-118.

[7]SHARMA G，MAZUMDAR R R，SHROFF N B.Maximum weighted matching with interference constraints[C]//Proc of IEEE Int Workshop on Foundations and Algorithms for Wireless Networking.Washington DC:IEEE Computer Society，2006:70-74.

[8]CHAPORKAR P，KAR K，SARKAR S.Throughput guarantees in maximal scheduling in wireless networks[C]//Proc of the 43rd Annu Allerton Conf on Commun， Control， Comput.2005.

[9]CHEN L，LOW S H，CHIANG M，et al.Cross-layer congestion control， routing and scheduling design in Ad hoc wireless networks[C]//Proc of IEEE INFOCOM.[S.l.]:IEEE，2006:1-13.

[10]PAPADIMITIOU C H.組合最優(yōu)化算法和復(fù)雜性[M].劉振宏，譯.北京: 清華大學(xué)出版社，1988.

[11]LIN Xiao-jun，RASOOL S B.Constant-time distributed scheduling policies for Ad hoc wireless networks[C]//Proc of the 45th IEEE Conference on Decision and Control.[S.l.]:IEEE，2006:1258-1263.