文獻標識碼: A
文章編號: 0258-7998(2012)08-0109-03
移動Ad Hoc網絡由于抗毀性和分布式等特點,得到了越來越廣泛的應用,不斷有新的MAC協議被提出,以適應不同的應用環(huán)境。動態(tài)時隙混合類協議(HTDMA)[1]一般先通過碰撞回避[2]、虛擬載波監(jiān)聽[3]等方式探測網絡的局部拓撲信息,據此接入新節(jié)點,同時保留現有節(jié)點的傳輸安排,這種方式降低了大量的競爭開銷,更易為Ad Hoc網絡提供QoS保障。國內外已提出多種動態(tài)時隙混合類TDMA協議。在參考文獻[4]中提出一種集總式消除沖突的HTDMA協議——CCS-QR協議,它在一個控制時隙內將多個發(fā)射節(jié)點的接入請求集中處理,從而預約多個數據分組,之后再根據酬金類優(yōu)先級算法和接入順序分配數據時隙。它具有平均時延小、吞吐量穩(wěn)定等優(yōu)點,很適合為實時業(yè)務提供QoS保障,但卻不能完全支持分布式運行。這類問題還廣泛存在于非耦合式HTDMA協議中[5]。
1 分布式運行約束條件
在CCS-QR協議中,控制時隙只完成虛擬載波監(jiān)聽,并不為節(jié)點分配數據時隙,這種完全解耦的業(yè)務關系,減少了很多控制開銷。但其帶來另一個問題是,如果不提前發(fā)送時隙分配表,在數據時隙內由各節(jié)點根據優(yōu)先級確定發(fā)送次序,則節(jié)點之間就不能相互協調地發(fā)送數據分組,就會引發(fā)沖突。
CCS-QR協議的數據時隙如圖1所示,結合圖2,例如在第1個數據時隙內,兩跳范圍內業(yè)務①②③會同時發(fā)送,而相互沖突導致失敗。原因是分布式網絡結構下,節(jié)點覆蓋范圍有限,無法得到所有節(jié)點的業(yè)務信息,所以每個節(jié)點所維持的預約序列都不相同[6]。
式(4)中的第一個約束條件表示一個時幀內節(jié)點至少分配一個時隙,第二個約束條件表示相距一跳的節(jié)點不能分配同一時隙,第三個約束條件表示兩個節(jié)點與同一節(jié)點相距一跳時不能分配同一時隙。以上說明,如果要滿足目標函數,無沖突發(fā)送數據,則必須保證相距兩跳范圍內的節(jié)點分配不同的時隙。
2 分布式隊列運行機制與分析
本文針對解耦關系的HTDMA,提出一種自協調分布式運行解決方案。下面對圖2所示的網絡模型和CCS-QR協議[4]進行分析和說明。
在圖2中,網絡由14個節(jié)點組成,實線表示兩個節(jié)點在對方覆蓋范圍內,箭頭表示兩個節(jié)點已在信令時隙完成數據時隙的預約,序號表示節(jié)點發(fā)送RTS/CTS分組的順序,為了簡化模型,省略了CCS-QR協議里優(yōu)先級的表達。
2.1業(yè)務管理樹算法原理
定義1:各個發(fā)射節(jié)點將所有兩跳范圍內的發(fā)送業(yè)務排成預約隊列,稱為不完全隊列,用Ci={ci-a,ci-b…ci}表示,Li為不完全隊列的長度。
定義2:根據協議安排,把控制時隙里允許接入的最大業(yè)務量按照優(yōu)先級或接入次序進行排隊,稱之為完全隊列,用Call={c1,c2…cn}表示,Lall為完全隊列的長度。
定義3:設Ci為節(jié)點i的不完全隊列,Ni為節(jié)點i在Ci中的序號,每當Ci中的一個節(jié)點發(fā)送了相應的數據業(yè)務,有Li=Li-1,則稱使Li=Ni-1的節(jié)點為節(jié)點i的業(yè)務觸發(fā)節(jié)點,其相應的數據業(yè)務稱為觸發(fā)業(yè)務,將此時節(jié)點i的業(yè)務稱為待發(fā)業(yè)務。
定義4:將所有發(fā)送業(yè)務按照預約順序的方向排成隊列,該隊列會從觸發(fā)業(yè)務和待發(fā)業(yè)務處產生樹形結構,稱它為業(yè)務管理樹,其模型如圖3。業(yè)務管理樹的長度Lall等于所有業(yè)務發(fā)送完畢所需時隙的個數。
當某個業(yè)務同時作為兩個預約隊列中不同節(jié)點的觸發(fā)業(yè)務時,業(yè)務樹將產生分支結構,分支點位于當前業(yè)務之后,即某兩個待發(fā)業(yè)務之前;當不同分支的兩個節(jié)點同時作為某個業(yè)務的觸發(fā)業(yè)務時,業(yè)務樹將產生匯聚結構,匯聚點位于當前業(yè)務之前。
業(yè)務樹出現分支意味著將有多個子序列同時發(fā)送數據,而業(yè)務樹的匯聚表示在某個節(jié)點接入信道前,其預約隊列中同時有多個節(jié)點發(fā)送了數據。
前面已經通過數學模型論證,協議只需要將發(fā)射節(jié)點兩跳范圍之內的業(yè)務進行協調就可以防止此類沖突的發(fā)生。而兩跳之內的節(jié)點必處于同一業(yè)務樹分支當中,業(yè)務樹中不同分支上的節(jié)點至少相距兩跳以上,不在同一分支的節(jié)點可以同時隙發(fā)送業(yè)務,發(fā)送次序為Li。
2.2 算法描述
一個業(yè)務管理樹運行過程面向業(yè)務序列,而不是節(jié)點。具體工作過程為:
(1)收集發(fā)射狀態(tài)(Collection Phase):在控制時隙,通過對所有RTS分組和對應CTS分組的監(jiān)聽,接收節(jié)點將所有相鄰發(fā)射節(jié)點納入自身隊列,發(fā)射節(jié)點也將相應接收節(jié)點的所有相鄰發(fā)射節(jié)點納入自身隊列。大多數HTDMA協議都能滿足此條件。
(2)接入順序表達(Sequence Phase):此階段,依據協議里優(yōu)先級設置和節(jié)點的接入次序為每項業(yè)務分配權重,即發(fā)送次序,并由此產生一個相同的完全隊列,包含所有業(yè)務信息。
(3)隊列形成(Establishing Phase):在此階段,節(jié)點依據已得到兩跳范圍內其他節(jié)點的發(fā)射狀態(tài)來形成不完全預約隊列,這個隊列只關心發(fā)送次序在自己之前的業(yè)務。
(4)確認發(fā)送次序(Approval Phase):根據業(yè)務管理樹算法,得到不完全隊列的補集,并將自身不完全隊列接入自己的觸發(fā)節(jié)點,業(yè)務將在不同分支間并行傳輸,而業(yè)務在不完全隊列中的次序即為發(fā)送次序。
2.3 算例分析
經過隊列調整后,各節(jié)點的預約隊列分別如表1所示。在此為了便于說明,隊列中業(yè)務序列按其序號排列。
3.1 吞吐量分析
圖6顯示了不同網絡負載下三種協議的吞吐量變化曲線。從圖中可以看出,CSMA/CA協議網絡吞吐量較低,這是由于競爭接入產生沖突所導致;而CCT—QR協議基于預留方式分配資源,產生的沖突很小,且控制開銷不大,所以網絡吞吐量較高;DCT—QR協議由于消除了CCT—QR協議數據時隙內的沖突,所以吞吐量更高且更穩(wěn)定。但由于接入容量有限,所以在網絡載荷增多的情況下,吞吐量會出現飽和。
本文提出了解決Ad Hoc網絡非耦合HTDMA協議分布式運行沖突的自協調式的業(yè)務管理樹算法,通過舉例分析和仿真實驗可以看出,該算法能夠達到預期效果。但這種算法在復雜網絡環(huán)境下,會增加分組時延,這將是下一步研究工作的重點。
參考文獻
[1] Li Wei, Wei Jibo, Wang Shan. An evolutionai-dynamic TDMA slot assignment protocol for Ad Hoc networks[C]. IEEE Communications Society subject matter experts for publication in the WCNC 2007 proceedings,2007:138-142.
[2] 嚴少虎,卓永寧,吳詩其,等. IEEE 802. 11 DCF 中帶優(yōu)先級的退避算法[J].電子與信息學報,2005,27(8):1315-1319.
[3] KAYNIA M, JINDAL N. Improving the performance of wireless Ad Hoc networks through MAC layer design[C]. IEEE transactions on wireless communication:January 2011.
[4] 楊海東,李建海,鄧勇.采用集總式沖突消除算法的Ad Hoc網絡MAC協議[J]. 系統(tǒng)工程與電子技術, 2009,31(5):1241-1245.
[5] 葉林容,余敬東.基于TDMA的Ad Hoc網絡MAC協議研究[D]. 成都:電子科技大學,2011.
[6] FULLERTON P S. Dynamic control slot scheduling algorithm for TDMA based mobile Ad Hoc networks[C]. Military Communications Conference, 2008:1-7.