WSN内一种基于TDMA的时隙优化重组算法

李 峰，范 菁，黄 道

（1.云南民族大学云南省高校无线传感器网络重点实验室，云南昆明650500；2.云南民族大学电气信息工程学院，云南昆明650500）

WSN内一种基于TDMA的时隙优化重组算法

李 峰1，范 菁1，黄 道2

（1.云南民族大学云南省高校无线传感器网络重点实验室，云南昆明650500；2.云南民族大学电气信息工程学院，云南昆明650500）

无线传感器网络内节点的时隙分配是影响整个网络能耗、时延的重要因素.STDMA的时隙分配算法能避免数据碰撞，在一定程度上降低了能量损耗，但由于每个节点分配的时隙固定、离散，造成节点频繁启动，损耗了大量能量，为此，在STDMA的基础之上提出了OTT-TDMA算法，在MAC层重新调度时隙，减少节点启动次数，同时尽量将节点发送时隙调度到接收时隙之后.实验仿真表明，改进算法在能耗和时效性方面比STDMA有一定提高.

无线传感器网络；时隙重组；时延；MAC；能量损耗

无线传感器网络（wireless sensor networks，WSN）是由分布在物理空间上的大量无线传感器节点通过自组织形式构成的网络.网络中每个传感器节点都具有一种或多种感知器，能在所分布空间内进行多领域、大范围的实时数据采集，在国防工业、险情监测等领域有广泛的应用.无线传感器网络常部署在恶劣环境和人不宜到达的场所［1］，因此节点能量的补充受到了极大的限制，而良好的MAC层协议设计不仅可以减小WSN的能耗，还能提高WSN的时效性.文献［2-3］分析了合理的MAC层协议设计对能量效率的有效提高.STDMA［4］（spatial time division multiple access）被视为一种主要的MAC层协议，因为它一方面提供了无碰撞的多信道接入，另一方面它允许多条非冲突链路在同一时隙中进行传输，有效降低了能量损失，提高了网络的吞吐量.文献［5-6］分析节点的频繁启动会造成能量的损失，然而只局限在链路层的能量优化.事实上，MAC层的时隙重组是有效减少启动次数的最佳选择.文献［7］分析了采用全向天线时网络内存在的广播风暴和信号干扰问题.

本文阐述了时隙分配机制，分析、归纳了STDMA时隙分配算法，利用STDMA无碰撞接入和链路容量大的优势，针对数据汇聚树这种拓扑结构，提出了OTT-TDMA算法，在MAC层重新调度时隙，从根本上降低能耗与时延.本文的研究在基于使用定向天线节点基础上展开，因为定向天线允许在同一邻近区域内同时进行多个发送，而不会损坏被发送的分组［7］.

1 时隙分配

WSN内节点间的数据传输总是在某个信道上完成的，因此可以通过将信道进行时间分隙来描述节点的激活-休眠机制.不同拓扑结构的WSN根据自身节点数目、拓扑形态在信道上沿时间轴划分不同的周期Tf.每个周期Tf包含数量不同、长度均为τ的时隙，且满足Tf＝mτ（其中m为Tf内包含的时隙个数，τ为时隙长度）.当节点在周期Tf的第i个时隙为激活态且这个时隙为发送时隙时，将此时隙按图1所示标记为1，用tran表示；当节点在周期Tf的第i个时隙为激活态且这个时隙为接收时隙时，将此时隙标记为-1，用rece表示；当节点处于休眠态时，相应的标记为0.当节点在某个时隙采集到或是接收到来自子节点的数据，用prod表示这个时隙.

这样，可以将某个节点i的激活／休眠周期通过一个向量V来表示.若将节点的向量V按节点序号排列则可得到整个网络内节点的时隙分配矩阵.

1.1 基于定向天线节点的TDMA时隙分配规则

WSN内存在2类碰撞［8-9］，第1类碰撞是本节点自身收发数据的碰撞；第2类碰撞是本节点和其他节点之间发送数据时产生的碰撞.不满足上述2类碰撞的链路，证明他们可以在同一时隙内共存，在使用全向天线的WSN内STDMA无冲突链路间分配时隙的准则，可以归纳为：①只要指定链路在传输数据，该链路的发送节点一跳之内的所有邻居节点（接收节点除外）将不能在该时隙内发送数据和接收数据；②指定链路的发送节点2跳以外的节点既可以在该时隙内发送数据，也可以接收数据；③如果该节点恰好是此链路发送节点的2跳邻居节点，则该节点不能发送数据.由于本文的研究基础是使用定向天线的WSN，允许在同一邻近区域内有多个发送同时进行，因此发送链路发送节点的2跳邻居节点可以发送数据［7］.以13个节点的拓扑结构为例（如图2），通过以上规则可确定其整个网络内节点的时隙分配矩阵如图3所示.

从网络内节点的时隙分配矩阵可以看出，此种时隙分配虽然满足了无碰撞的条件，却分配得很散乱，节点在一帧内的启动次数较多.且接收时隙与发送时隙的顺序安排也是随机的，增大了排队时延.

1.2 OTT-TDMA算法时隙重组

图3中，每一时隙内启动节点数目相差很大，各节点在1帧内的启动次数也是不一样的，整个帧在网络中的节点激活时隙十分散乱.这是由于在STDMA帧划分无冲突域时，未考虑节点重启能耗，这样分配时隙会使某些节点在1帧内的启动次数很多（启动次数最大可以占到激活次数的2／3），使得节点不断地开启和关闭，造成大量的能量浪费.

在此将运用OTT-TDMA（optimal timeslot table TDMA）算法，对每一帧的时隙进行重新组合，使每一帧的每个节点启动次数在满足STDMA的条件下降到最低，如图4所示.

由图4可以看出，整个网络内的发送链路并未改变，只是调整了各个链路的激活时隙.如链路｛7，6｝的激活时隙由第1个变为第4个.调整后的时隙分配矩阵，激活时隙都连在一起且发送时隙一般都被安排在接收时隙之后，既减少了重启能耗又减少了同步时延和排队时延.

2 激活时隙反转分析

STDMA采取的是一种静态的时隙分配法则，即在1帧内给节点分配固定的激活时隙，无论在此时隙节点有无数据发送都会被激活.本文协议在此基础上改进.根据本文协议的设计，节点的发送状态除了当节点所处信道的时隙标记为1时会发生，还会在这种情况下发生：当节点和它的父节点在同一个时隙内都处于接收状态，父节点在此接收时隙对应的子节点和节点在此接收时隙对应的子节点都无数据发送且节点缓存内有数据时，节点在此时隙内由接收状态转变为发送状态，向父节点发送数据，并将此时隙记为tran.例如在图2的拓扑结构中，6、7节点在第3个时隙都处于接收状态，当7节点在此时隙下对应的子节点9及节点6在此时隙下对应的子节点8都无数据发送，且7节点缓存内有数据要发送时，节点7由接收状态转变为发送状态，向父节点6发送数据.

3 时延分析

数据包在传递过程中存在2类时延：①节点在产生／接收到数据包后往往不能立即被发送，需等到本帧的发送时隙才能发送，这个等待过程称为同步时延；②存在缓存内的数据包如果在本帧未被选中发送，需等下一帧的发送时隙，这个等待过程称为排队时延.数据包的总时延即同步时延与排队时延之和.

如果拓扑结构内处在第φ层编号为i的节点在第j个时隙采集到了1个数据包，试图传向信宿节点，则在向上传递过程中它在各层所产生的时延可表示为d（i，j，k），其中k表示它所处的层.

其中prodk表示数据包在链路中第k层时被采集／接收到的时隙，trank表示对应的发送时隙.则这个数据包在网络中传输的总时延：

网络中数据包是并行传输，因此1帧数据传输的总时延

4 能耗分析

研究表明无线传感器节点的能量主要消耗在无线通信模块，传感器模块和处理器模块的能耗相对较少.通信耗能以几个数量级的规模大于计算耗能和感知耗能，因此可以忽略计算耗能和感知耗能.

如果在拓扑结构内处在第k层编号为i的节点在第j个时隙采集到1个数据包，试图传向信宿节点，则在向上传递过程中它的能耗e可表示为：

其中Ptx为发送功率，Prx为接收功率，Ttx为发送时间，Trx为接收时间，Pout为天线驱动功率（很小，可略为0），（k-1）为数据包转发的次数.其在网络内的总发送时间可表示为T＝（k-1）Ttx.数据负荷为i的网络内，1帧的能耗等于激活空闲能耗与数据包发送、接收能耗之和.可表示为：

其中n为网络内激活时隙数，τ为时隙宽度，pact为激活空闲功率.

5 仿真实验与结果分析

5.1 仿真环境设置

本文采用Matlab进行仿真，仿真均基于同一实验场景：13个无线传感器节点通过自组织的方式形成图2所示的WSN.仿真所用模型分别是STDMA算法与本文提出的OTT-TDMA算法.2种算法设置的参数相同，仿真主要参数如表1.

表1 仿真参数

5.2 仿真结果与分析

设网络内每个帧长所产生数据包从1～30变化.在2种算法下网络总时延变化如图5.由图5可得，在相同的仿真场景下OTT-TDMA算法的总时延基本低于STDMA算法的总时延，且随着网络负荷增大网络总时延也呈增大趋势.这是因为新算法总是尽量将发送时隙安排在接收时隙之后，以此来减少数据包转发过程中的同步、排队时延，时隙反转算法也能在一定程度上降低时延，网络负载增大，节点缓存内数据包增多，数据包的排队时延随之增大，传输时延也随之增大.

设网络内每个帧长所产生数据包从6～10变化.在2种算法模式下包平均能耗变化如图6.从图6中可以看出在相同的仿真场景下OTT-TDMA算法的包平均能耗要低于STDMA算法，且随着网络负载增大，包平均能耗降低.这是因为新算法将节点的激活时隙连结到了一块，降低了节点的启动能耗.网络内的激活时隙数固定，节点接收／发送功率与激活空闲功率相近，所以在2种算法下帧能耗都相对固定，包平均能耗随负荷增大而下降.

［1］AKYILDIZ I F，SU W，SANKARASUBRAMANIAM Y，et al.Wireless sensor networks：A survey［J］.Computer Networks，2002，38（4）：393-422.

［2］XIAO X，ZHENG B Y，YAN ZY，et al.Energy efficient TDMA-based MAC protocol associated with GAF for wireless sensor networks［J］.The Journal of China Universities of Posts and Telecommunications，2007，14（1）：6-11.

［3］LU X F，TOWSLEY D，LIO P，et al.An adaptive directional MAC protocol for ad hoc networks using directional antennas［J］.Science China Information Sciences，2012，55（6）：1360-1371.

［4］LATTANZI E，REGINIE，ACQUAVIVA A，et al.Energetic sustainability of routing algorithms for energy-harvesting wireless sensor networks［J］.Computer Communications，2007，30（14）：2976-2986.

［5］NELSON R，KLEINROCK L.Spatial TDMA：A collisionfree multihop channel access protocol［J］.Communications，IEEE Transactions on，1985，33（9）：934-944.

［6］XIANG C S，LIG，LIQ X，et al.Energy efficient cross layer STDMA design in solar-powered wireless mesh network［J］.Applied Mechanics and Materials，2013，321：2849-2854.

［7］安丰彩，吴华.定向天线配置Ad Hoc网络的MAC协议研究［J］.大连海事大学学报：自然科学版，2005，31（3）：90-93.

［8］范菁.异构无线传感器网络跨层MAC协议研究现状［J］.云南民族大学学报：自然科学版，2011，20（5）：381-387.

［9］KWON Y，FANG Y，LATCHMAN H.A novel MAC protocol with fast collision resolution for wireless LANs［C］／／INFOCOM 2003，Twenty-Second Annual Joint Conference of the IEEE Computer and Communications.IEEE Societies.IEEE，2003（2）：853-862.

（责任编辑 庄红林）

An optimization algorithm based on reorganizing TDMA′s time slot in WSN

LI Feng1，FAN Jing1，HUANG Dao2
（1.Key Laboratory of Wireless Sensor Networks in Universities of Yunnan Province，Yunnan Minzu University，Kunming 650500，China；2.School of Electric and Information，Yunnan Minzu University，Kunming 650500，China）

The node′s time slot assignment in WSN is very important because it affects the entire network′s energy consumption and delay.STDMA can help avoid data collisions and reduce the energy loss to some extent，but each node′s time slots are both fixed and discrete，resulting in frequent node′s start and a lot of energy loss.On the basis of STDMA，this researchhas proposed OTT-TDMA algorithm to reschedule slots at the MAC layer，reducing the number of the node′s startand trying to schedule the node′s sending slotsafter its receiving slots.Simulation results show that the proposed algorithm has better performance on delay and energy consumption than STDMA.

wireless sensor networks；time slots reschedule；delay；MAC；energy consumption

TP393

A

1672-8513（2014）06-0396-04

2014-04-11.

国家自然科学基金（60963026，61163061）；云南省应用基础科学研究计划项目（2011FZ174）.

李峰（1988-），男，硕士研究生.主要研究方向：无线传感器网络.

范菁（1976-），女，博士研究生，教授，硕士生导师.主要研究方向：无线传感器网络、智能计算与环境监测.