2010年第03期,第43卷通信技術(shù)Vol.43,No.03,2010總第219期Communicat ions TechnologyNo. 219, Totally多跳無線網(wǎng)中基于空分TDMA的時隙分配策略韓成,吳援明(電子科技大學光電信息學院,四川成都610054)【摘要】空分TDMA( STDMA)是基于TDMA的信道接入?yún)f(xié)議,該技術(shù)被應用于實時性要求較高的多跳( multi-hop)無線網(wǎng)絡(luò)中,并可使多個在地理位置相互獨立的移動終端使用相同的時隙來増加網(wǎng)絡(luò)容量,不冋移動終端之間的教據(jù)傳輸通過對終端調(diào)度安排來實現(xiàn)。調(diào)度算法一般分為基于節(jié)點或基于鏈路的分配方式。對這兩種方式對比發(fā)現(xiàn),在一定條件下兩者都有不理想的特性。因此,結(jié)合兩種方式優(yōu)點提出了一種新穎的分配策略。仿真結(jié)果表眀:該分配策略在高業(yè)務(wù)負載情況下能滿足鏈路分配的高吞吐量,也能達到低業(yè)務(wù)負載下節(jié)點分配的低延遲【關(guān)鍵詞】 STDMA;多跳無線網(wǎng);媒體介入控制;調(diào)度【中圖分類號】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引言兩種基本 STDMA調(diào)度策略之一是將傳輸權(quán)直接賦予節(jié)在多跳無線網(wǎng)中一個具有挑戰(zhàn)性的問題是如何保證延點。另一種將傳輸權(quán)賦予鏈路。節(jié)點分配算法和鏈路分配算遲。相關(guān)文獻研究表明使用CSMA的接入方式,在需提供具有法在文獻[2]中有過深入的探討。研究表明不論是節(jié)點分配延遲保證的應用環(huán)境表現(xiàn)很差。解決這類問題可以引入時還是鏈路分配在尋找最小長度調(diào)度是都歸結(jié)為全NP問題分多址接入TDM。但在 Ad hoc網(wǎng)絡(luò)中鏈路相對較少時使用在本文中,我們提出了一個結(jié)合兩者優(yōu)點的分配策略。該策效率不高。一個對TDM機制的有效改進方法是空分TDM,它略基于鏈路調(diào)度,但是傳輸權(quán)被擴展。該方式提高了鏈路分將無線結(jié)點之間的物理距離考慮在內(nèi),規(guī)定互相不干擾的通訊鏈路可以在相同的時間片內(nèi)傳輸,從而減少了網(wǎng)絡(luò)所需時配的空間利用程度。為了對比該策略是否優(yōu)于單純的節(jié)點或間片的總量,從而提高了整個網(wǎng)絡(luò)的吞吐量。其容量的提高鏈路分配,我們使用在TDMA調(diào)度中經(jīng)常使用的網(wǎng)絡(luò)干擾模通過時隙的空間復用來實現(xiàn),而延遲保證有TDM來提供型。我們將分別采用分析法和仿真來估計該策略在不同網(wǎng)絡(luò)通性下的端到端時延和吞吐量收稿日期:2008-12-31作者簡介:韓成(1984-),男,碩士研究生,主要研究方向為無線移動網(wǎng)絡(luò)MAC技術(shù)、組網(wǎng)技術(shù):吳援明(1966-),男,教1網(wǎng)絡(luò)模型碩士生導師,主要研究方向為現(xiàn)代通信中的信號處理。假設(shè)使用全向天線并且所有節(jié)點具有相同的傳輸功率。對于任意兩個節(jié)點(,),其中v表示發(fā)送節(jié)點,ν表示接包的傳輸方向,除了分配的接收節(jié)點外,新的接收節(jié)點對于收節(jié)點,且v≠v,節(jié)點v和節(jié)點v之間的鏈路可以成功傳不等式(4)n(,0≥y,,V()∈L仍能得到滿足,這就意輸分組的條件是節(jié)點間的信噪比(SNR)超過一個門限,即味著對于其他接收節(jié)點的干擾級別并沒有改變。r=PG(,2基于上述理由改進的面向鏈路分配策略可以描述為,對于已分配時隙的鏈路,首先檢查該條鏈路上是否有分組需要其中,P表示發(fā)送節(jié)點v的傳輸功率。G(,)表示節(jié)點v2、傳輸,如果沒有便將該時隙分配給具有相同發(fā)送節(jié)點的其他,之間的鏈路增益。N表示在接收節(jié)點所有的噪聲功率。鏈路(該鏈路上存在數(shù)據(jù)包傳送)。當然為了避免不必要的分如果SNR不小于通信門限y’我們說一對節(jié)點C,v)形成組丟失,無沖突鏈路可以按照優(yōu)先級來選擇。我們定義該策條鏈路()。n表示網(wǎng)絡(luò)中形成的鏈路集合,定義為略為基于擴展傳輸權(quán)限的鏈路分配策略 LET (Linkn={(0:≥7}。任意的鏈路集合的子集L≤n,定義t with Extended Transmission Rights)發(fā)送節(jié)點(L)=:(,)∈L}。下面我們證明重新分配傳輸權(quán)的鏈路不會對本時隙中干擾包括背景噪聲和所有并發(fā)鏈路的同頻干擾。對于任其他鏈路引入附加的競爭。設(shè)按照公式(4)能同時傳輸?shù)逆溡怄溌?j)∈L,定義干擾如下路集合為L,則∏(j≥γ,(,j∈L。打算撤銷傳輸權(quán)l(xiāng)()=∑PG(k,),的鏈路集合為La(La∈L),該時隙余下的鏈路集合設(shè)為L,滿足關(guān)系L=L\L。重新分配傳輸權(quán)的鏈路集合為因此,信干噪比∏4(,八可由以下式子求得L,可推得V(L)=V(La)。由于L為無沖突鏈路集合,n0)=-.PG(k(3)因此需要證明下式無等式成立(N+l1(i,∏L,(,)≥y,v(,))∈LNR我們假設(shè)當任意節(jié)點間的SIR大于最小通信門限y時,任意根據(jù)式(4)信干噪比SNR定義可知:兩個通信節(jié)點間都能無錯誤的傳輸分組并在一個時隙內(nèi)不(i,))∈Lw能同時發(fā)送和接收。調(diào)度策略S定義為一個集合xPG(i,Dt=1,2…,T,其中T表示調(diào)度周期。集合X,中包含已分配了14(,)=(N+(n)時隙t的節(jié)點或者鏈路。如果該集合內(nèi)所有節(jié)點的SIR都小于門限γ,我們稱該調(diào)度為無干擾調(diào)度又因為,V(La∪L)=V(L2)V7(L)=V(L∪L)=2分配策略描述V(L,所以干擾l(,=L(),信干噪比∏n(n2.1鏈路分配策略∏4(,j),則式(6)成立。證明了LET分配策略不會在任何節(jié)如果{⌒伙,}≠φ,鏈路(k,D)稱為鏈路(,的鄰近點之間引入附加的競爭。鏈路。時隙t對應分配的鏈路集合為L,由此我們定義平(L)為集合L中各鏈路對應的鄰近鏈路旁集合。當滿足如下兩個3分配策略性能分析條件:本節(jié)我們將給出LET性能的一些分析結(jié)果。首先討論吞L∩(L)=;∏(i,j)≥y,,V(i,j∈L,(4)吐量其次計算在低業(yè)務(wù)到達率前提下的分組延時。時隙t分配的鏈路集合L中各鏈路能同時傳輸。3.1分配策略對網(wǎng)絡(luò)吞吐率的影響2.2節(jié)點分配策略文獻[4]中討論了在固定鏈路容量和固定路由下的網(wǎng)絡(luò)在面向節(jié)點的分配策略中,我們定義時隙4對應分配的吞吐量。文獻5]中提出了鏈路調(diào)度策略的網(wǎng)絡(luò)最大吞吐量節(jié)點集合為V,定義集合V中某一節(jié)點v(v∈V)的鄰節(jié)點A2。重寫如下為Φ(),這里的鄰居節(jié)點表示能同時接收到節(jié)點ν傳輸?shù)姆諲(N-I)h組。設(shè)集合所有節(jié)點的鄰節(jié)點為Φ(V),L()表示Φ(V)TA相關(guān)的鏈路集合,為了滿足集合V中的節(jié)點以及L()中鏈其中T是鏈路調(diào)度的長度。N表示節(jié)點的數(shù)目,N=。b路能同時傳輸分組,同樣也需要滿足如下兩個約束表示在一個調(diào)度幀長內(nèi),分配給鏈路(,0的時隙數(shù)量。A表Ln9)=;nlmn(,)≥y,v(i,∈L(),(5)示路由表中包含(i,)鏈路的路徑式(5)表示的物理意義為同時傳輸?shù)墓?jié)點不應有相同的鄰節(jié)的網(wǎng)絡(luò)最大吞吐量列如下所布量。對應地,按節(jié)點分配點以及同時傳輸節(jié)點的鏈路相互不應有干擾=N(N-)2.3改進的面向鏈路分配策略T-A我們注意到式(3)發(fā)生沖突檢測的條件依賴于數(shù)據(jù)包發(fā)其中7是節(jié)點調(diào)度的長度,b表示在一個調(diào)度幀長內(nèi),分送節(jié)點,而不在于接收節(jié)點上。假定某一節(jié)點在該時隙中分配給節(jié)點()的時隙數(shù)量。4表示路由表中包含節(jié)點()的路配為發(fā)送節(jié)點,這樣就存在一條傳輸鏈路,如果要更改數(shù)據(jù)徑數(shù)量從以上兩式可以看出,如果所有節(jié)點或鏈路都處于飽和絡(luò)連通性有不同的吞吐量比,隨著連通性的下降鏈路分配能狀態(tài),那么平均分組時延將會無限長。這時節(jié)點吞吐量實現(xiàn)更高的吞吐量。在20節(jié)點低業(yè)務(wù)負載條件下,我們探A/NN-1)就與T/h相等。而且在鏈路調(diào)度中對業(yè)務(wù)進討鏈路分配平均時延D2與節(jié)點分配平均時延D間的比值行完全補償(=4)后,上述網(wǎng)絡(luò)吞吐量的計算可以分別簡關(guān)系。從圖2可以看出比值基本與連通率呈線性關(guān)系。從數(shù)化為值上看,鏈路分配時延遠遠大于節(jié)點分配時延。并隨連通率的增大而增大下面我們來探討節(jié)點分配與LET的關(guān)系,如圖3為20這樣上式就建立起兩種分配方案與吞吐量之間的關(guān)系個節(jié)點、低延遲負載條件下,D/Dx的比值大小。(10)所以兩種分配方案下的吞吐量與 STDMA幀長度相關(guān)。3.2分配策略對網(wǎng)絡(luò)延時的影響轉(zhuǎn)發(fā)業(yè)務(wù)可以使用泊松分布過程來描述。根據(jù)網(wǎng)絡(luò)延時的定義,在面向鏈路的分配策略中對于廣播業(yè)務(wù)系統(tǒng)網(wǎng)絡(luò)延時為d=7/2h其中d為鏈路(i,)的平均 edge delayo如果對業(yè)務(wù)進行完全補償(=A)后:M7D=2N(N-1)圖1吞吐量之比與連通率的關(guān)系這里M為網(wǎng)絡(luò)中所有鏈路的總數(shù)同理,對于面向節(jié)點的分配策略中網(wǎng)絡(luò)延時完全補償后為D故兩種分配策略的延M T MAD、NTNA以上兩點假設(shè)對LET策略同樣適用,但由于LET在低業(yè)務(wù)負載情況下表現(xiàn)為節(jié)點分配調(diào)度。因此鏈路分配策略必須擴展到節(jié)點,并按照調(diào)度中的安排進行廣播或單播。因此LET策略的延時可以定義為D=∑A。進行業(yè)務(wù)完全補N(N-1)2h圖2兩種分配策略延時比值關(guān)系NTL償后D1=2N(N-1)因此鏈路分配、節(jié)點分配分別與LET之間的時延關(guān)系如下N DLET可見,分配策略時延關(guān)系與網(wǎng)絡(luò)大小、連通度以及調(diào)度周期有關(guān)。仿真本節(jié)我們評價在不同連接性和節(jié)點數(shù)下,網(wǎng)絡(luò)的吞吐量圖3不同節(jié)點數(shù)目下吞吐量與連通性的關(guān)系和時延。為了便于比較分別生成了500個節(jié)點數(shù)量為10、20如果參數(shù)值大于1則說明LET策略在低負載條件下時比值和40的網(wǎng)絡(luò)拓撲。每個節(jié)點平均產(chǎn)生參數(shù)為λ的泊松過程數(shù)與連通率的關(guān)系,可以看出在不同網(wǎng)絡(luò)拓撲下該值變化較大據(jù)流。由于傳輸功率P不同,將導致拓撲結(jié)構(gòu)連通性的變化。圖4為在10/20/40節(jié)點條件下平均D、D比值關(guān)系這里定義連通性為單跳內(nèi)平均每節(jié)點的鏈路數(shù),即D、Da隨著連通率的提高而降低,這是由于連通率的提高導M/(N(N-1)。M表示網(wǎng)絡(luò)中所有鏈路的數(shù)量致鏈路分配空分復用能力的降低。并且在中低連了在20節(jié)點高業(yè)務(wù)負載條件下,鏈路分配最大吞吐量和D、/D4x<1的情況。而網(wǎng)絡(luò)中節(jié)點數(shù)越多D、Dx比值越大,節(jié)點分配最大吞吐量的比值λ2入,根據(jù)式(10)應等于即LET延遲越小,這是因為網(wǎng)絡(luò)越大每個節(jié)點可供傳輸?shù)闹車鶷/T。仿真結(jié)果如圖1所示。從圖中可以看出,鏈路分配節(jié)點越多,則LT策略可選的鏈路也就越多,以致時延減少。策略性能比節(jié)點分配策略提供更大的吞吐量,而且不同的網(wǎng)(下轉(zhuǎn)第95頁范圍在-4~4dBm之間,Δα的取值范圍在-0.5~0.5之間多邊定位法具有更好的魯棒性,而在噪聲較小,差圓法的性設(shè)信號衰減模型的參數(shù)為P=-30dBm和α=3。上述算法能優(yōu)勢比較明顯中的閾值0=0.5dBm。使用4個錨節(jié)點,排列方式如圖3所示,未知節(jié)點位置在圖3所示區(qū)域內(nèi)任意分布3結(jié)語▲錨節(jié)點本文在實測RSSI數(shù)據(jù)的基礎(chǔ)上指出了信號衰減模型時變性的特點,事實上,無法建立足夠精確的無線信號強度衰減模型正是影響基于RSSI的定位算法精度提高的主要原因之一。針對這一問題,本文提出了一種新的定位法—差圓法。該算法是針對目前使用RSSI測距的定位方法對模型參數(shù)依賴較大的問題進行的一些改進。差圓法實際上通過弱化衰減模型在定位算法中的作用從而在一定程度上提高了定位的精度。通過仿真也進一步證明在噪聲較小時,差圓法具有較好的定位性能。但是該方法的抗噪聲性能不佳,在噪聲較大時性能惡化比較嚴重,這是需要改進的方向之一,例如圖3錨節(jié)點分布及定位區(qū)域示意圖引入加權(quán)思想等。盡管差圓法具有一定局限性,但在針對為了不失一般性,在圖3所示待定位區(qū)域內(nèi),隨機的產(chǎn)型的處理上提出了新思路,具有一定研究價值。生10000個目標節(jié)點,將定位結(jié)果的誤差進行平均。式(12)中高斯隨機變量X均值為零,在不同的標準差下,兩種算參考文獻法的定位誤差如圖4所示[1]于宏毅,李鷗,張效義,無線傳感器網(wǎng)絡(luò)理論技術(shù)與實現(xiàn)[M].北京:國防工業(yè)出版社,2008[2]王福豹,史龍,任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J]軟件學報,2005,16(5):857-868[3]王建剛,王福豹,段渭軍.加權(quá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仿真結(jié)果如圖4所示,在噪聲較小時,差圓法具有較好7] Savarese C, Raba j, Langendoen K. Robust positioner的性能,當噪聲增大時,性能開始惡化,這主要是由于所構(gòu)Algorithms for Distributed Ad hoc Wireless Sensor Networks造的圓曲線方程不能夠相交造成的,具體的數(shù)學原理在此限[C]//Carla Schlatter Ellis. Proceedings of The USENIX于篇幅在此不再討論,應當指出的是,同樣的原因也造成了Technical Annual Conference. Monterey: USENIX Press, 2002多邊定位法的性能惡化,不過相比較而言,在噪聲較大時,17-327.(上接第92頁)Radio Networks [J]. IEEE/ACM Trans. Networking, 1993, 1(02)5結(jié)語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)更高的空間復用能力比節(jié)點分配具有更好的吞吐量。相反地,34-944在低業(yè)務(wù)負載下節(jié)點分配能提供節(jié)點間更短的傳輸時間。從仿[3 Arikan E. Some Complexbout Packet Radio真結(jié)果可以看出,LET策略在保持高吞吐量的前提下,時延比鏈路分配低很多。而且在中低連通率條件下也比節(jié)點分配低Networks[J. IFFE Trans. Inform.1984(IT-30):910918這說明LET策略很好地結(jié)合的兩者的優(yōu)點,使性能達到最佳。[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