多跳无线网中基于空分TDMA的时隙分配策略

2010年第03期,第43卷通信技术Vol.43,No.03,2010总第219期Communicat ions TechnologyNo. 219, Totally多跳无线网中基于空分TDMA的时隙分配策略韩成,吴援明(电子科技大学光电信息学院,四川成都610054)【摘要】空分TDMA( STDMA)是基于TDMA的信道接入协议,该技术被应用于实时性要求较高的多跳( multi-hop)无线网络中,并可使多个在地理位置相互独立的移动终端使用相同的时隙来増加网络容量,不冋移动终端之间的教据传输通过对终端调度安排来实现。调度算法一般分为基于节点或基于链路的分配方式。对这两种方式对比发现,在一定条件下两者都有不理想的特性。因此,结合两种方式优点提出了一种新颖的分配策略。仿真结果表眀:该分配策略在高业务负载情况下能满足链路分配的高吞吐量,也能达到低业务负載下节点分配的低延迟【关键词】 STDMA;多跳无线网;媒体介入控制;调度【中图分类号】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调度策略之一是将传输权直接赋予节在多跳无线网中一个具有挑战性的问题是如何保证延点。另一种将传输权赋予链路。节点分配算法和链路分配算迟。相关文献研究表明使用CSMA的接入方式,在需提供具有法在文献[2]中有过深入的探讨。研究表明不论是节点分配延迟保证的应用环境表现很差。解决这类问题可以引入时还是链路分配在寻找最小长度调度是都归结为全NP问题分多址接入TDM。但在 Ad hoc网络中链路相对较少时使用在本文中,我们提出了一个结合两者优点的分配策略。该策效率不高。一个对TDM机制的有效改进方法是空分TDM,它略基于链路调度,但是传输权被扩展。该方式提高了链路分将无线结点之间的物理距离考虑在内,规定互相不干扰的通讯链路可以在相同的时间片内传输,从而减少了网络所需时配的空间利用程度。为了对比该策略是否优于单纯的节点或间片的总量,从而提高了整个网络的吞吐量。其容量的提高链路分配,我们使用在TDMA调度中经常使用的网络干扰模通过时隙的空间复用来实现,而延迟保证有TDM来提供型。我们将分别采用分析法和仿真来估计该策略在不同网络通性下的端到端时延和吞吐量收稿日期:2008-12-31作者简介:韩成(1984-),男,硕士研究生,主要研究方向为无线移动网络MAC技术、组网技术:吴援明(1966-),男,教1网络模型硕士生导师,主要研究方向为现代通信中的信号处理。假设使用全向天线并且所有节点具有相同的传输功率。对于任意两个节点(,),其中v表示发送节点,ν表示接包的传输方向,除了分配的接收节点外,新的接收节点对于收节点,且v≠v,节点v和节点v之间的链路可以成功传不等式(4)n(,0≥y,,V()∈L仍能得到满足,这就意输分组的条件是节点间的信噪比(SNR)超过一个门限,即味着对于其他接收节点的干扰级别并没有改变。r=PG(,2基于上述理由改进的面向链路分配策略可以描述为,对于已分配时隙的链路,首先检查该条链路上是否有分组需要其中,P表示发送节点v的传输功率。G(,)表示节点v2、传输,如果没有便将该时隙分配给具有相同发送节点的其他,之间的链路增益。N表示在接收节点所有的噪声功率。链路(该链路上存在数据包传送)。当然为了避免不必要的分如果SNR不小于通信门限y’我们说一对节点C,v)形成组丢失,无冲突链路可以按照优先级来选择。我们定义该策条链路()。n表示网络中形成的链路集合,定义为略为基于扩展传输权限的链路分配策略 LET (Linkn={(0:≥7}。任意的链路集合的子集L≤n,定义t with Extended Transmission Rights)发送节点(L)=:(,)∈L}。下面我们证明重新分配传输权的链路不会对本时隙中干扰包括背景噪声和所有并发链路的同频干扰。对于任其他链路引入附加的竞争。设按照公式(4)能同时传输的链意链路(j)∈L,定义干扰如下路集合为L,则∏(j≥γ,(,j∈L。打算撤销传输权l()=∑PG(k,),的链路集合为La(La∈L),该时隙余下的链路集合设为L,满足关系L=L\L。重新分配传输权的链路集合为因此,信干噪比∏4(,八可由以下式子求得L,可推得V(L)=V(La)。由于L为无冲突链路集合,n0)=-.PG(k(3)因此需要证明下式无等式成立(N+l1(i,∏L,(,)≥y,v(,))∈LNR我们假设当任意节点间的SIR大于最小通信门限y时,任意根据式(4)信干噪比SNR定义可知:两个通信节点间都能无错误的传输分组并在一个时隙内不(i,))∈Lw能同时发送和接收。调度策略S定义为一个集合xPG(i,Dt=1,2…,T,其中T表示调度周期。集合X,中包含已分配了14(,)=(N+(n)时隙t的节点或者链路。如果该集合内所有节点的SIR都小于门限γ,我们称该调度为无干扰调度又因为,V(La∪L)=V(L2)V7(L)=V(L∪L)=2分配策略描述V(L,所以干扰l(,=L(),信干噪比∏n(n2.1链路分配策略∏4(,j),则式(6)成立。证明了LET分配策略不会在任何节如果{⌒伙,}≠φ,链路(k,D)称为链路(,的邻近点之间引入附加的竞争。链路。时隙t对应分配的链路集合为L,由此我们定义平(L)为集合L中各链路对应的邻近链路旁集合。当满足如下两个3分配策略性能分析条件:本节我们将给出LET性能的一些分析结果。首先讨论吞L∩(L)=;∏(i,j)≥y,,V(i,j∈L,(4)吐量其次计算在低业务到达率前提下的分组延时。时隙t分配的链路集合L中各链路能同时传输。3.1分配策略对网络吞吐率的影响2.2节点分配策略文献[4]中讨论了在固定链路容量和固定路由下的网络在面向节点的分配策略中,我们定义时隙4对应分配的吞吐量。文献5]中提出了链路调度策略的网络最大吞吐量节点集合为V,定义集合V中某一节点v(v∈V)的邻节点A2。重写如下为Φ(),这里的邻居节点表示能同时接收到节点ν传输的分N(N-I)h组。设集合所有节点的邻节点为Φ(V),L()表示Φ(V)TA相关的链路集合,为了满足集合V中的节点以及L()中链其中T是链路调度的长度。N表示节点的数目,N=。b路能同时传输分组,同样也需要满足如下两个约束表示在一个调度帧长内,分配给链路(,0的时隙数量。A表Ln9)=;nlmn(,)≥y,v(i,∈L(),(5)示路由表中包含(i,)链路的路径式(5)表示的物理意义为同时传输的节点不应有相同的邻节的网络最大吞吐量列如下所布量。对应地,按节点分配点以及同时传输节点的链路相互不应有干扰=N(N-)2.3改进的面向链路分配策略T-A我们注意到式(3)发生冲突检测的条件依赖于数据包发其中7是节点调度的长度,b表示在一个调度帧长内,分送节点,而不在于接收节点上。假定某一节点在该时隙中分配给节点()的时隙数量。4表示路由表中包含节点()的路配为发送节点,这样就存在一条传输链路,如果要更改数据径数量从以上两式可以看出,如果所有节点或链路都处于饱和络连通性有不同的吞吐量比,随着连通性的下降链路分配能状态,那么平均分组时延将会无限长。这时节点吞吐量实现更高的吞吐量。在20节点低业务负载条件下,我们探A/NN-1)就与T/h相等。而且在链路调度中对业务进讨链路分配平均时延D2与节点分配平均时延D间的比值行完全补偿(=4)后,上述网络吞吐量的计算可以分别简关系。从图2可以看出比值基本与连通率呈线性关系。从数化为值上看,链路分配时延远远大于节点分配时延。并随连通率的增大而增大下面我们来探讨节点分配与LET的关系,如图3为20这样上式就建立起两种分配方案与吞吐量之间的关系个节点、低延迟负载条件下,D/Dx的比值大小。(10)所以两种分配方案下的吞吐量与 STDMA帧长度相关。3.2分配策略对网络延时的影响转发业务可以使用泊松分布过程来描述。根据网络延时的定义,在面向链路的分配策略中对于广播业务系统网络延时为d=7/2h其中d为链路(i,)的平均 edge delayo如果对业务进行完全补偿(=A)后:M7D=2N(N-1)图1吞吐量之比与连通率的关系这里M为网络中所有链路的总数同理,对于面向节点的分配策略中网络延时完全补偿后为D故两种分配策略的延M T MAD、NTNA以上两点假设对LET策略同样适用,但由于LET在低业务负载情况下表现为节点分配调度。因此链路分配策略必须扩展到节点,并按照调度中的安排进行广播或单播。因此LET策略的延时可以定义为D=∑A。进行业务完全补N(N-1)2h图2两种分配策略延时比值关系NTL偿后D1=2N(N-1)因此链路分配、节点分配分别与LET之间的时延关系如下N DLET可见,分配策略时延关系与网络大小、连通度以及调度周期有关。仿真本节我们评价在不同连接性和节点数下,网络的吞吐量图3不同节点数目下吞吐量与连通性的关系和时延。为了便于比较分别生成了500个节点数量为10、20如果参数值大于1则说明LET策略在低负载条件下时比值和40的网络拓扑。每个节点平均产生参数为λ的泊松过程数与连通率的关系,可以看出在不同网络拓扑下该值变化较大据流。由于传输功率P不同,将导致拓扑结构连通性的变化。图4为在10/20/40节点条件下平均D、D比值关系这里定义连通性为单跳内平均每节点的链路数,即D、Da随着连通率的提高而降低,这是由于连通率的提高导M/(N(N-1)。M表示网络中所有链路的数量致链路分配空分复用能力的降低。并且在中低连了在20节点高业务负载条件下,链路分配最大吞吐量和D、/D4x<1的情况。而网络中节点数越多D、Dx比值越大,节点分配最大吞吐量的比值λ2入,根据式(10)应等于即LET延迟越小,这是因为网络越大每个节点可供传输的周围T/T。仿真结果如图1所示。从图中可以看出,链路分配节点越多,则LT策略可选的链路也就越多,以致时延减少。策略性能比节点分配策略提供更大的吞吐量,而且不同的网(下转第95页范围在-4~4dBm之间,Δα的取值范围在-0.5~0.5之间多边定位法具有更好的鲁棒性,而在噪声较小,差圆法的性设信号衰减模型的参数为P=-30dBm和α=3。上述算法能优势比较明显中的阈值0=0.5dBm。使用4个锚节点,排列方式如图3所示,未知节点位置在图3所示区域内任意分布3结语▲锚节点本文在实测RSSI数据的基础上指出了信号衰减模型时变性的特点,事实上,无法建立足够精确的无线信号强度衰减模型正是影响基于RSSI的定位算法精度提高的主要原因之一。针对这一问题,本文提出了一种新的定位法—差圆法。该算法是针对目前使用RSSI测距的定位方法对模型参数依赖较大的问题进行的一些改进。差圆法实际上通过弱化衰减模型在定位算法中的作用从而在一定程度上提高了定位的精度。通过仿真也进一步证明在噪声较小时,差圆法具有较好的定位性能。但是该方法的抗噪声性能不佳,在噪声较大时性能恶化比较严重,这是需要改进的方向之一,例如图3锚节点分布及定位区域示意图引入加权思想等。尽管差圆法具有一定局限性,但在针对为了不失一般性,在图3所示待定位区域内,随机的产型的处理上提出了新思路,具有一定研究价值。生10000个目标节点,将定位结果的误差进行平均。式(12)中高斯随机变量X均值为零,在不同的标准差下,两种算参考文献法的定位误差如图4所示[1]于宏毅,李鸥,张效义,无线传感器网络理论技术与实现[M].北京:国防工业出版社,2008[2]王福豹,史龙,任丰原.无线传感器网络中的自身定位系统和算法[J]软件学报,2005,16(5):857-868[3]王建刚,王福豹,段渭军.加权最小二乘估计在无线传感器网络定位中的应用[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所示,在噪声较小时,差圆法具有较好7] Savarese C, Raba j, Langendoen K. Robust positioner的性能,当噪声增大时,性能开始恶化,这主要是由于所构Algorithms for Distributed Ad hoc Wireless Sensor Networks造的圆曲线方程不能够相交造成的,具体的数学原理在此限[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结语166-177从以上三种分配策略分析表明,策略的选择与网络连通率[2] Nelson R, Kleinrock L, Spatial-TDMA: A Collision-free Multihe业务负载和网络大小有关。在高业务负载下,由于链路分配有Channel Access Protocol[]. IEEE Trans, Commun., 1985, 33(09)更高的空间复用能力比节点分配具有更好的吞吐量。相反地,34-944在低业务负载下节点分配能提供节点间更短的传输时间。从仿[3 Arikan E. Some Complexbout Packet Radio真结果可以看出,LET策略在保持高吞吐量的前提下,时延比链路分配低很多。而且在中低连通率条件下也比节点分配低Networks[J. IFFE Trans. Inform.1984(IT-30):910918这说明LET策略很好地结合的两者的优点,使性能达到最佳。[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