多跳無(wú)線(xiàn)網(wǎng)中基于空分TDMA的時(shí)隙分配策略

2010年第03期,第43卷通信技術(shù)Vol.43,No.03,2010總第219期Communicat ions TechnologyNo. 219, Totally多跳無(wú)線(xiàn)網(wǎng)中基于空分TDMA的時(shí)隙分配策略韓成,吳援明(電子科技大學(xué)光電信息學(xué)院,四川成都610054)【摘要】空分TDMA( STDMA)是基于TDMA的信道接入協(xié)議,該技術(shù)被應用于實(shí)時(shí)性要求較高的多跳( multi-hop)無(wú)線(xiàn)網(wǎng)絡(luò )中,并可使多個(gè)在地理位置相互獨立的移動(dòng)終端使用相同的時(shí)隙來(lái)増加網(wǎng)絡(luò )容量,不冋移動(dòng)終端之間的教據傳輸通過(guò)對終端調度安排來(lái)實(shí)現。調度算法一般分為基于節點(diǎn)或基于鏈路的分配方式。對這兩種方式對比發(fā)現,在一定條件下兩者都有不理想的特性。因此,結合兩種方式優(yōu)點(diǎn)提出了一種新穎的分配策略。仿真結果表眀:該分配策略在高業(yè)務(wù)負載情況下能滿(mǎn)足鏈路分配的高吞吐量,也能達到低業(yè)務(wù)負載下節點(diǎn)分配的低延遲【關(guān)鍵詞】 STDMA;多跳無(wú)線(xiàn)網(wǎng);媒體介入控制;調度【中圖分類(lèi)號】TP393【文獻標識碼】A【文章編號】1002-0802(2010)03-0090-03Slot Assignment Strategies of Spatial Reuse TDMAin Multi-hop Wireless Networkshan Cheng, WU Yuan-ming(College of Optic-electronic Information, UESTC, Chengdu Sichuan 610054, China)(Abstract] In the multi-hop radio networks, spatial reuse TDMa is proposed as an access scheme. The ideais to increase capacity by letting several radio terminals use the same time slot when possible. A time slot couldbe shared when the radio units are geographically separated such that small interference is produced. In reusescheduling, there are several alternative assignment methods. Traditionally, transmission rights are given tenodes or to links. A comparison of these two approaches is given, and it shows that both have undesirable propertiesin certain cases, Furthermore, a novel assignment strategy is proposed, which integrates the advantages of bothmethods. Simulation results indicate that the proposed method could achieve the throughput of link assignmentfor high traffic loads as well as the lower delay characteristics of node assignment for low traffic loads.(Key words] Ad Hoc networks: smart antenna: STDMA: link scheduling引言?xún)煞N基本 STDMA調度策略之一是將傳輸權直接賦予節在多跳無(wú)線(xiàn)網(wǎng)中一個(gè)具有挑戰性的問(wèn)題是如何保證延點(diǎn)。另一種將傳輸權賦予鏈路。節點(diǎn)分配算法和鏈路分配算遲。相關(guān)文獻研究表明使用CSMA的接入方式,在需提供具有法在文獻[2]中有過(guò)深入的探討。研究表明不論是節點(diǎn)分配延遲保證的應用環(huán)境表現很差。解決這類(lèi)問(wèn)題可以引入時(shí)還是鏈路分配在尋找最小長(cháng)度調度是都歸結為全NP問(wèn)題分多址接入TDM。但在 Ad hoc網(wǎng)絡(luò )中鏈路相對較少時(shí)使用在本文中,我們提出了一個(gè)結合兩者優(yōu)點(diǎn)的分配策略。該策效率不高。一個(gè)對TDM機制的有效改進(jìn)方法是空分TDM,它略基于鏈路調度,但是傳輸權被擴展。該方式提高了鏈路分將無(wú)線(xiàn)結點(diǎn)之間的物理距離考慮在內,規定互相不干擾的通訊鏈路可以在相同的時(shí)間片內傳輸,從而減少了網(wǎng)絡(luò )所需時(shí)配的空間利用程度。為了對比該策略是否優(yōu)于單純的節點(diǎn)或間片的總量,從而提高了整個(gè)網(wǎng)絡(luò )的吞吐量。其容量的提高鏈路分配,我們使用在TDMA調度中經(jīng)常使用的網(wǎng)絡(luò )干擾模通過(guò)時(shí)隙的空間復用來(lái)實(shí)現,而延遲保證有TDM來(lái)提供型。我們將分別采用分析法和仿真來(lái)估計該策略在不同網(wǎng)絡(luò )通性下的端到端時(shí)延和吞吐量收稿日期:2008-12-31作者簡(jiǎn)介:韓成(1984-),男,碩士研究生,主要研究方向為無(wú)線(xiàn)移動(dòng)網(wǎng)絡(luò )MAC技術(shù)、組網(wǎng)技術(shù):吳援明(1966-),男,教1網(wǎng)絡(luò )模型碩士生導師,主要研究方向為現代通信中的信號處理。假設使用全向天線(xiàn)并且所有節點(diǎn)具有相同的傳輸功率。對于任意兩個(gè)節點(diǎn)(,),其中v表示發(fā)送節點(diǎn),ν表示接包的傳輸方向,除了分配的接收節點(diǎn)外,新的接收節點(diǎn)對于收節點(diǎn),且v≠v,節點(diǎn)v和節點(diǎn)v之間的鏈路可以成功傳不等式(4)n(,0≥y,,V()∈L仍能得到滿(mǎn)足,這就意輸分組的條件是節點(diǎn)間的信噪比(SNR)超過(guò)一個(gè)門(mén)限,即味著(zhù)對于其他接收節點(diǎn)的干擾級別并沒(méi)有改變。r=PG(,2基于上述理由改進(jìn)的面向鏈路分配策略可以描述為,對于已分配時(shí)隙的鏈路,首先檢查該條鏈路上是否有分組需要其中,P表示發(fā)送節點(diǎn)v的傳輸功率。G(,)表示節點(diǎn)v2、傳輸,如果沒(méi)有便將該時(shí)隙分配給具有相同發(fā)送節點(diǎn)的其他,之間的鏈路增益。N表示在接收節點(diǎn)所有的噪聲功率。鏈路(該鏈路上存在數據包傳送)。當然為了避免不必要的分如果SNR不小于通信門(mén)限y’我們說(shuō)一對節點(diǎn)C,v)形成組丟失,無(wú)沖突鏈路可以按照優(yōu)先級來(lái)選擇。我們定義該策條鏈路()。n表示網(wǎng)絡(luò )中形成的鏈路集合,定義為略為基于擴展傳輸權限的鏈路分配策略 LET (Linkn={(0:≥7}。任意的鏈路集合的子集L≤n,定義t with Extended Transmission Rights)發(fā)送節點(diǎn)(L)=:(,)∈L}。下面我們證明重新分配傳輸權的鏈路不會(huì )對本時(shí)隙中干擾包括背景噪聲和所有并發(fā)鏈路的同頻干擾。對于任其他鏈路引入附加的競爭。設按照公式(4)能同時(shí)傳輸的鏈意鏈路(j)∈L,定義干擾如下路集合為L(cháng),則∏(j≥γ,(,j∈L。打算撤銷(xiāo)傳輸權l()=∑PG(k,),的鏈路集合為L(cháng)a(La∈L),該時(shí)隙余下的鏈路集合設為L(cháng),滿(mǎn)足關(guān)系L=L\L。重新分配傳輸權的鏈路集合為因此,信干噪比∏4(,八可由以下式子求得L,可推得V(L)=V(La)。由于L為無(wú)沖突鏈路集合,n0)=-.PG(k(3)因此需要證明下式無(wú)等式成立(N+l1(i,∏L,(,)≥y,v(,))∈LNR我們假設當任意節點(diǎn)間的SIR大于最小通信門(mén)限y時(shí),任意根據式(4)信干噪比SNR定義可知:兩個(gè)通信節點(diǎn)間都能無(wú)錯誤的傳輸分組并在一個(gè)時(shí)隙內不(i,))∈Lw能同時(shí)發(fā)送和接收。調度策略S定義為一個(gè)集合x(chóng)PG(i,Dt=1,2…,T,其中T表示調度周期。集合X,中包含已分配了14(,)=(N+(n)時(shí)隙t的節點(diǎn)或者鏈路。如果該集合內所有節點(diǎn)的SIR都小于門(mén)限γ,我們稱(chēng)該調度為無(wú)干擾調度又因為,V(La∪L)=V(L2)V7(L)=V(L∪L)=2分配策略描述V(L,所以干擾l(,=L(),信干噪比∏n(n2.1鏈路分配策略∏4(,j),則式(6)成立。證明了LET分配策略不會(huì )在任何節如果{⌒伙,}≠φ,鏈路(k,D)稱(chēng)為鏈路(,的鄰近點(diǎn)之間引入附加的競爭。鏈路。時(shí)隙t對應分配的鏈路集合為L(cháng),由此我們定義平(L)為集合L中各鏈路對應的鄰近鏈路旁集合。當滿(mǎn)足如下兩個(gè)3分配策略性能分析條件:本節我們將給出LET性能的一些分析結果。首先討論吞L∩(L)=;∏(i,j)≥y,,V(i,j∈L,(4)吐量其次計算在低業(yè)務(wù)到達率前提下的分組延時(shí)。時(shí)隙t分配的鏈路集合L中各鏈路能同時(shí)傳輸。3.1分配策略對網(wǎng)絡(luò )吞吐率的影響2.2節點(diǎn)分配策略文獻[4]中討論了在固定鏈路容量和固定路由下的網(wǎng)絡(luò )在面向節點(diǎn)的分配策略中,我們定義時(shí)隙4對應分配的吞吐量。文獻5]中提出了鏈路調度策略的網(wǎng)絡(luò )最大吞吐量節點(diǎn)集合為V,定義集合V中某一節點(diǎn)v(v∈V)的鄰節點(diǎn)A2。重寫(xiě)如下為Φ(),這里的鄰居節點(diǎn)表示能同時(shí)接收到節點(diǎn)ν傳輸的分N(N-I)h組。設集合所有節點(diǎn)的鄰節點(diǎn)為Φ(V),L()表示Φ(V)TA相關(guān)的鏈路集合,為了滿(mǎn)足集合V中的節點(diǎn)以及L()中鏈其中T是鏈路調度的長(cháng)度。N表示節點(diǎn)的數目,N=。b路能同時(shí)傳輸分組,同樣也需要滿(mǎn)足如下兩個(gè)約束表示在一個(gè)調度幀長(cháng)內,分配給鏈路(,0的時(shí)隙數量。A表Ln9)=;nlmn(,)≥y,v(i,∈L(),(5)示路由表中包含(i,)鏈路的路徑式(5)表示的物理意義為同時(shí)傳輸的節點(diǎn)不應有相同的鄰節的網(wǎng)絡(luò )最大吞吐量列如下所布量。對應地,按節點(diǎn)分配點(diǎn)以及同時(shí)傳輸節點(diǎn)的鏈路相互不應有干擾=N(N-)2.3改進(jìn)的面向鏈路分配策略T-A我們注意到式(3)發(fā)生沖突檢測的條件依賴(lài)于數據包發(fā)其中7是節點(diǎn)調度的長(cháng)度,b表示在一個(gè)調度幀長(cháng)內,分送節點(diǎn),而不在于接收節點(diǎn)上。假定某一節點(diǎn)在該時(shí)隙中分配給節點(diǎn)()的時(shí)隙數量。4表示路由表中包含節點(diǎn)()的路配為發(fā)送節點(diǎn),這樣就存在一條傳輸鏈路,如果要更改數據徑數量從以上兩式可以看出,如果所有節點(diǎn)或鏈路都處于飽和絡(luò )連通性有不同的吞吐量比,隨著(zhù)連通性的下降鏈路分配能狀態(tài),那么平均分組時(shí)延將會(huì )無(wú)限長(cháng)。這時(shí)節點(diǎn)吞吐量實(shí)現更高的吞吐量。在20節點(diǎn)低業(yè)務(wù)負載條件下,我們探A/NN-1)就與T/h相等。而且在鏈路調度中對業(yè)務(wù)進(jìn)討鏈路分配平均時(shí)延D2與節點(diǎn)分配平均時(shí)延D間的比值行完全補償(=4)后,上述網(wǎng)絡(luò )吞吐量的計算可以分別簡(jiǎn)關(guān)系。從圖2可以看出比值基本與連通率呈線(xiàn)性關(guān)系。從數化為值上看,鏈路分配時(shí)延遠遠大于節點(diǎn)分配時(shí)延。并隨連通率的增大而增大下面我們來(lái)探討節點(diǎn)分配與LET的關(guān)系,如圖3為20這樣上式就建立起兩種分配方案與吞吐量之間的關(guān)系個(gè)節點(diǎn)、低延遲負載條件下,D/Dx的比值大小。(10)所以?xún)煞N分配方案下的吞吐量與 STDMA幀長(cháng)度相關(guān)。3.2分配策略對網(wǎng)絡(luò )延時(shí)的影響轉發(fā)業(yè)務(wù)可以使用泊松分布過(guò)程來(lái)描述。根據網(wǎng)絡(luò )延時(shí)的定義,在面向鏈路的分配策略中對于廣播業(yè)務(wù)系統網(wǎng)絡(luò )延時(shí)為d=7/2h其中d為鏈路(i,)的平均 edge delayo如果對業(yè)務(wù)進(jìn)行完全補償(=A)后:M7D=2N(N-1)圖1吞吐量之比與連通率的關(guān)系這里M為網(wǎng)絡(luò )中所有鏈路的總數同理,對于面向節點(diǎn)的分配策略中網(wǎng)絡(luò )延時(shí)完全補償后為D故兩種分配策略的延M T MAD、NTNA以上兩點(diǎn)假設對LET策略同樣適用,但由于LET在低業(yè)務(wù)負載情況下表現為節點(diǎn)分配調度。因此鏈路分配策略必須擴展到節點(diǎn),并按照調度中的安排進(jìn)行廣播或單播。因此LET策略的延時(shí)可以定義為D=∑A。進(jìn)行業(yè)務(wù)完全補N(N-1)2h圖2兩種分配策略延時(shí)比值關(guān)系NTL償后D1=2N(N-1)因此鏈路分配、節點(diǎn)分配分別與LET之間的時(shí)延關(guān)系如下N DLET可見(jiàn),分配策略時(shí)延關(guān)系與網(wǎng)絡(luò )大小、連通度以及調度周期有關(guān)。仿真本節我們評價(jià)在不同連接性和節點(diǎn)數下,網(wǎng)絡(luò )的吞吐量圖3不同節點(diǎn)數目下吞吐量與連通性的關(guān)系和時(shí)延。為了便于比較分別生成了500個(gè)節點(diǎn)數量為10、20如果參數值大于1則說(shuō)明LET策略在低負載條件下時(shí)比值和40的網(wǎng)絡(luò )拓撲。每個(gè)節點(diǎn)平均產(chǎn)生參數為λ的泊松過(guò)程數與連通率的關(guān)系,可以看出在不同網(wǎng)絡(luò )拓撲下該值變化較大據流。由于傳輸功率P不同,將導致拓撲結構連通性的變化。圖4為在10/20/40節點(diǎn)條件下平均D、D比值關(guān)系這里定義連通性為單跳內平均每節點(diǎn)的鏈路數,即D、Da隨著(zhù)連通率的提高而降低,這是由于連通率的提高導M/(N(N-1)。M表示網(wǎng)絡(luò )中所有鏈路的數量致鏈路分配空分復用能力的降低。并且在中低連了在20節點(diǎn)高業(yè)務(wù)負載條件下,鏈路分配最大吞吐量和D、/D4x<1的情況。而網(wǎng)絡(luò )中節點(diǎn)數越多D、Dx比值越大,節點(diǎn)分配最大吞吐量的比值λ2入,根據式(10)應等于即LET延遲越小,這是因為網(wǎng)絡(luò )越大每個(gè)節點(diǎn)可供傳輸的周?chē)鶷/T。仿真結果如圖1所示。從圖中可以看出,鏈路分配節點(diǎn)越多,則LT策略可選的鏈路也就越多,以致時(shí)延減少。策略性能比節點(diǎn)分配策略提供更大的吞吐量,而且不同的網(wǎng)(下轉第95頁(yè)范圍在-4~4dBm之間,Δα的取值范圍在-0.5~0.5之間多邊定位法具有更好的魯棒性,而在噪聲較小,差圓法的性設信號衰減模型的參數為P=-30dBm和α=3。上述算法能優(yōu)勢比較明顯中的閾值0=0.5dBm。使用4個(gè)錨節點(diǎn),排列方式如圖3所示,未知節點(diǎn)位置在圖3所示區域內任意分布3結語(yǔ)▲錨節點(diǎn)本文在實(shí)測RSSI數據的基礎上指出了信號衰減模型時(shí)變性的特點(diǎn),事實(shí)上,無(wú)法建立足夠精確的無(wú)線(xiàn)信號強度衰減模型正是影響基于RSSI的定位算法精度提高的主要原因之一。針對這一問(wèn)題,本文提出了一種新的定位法—差圓法。該算法是針對目前使用RSSI測距的定位方法對模型參數依賴(lài)較大的問(wèn)題進(jìn)行的一些改進(jìn)。差圓法實(shí)際上通過(guò)弱化衰減模型在定位算法中的作用從而在一定程度上提高了定位的精度。通過(guò)仿真也進(jìn)一步證明在噪聲較小時(shí),差圓法具有較好的定位性能。但是該方法的抗噪聲性能不佳,在噪聲較大時(shí)性能惡化比較嚴重,這是需要改進(jìn)的方向之一,例如圖3錨節點(diǎn)分布及定位區域示意圖引入加權思想等。盡管差圓法具有一定局限性,但在針對為了不失一般性,在圖3所示待定位區域內,隨機的產(chǎn)型的處理上提出了新思路,具有一定研究?jì)r(jià)值。生10000個(gè)目標節點(diǎn),將定位結果的誤差進(jìn)行平均。式(12)中高斯隨機變量X均值為零,在不同的標準差下,兩種算參考文獻法的定位誤差如圖4所示[1]于宏毅,李鷗,張效義,無(wú)線(xiàn)傳感器網(wǎng)絡(luò )理論技術(shù)與實(shí)現[M].北京:國防工業(yè)出版社,2008[2]王福豹,史龍,任豐原.無(wú)線(xiàn)傳感器網(wǎng)絡(luò )中的自身定位系統和算法[J]軟件學(xué)報,2005,16(5):857-868[3]王建剛,王福豹,段渭軍.加權最小二乘估計在無(wú)線(xiàn)傳感器網(wǎng)絡(luò )定位中的應用[J].計算機應用研究,2006,23(09):41-43.[4] Mac Duffee CC. The Theory of Matrices [M. USA: Dover Publications2004:51-89[5]Theodore S R, Wirless Communications: Principles and Practice2nd Edition)[M]. USA: Prentice Hall Press, 2001: 69-138[6] Paramvir B, Venkata N, Padmanabhan. RADAR: An In-building噪聲標準差RF-based User Location and Tracking System[C]. Israel: IEEE圖4多邊定位法和差園法平均定位誤差Computer and Communications Societies, 2000: 775-584仿真結果如圖4所示,在噪聲較小時(shí),差圓法具有較好7] Savarese C, Raba j, Langendoen K. Robust positioner的性能,當噪聲增大時(shí),性能開(kāi)始惡化,這主要是由于所構Algorithms for Distributed Ad hoc Wireless Sensor Networks造的圓曲線(xiàn)方程不能夠相交造成的,具體的數學(xué)原理在此限[C]//Carla Schlatter Ellis. Proceedings of The USENIX于篇幅在此不再討論,應當指出的是,同樣的原因也造成了Technical Annual Conference. Monterey: USENIX Press, 2002多邊定位法的性能惡化,不過(guò)相比較而言,在噪聲較大時(shí),17-327.(上接第92頁(yè))Radio Networks [J]. IEEE/ACM Trans. Networking, 1993, 1(02)5結語(yǔ)166-177從以上三種分配策略分析表明,策略的選擇與網(wǎng)絡(luò )連通率[2] Nelson R, Kleinrock L, Spatial-TDMA: A Collision-free Multihe業(yè)務(wù)負載和網(wǎng)絡(luò )大小有關(guān)。在高業(yè)務(wù)負載下,由于鏈路分配有Channel Access Protocol[]. IEEE Trans, Commun., 1985, 33(09)更高的空間復用能力比節點(diǎn)分配具有更好的吞吐量。相反地,34-944在低業(yè)務(wù)負載下節點(diǎn)分配能提供節點(diǎn)間更短的傳輸時(shí)間。從仿[3 Arikan E. Some Complexbout Packet Radio真結果可以看出,LET策略在保持高吞吐量的前提下,時(shí)延比鏈路分配低很多。而且在中低連通率條件下也比節點(diǎn)分配低Networks[J. IFFE Trans. Inform.1984(IT-30):910918這說(shuō)明LET策略很好地結合的兩者的優(yōu)點(diǎn),使性能達到最佳。[4]AspB, Eriksson G, Holm f. Detvag90R= Final ReportScientific Report FOA-R-97-00566-504- SE, Defence Research參考文獻of Command and Control Warfare Tech. [R]. Sweden[1] Ramanathan S, Lloyd E. Scheduling Algorithms for Multihop[s.n.],1997