無線Ａｄ ｈｏｃ網絡中分布式極大吞吐率調度算法研究

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



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

關鍵詞：分布式極大調度；2跳鏈路干擾約束；穩定區域；局部拓撲

中圖分類號：TP393文獻標志碼：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網絡中，由于任意一條無線傳輸鏈路都可能和地理位置與其相鄰的其他無線鏈路相互干擾，從而使得無線鏈路間形成了某種約束關系，也即是在每一個時刻，網絡中只能有部分鏈路同時傳輸，而干擾這些鏈路的其他鏈路均不能被使用。所以，無線Ad hoc網絡鏈路調度是研究在某種特定無線鏈路干擾約束條件下，網絡中哪些鏈路能夠互不干擾地并行工作，進而達到某種網絡性能的優化。

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

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

1網絡模型

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

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

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

0鏈路l未被調度

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

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

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

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

如果一個排隊網絡內所有排隊隊列長度始終都能保持有限的，那么就稱該網絡是穩定的。

2鏈路調度算法及其穩定區域

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

文獻[1]將在調度算法下，所有能夠通過網絡穩定傳輸的平均分組到達率向量的集合Λ={λ}定義為調度算法的穩定區域或者容量區域(capacity region)。而對于某一給定網絡，將所有調度算法穩定區域的并集稱之為該網絡的最大穩定區域Λ，或者稱為最優容量區域(optimal capacity region)。那么，如果某種調度算法opt，其容量區域能夠達到Λ，就稱該調度策略為最大吞吐率調度或最優調度。

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

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

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

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

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

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

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

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

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

22無線鏈路次優吞吐率調度算法

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

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

3分布式貪婪極大調度算法設計

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

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

31構造調度局部拓撲圖

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

定義鏈路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)≠}。

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

定理1如果每個節點i都周期性地向直接鄰居廣播2跳生成子圖G2i(V2(i)，E2(i))，那么任意節點i通過收集鄰居節點通告，可以構造其調度局部拓撲圖Gs_local(i)=∪j∈V1(i)G2j(V2(j)，E2(j))，即節點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)的邊集。

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

以圖2中節點i為例，計算鏈路(i， j)的鏈路干擾集合，其1跳鄰居節點集V1(i)={a，b， j，k}，節點i通過學習其鄰居節點的1跳鄰居節點通告可以計算出自己的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)}。通過學習鄰居節點的2跳生成子圖，節點i可以形成自己調度局部拓撲圖Gs_local(i)。而根據調度局部拓撲圖，節點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分布式貪婪極大調度算法

假設所有節點已掌握帶權重的調度局部拓撲圖，在每個時隙的開始時刻，節點狀態都設置為未確定狀態。

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

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

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

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

e)當網絡中不存在未確定狀態的節點時，算法執行完畢，所有狀態為調度的節點將被調度，執行數據發送。

根據算法，節點的狀態被分為三類，即調度、不調度和未確定。每個時隙開始時刻，節點狀態都設置為未確定；每當一條在局部（2跳鏈路范圍內）具有最大權重鏈路被確定之后，對應的發送、接收節點的狀態就被設置為調度，并通過廣播鏈路調度通告，將各自的1跳鄰居節點的狀態設置為不調度；這些不被調度的節點再通過廣播不調度通告，通知各自1跳鄰居節點，這些節點中狀態為未確定的節點會將所有與不調度節點相關的鏈路從自己的調度局部拓撲圖中刪除，并繼續執行算法。

4算法性能分析

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

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

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

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

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

定理2證明了DGMS算法在每個時隙t中所選出的調度鏈路集合，其權重值總是滿足大于等于在t時隙網絡鏈路的最大權重值的γ(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)中，能夠同時傳輸而互不干擾的鏈路數目的最大值。

證明設最優調度鏈路集合為SO，分布式貪婪調度鏈路集合為SM。對于l∈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中存在多組相同的邊。假設S′M總共有p組不同的邊S′Mp={l′i∈S′M，i=1，2，…，p}。假設S′M中任意一組相同邊是l′p1=l′p2=…=l′pn，共有n條，那么在SO中，一定對應存在n條互不相同的邊{lp1，lp2，…，lpn∈SO}，并且{lp1，lp2，…，lpn｝∈I(l′p1)。

κmax=maxl∈Eκ(l)表示鏈路l的鏈路干擾集合中，可以互不干擾并行工作的最大鏈路數目。顯然有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算法是一種次優調度算法，即對于任何數據到達率向量λ，如果滿足λ+ε∈γΛ(其中L維向量ε=(ε，ε，…，ε)T，ε＞0），那么DGMS算法都能保證網絡是穩定的，且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數值仿真

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

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

仿真數據圖 5和6記錄了在不同網絡負載下，DGMS和GMM調度算法瞬時隊列總長度的變化情況。仿真結果表明，當數據流的平均到達率均在各自算法的穩定區域時，DGMS算法的收斂時間與GMM算法比較接近。

6結束語

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

在無線Ad hoc網絡中，分布式的網絡控制機制是目前研究的熱點之一。而分布式控制所引入的開銷對網絡性能的影響需要進一步研究。所以，DGMS算法開銷的規模、算法開銷對網絡吞吐率的影響，以及減小開銷的協議優化技術等問題是需要進一步深入研究的內容。

參考文獻：

［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.組合最優化算法和復雜性[M].劉振宏，譯.北京: 清華大學出版社，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.