基于无线传感器网络汇聚传输实时性的分布式调度算法.doc

第4期柯欣等：基于无线传感器网络汇聚传输实时性的分布式调度算法51基于无线传感器网络汇聚传输实时性的分布式调度算法柯欣1,2，孙利民1,2，吴志美1,2（1. 中国科学院 软件研究所，北京 100080；2. 中国科学院 研究生院，北京 100049）摘 要：在无线传感器网络多种应用中，各节点需要在短时间内将采集的数据传输至汇聚节点，从而形成多对一的汇聚传输。针对网络汇聚传输的实时性，提出了一种分布式的节点传输调度算法。各节点只需要根据一跳范围内的邻居信息进行传输调度。仿真和分析表明该算法可以有效避免数据碰撞，并使得完成一次全网数据收集所需要的时隙数基本在网络节点总数的1.6到1.8倍左右，比目前其他调度算法在实时性和复杂度方面更具有优势。关键词：无线传感器网络；汇聚传输；调度；时分复用中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2007)04-0044-07Distributed scheduling for real-time convergecast in wireless sensor networksKE Xin1,2, SUN Li-min1,2, WU Zhi-mei1,2(1. Institute of Software, Chinese Academy of Science, Beijing 100080, China;2. Graduate University of Chinese Academy of Sciences, Beijing 100049, China)Abstract: In some applications of wireless sensor networks, data packets generated by every node have to reach the sink node in short time. It resulted in a many-to-one communication paradigm referred to as convergecast. For the real-time of convergecast, a distributed scheduling algorithm was proposed. According to the algorithm, every node was scheduled by itself with information of one-hop range neighbor nodes. Some simulation and analysis prove that the algorithm can avoid data collisions, and the total number of timeslots needed to complete the convergecast once was around 1.6N to 1.8N, where N represents the number of nodes in the network.Key words: wireless sensor networks; convergecast; scheduling; TDMA1 引言收稿日期：2006-12-05；修回日期：2007-03-25基金项目：国家自然科学基金资助项目(60673178)；国家重点基础研究发展计划(“973”计划)基金资助项目(2006CB303007)；国家高技术研究发展计划(“863”计划)基金资助项目(2006AA01Z218)Foundation Items: The National Natural Science Foundation of China(60673178); The National Basic Resarch Program of China (973 Program) (2006CB303007); The National High Technology Rersearch and Development Program of China (863 Program) (2006AA01Z218)在无线传感器网络(WSN, wireless sensor networks)13多种应用场景中，各传感器节点需要在短时间内将采集数据传输至汇聚节点，例如网络状态监测应用中节点对自身的剩余能量扫描、火灾现场探测应用中节点采集温度汇报4等。由于无线传感器网络往往只有一个汇聚节点，因此在上述场景中网络数据传输呈现出一种“多对一”的汇聚传输。在汇聚传输过程中，无线数据碰撞问题尤为明显。现有的基于竞争的通信协议，如CSMA等，其所引入的退避重传机制以及错误阻塞现象(false blocking)5无法保证数据传输的实时性。而目前大部分基于时分复用（TDMA）的无线传感器网络通信调度协议则主要从避免数据碰撞以及提高能量效率的角度出发，对数据传输的实时性考虑较少。本文针对无线传感器网络汇聚传输的实时性进行了探讨，考虑在每个节点都有一个数据需要汇报的情况下，如何尽可能的减少全网数据收集的传输时间，并提出了一个基于时分复用的分布式调度算法。通过该算法可以有效的避免数据碰撞，并使得完成一次全网数据收集所需要的时隙数基本在网络节点数目的1.6倍到1.8倍左右。2 相关工作通过调度不仅可以有效的避免数据碰撞并且可以使节点在不需要工作时进入休眠状态，从而节省能量消耗，因此调度问题一直是无线传感器网络研究的热点。但目前大部分的调度研究610主要是针对调度算法本身和能量效率2个方面，而忽略了数据传输实时性的要求。例如文献8在进行调度分配时，为了避免数据碰撞采用RTS/CTS机制让节点去竞争占用可分配的传输时隙，因此很难保证数据的实时性；再如文献10提出的DCS调度算法，虽然可以有效地提高能量使用效率，但其父节点必须在获得所有子节点的数据后才能进行传输的规定不仅影响了传输的时间效率而且也加重了节点存储空间的负担。文献4在假设已知每个数据传输延时上限的情况下，提出了一种集中式的传输调度策略。网络中所有数据的每一跳传输时间都要由汇聚节点集中分配，从而尽量满足传输延时的要求。这种集中式方法需要汇聚节点掌握网络全局信息，在网络规模较大时计算复杂度很高。文献11从理论上证明了对于节点数目为N的网络，通过调度最多只需要3N个时隙就能完成一次全网数据的汇聚传输，并提出了相应的调度算法。该算法虽然由各个节点自主决定传输时隙的分配，但是每个节点需要掌握网络拓扑中分支总数、各分支长度、节点与各分支相互间的传输干扰关系等多种信息，在计算复杂度上已经接近于集中式调度。3 调度算法3.1 系统模型与其他基于TDMA的调度算法相同，本文也假设无线传感器网络各节点能够维持时间同步。另外假设各节点的数据长度相等，每个时隙的长度恰可以保证节点完整的接收或发送一个数据，并且在每一轮的汇聚传输中各节点只有一个数据需要发送。网络中各节点通过惟一的ID标识，且通信范围相等。另外假设各节点在进行传输调度之前已知自己距离汇聚节点的跳数以及一跳通信范围内各邻居节点ID和跳数。此假设可以通过如下方法实现，汇聚节点广播一个包含自身ID和跳数的分组，其他节点第一次接收到该类型的分组后，先等待一定的时间，然后根据这段时间内所接收的所有该类型分组来确定自身的跳数，再生成同样的分组广播出去。为了避免分组广播的数据碰撞，各节点等待时间可以与节点ID成正比。3.2 算法模型在无线传感器网络中，各节点除了发送自身数据外，还需要负责向汇聚节点转发其他节点的数据，跳数越少的节点转发的任务越重，并且上层节点的传输时隙安排将直接影响到下层节点的调度方案。因此采用“由上至下”的调度分配策略，即上一跳节点先确定调度方案后将方案广播至下一跳节点，使下一跳节点据此进行调度分配。为了便于描述，将距离汇聚节点跳数为n的节点称为n跳节点，则该调度算法可以分为一跳节点调度分配、全网调度分配和周期长度调整3个过程。3.2.1 一跳节点调度分配无论无线传感器网络节点规模多大，汇聚节点在一个时隙内只能接收一个数据分组。因此为了提高全网数据的传输效率，需要尽可能的使汇聚节点连续不停的接收数据。而汇聚节点所接收的数据都是由一跳节点发送或者转发的，因此一跳节点收发时隙调度将成为影响全网数据汇聚传输效率的关键。每个节点自身需要发送的数据只有一个，进行转发的数据则需要通过一个时隙的接收获得，因此任何节点都无法持续不断的发送数据。为了尽可能的使汇聚节点连续接收，就需要各一跳节点依次进行数据发送。为了便于计算，先假设下层节点总是有数据需要各一跳节点进行转发，然后寻找一跳节点调度的最短时隙周期和调度方案，使得各一跳节点在此周期内都能够完成一次数据的发送和接收。定义1 定义Cs表示一跳节点调度的最短周期时隙数，并定义节点在一个时隙内所处的3种状态分别为1)传输状态（T）：节点在此时隙内进行数据发送；2）接收状态（R）：节点在此时隙内进行数据接收；3）空闲状态（I）：节点在此时隙内即不进行数据发送又不进行数据接收。显然在对于任意一个时隙，只能有一个一跳节点为传输状态，否则将发生数据碰撞，从而使得汇聚节点无法正确接收数据。同理规定对于任意一个时隙，最多只能有一个一跳节点进入接收状态。这是为了避免下层节点汇报时产生数据碰撞。如图 1所示（图中节点0为汇聚节点，其余为传感器节点，两点间连线表示互为邻居节点，后文相同），如果节点1和节点2在同一时隙分别接收节点3和节点4的汇报，则会发生数据碰撞，使得节点2无法正确接收数据。图1 网络示意图定理1 多跳网络中，一跳节点最短调度周期长度Cs最少为3。证明 考虑简单的线性网络，如图2所示，一跳节点只有节点1。由于节点1在一个周期内要分别进行一次数据的收发，因此Cs2。同样，为了使节点1每个周期都能接收一个数据，节点2在每个周期也需要分别进行一次数据的收发。但由于无线通信的隐终端问题，节点2在接收数据时节点1不能进行数据发送，显然此时节点1也无法接收数据。因此节点1在一个周期内至少要有一个时隙处于空闲状态，从而Cs3。图2 线性网络及调度方案定义2 如果2个节点不为邻居节点，则称这2个节点为一个“非邻对”。如果3个节点彼此互不为邻居节点，则称这3个节点为一个“非邻组”。节点没有交集的非邻对/组，称之为“不相交非邻对/组”。由定义2可知，对于任意n个（n4）互不为邻居的节点都可以分解为若干不相交非邻对/组。并且对于任意一组节点和节点间相邻关系，都可以得到若干不相交非邻对和非邻组的组合，将每一种组合称之为该节点集的一个不相交非邻集。定义3 给定一组节点和节点间相邻关系，使其不相交非邻集的节点数最大的非邻组和非邻对的组合定义为“最大不相交非邻集”，将该组合的节点数定义为“最大不相交非邻节点数”。例如图3所示，该网络中最大不相交非邻集由非邻对(节点1、2)和非邻组（节点3、4、5）组成，其最大不相交非邻节点数为5。图3 网络示意图定理2 多跳网络中，对于n个一跳节点，设其最大不相交非邻节点数为m，则该n个一跳节点最短调度周期长度Cs=max(3,2n-m)。证明 由于汇聚节点每个时隙只能接收一个数据，因此调度周期至少需要有n个时隙用于n个一跳节点的数据发送。另外，n个一跳节点还需要有n个时隙用于各自的数据接收。但对于组成非邻对/组的节点，可以按照图4的方式利用其他节点的发送时隙进行数据接收。因此可以将m个接收时隙与发送时隙合并。所以只要通过n+n-m=2n-m个时隙就能够使得所有一跳节点各完成一次收发。另外根据定理1，在多跳网络中一跳节点调度周期的时隙长度最少为3，即得到Cs=max(3,2n-m)。图4 非邻对、非邻组调度分配方案定理2不仅给出了计算最短调度周期的表达式，而且定理2的证明也明确了一跳节点调度的分配方案。例如，图3所示网络中的6个节点可以按照表1中所示的调度方案，在7个时隙内各自完成一次数据的收发，并且在同一时隙内最多分别只有一个节点处于发送或接收状态。表1图3节点调度分配方案时隙节点1节点2节点3节点4节点5节点61TRIIII2RTIIII3IITIRI4IIRTII5IIIRTI6IIIIIT7IIIIIR由于在实际应用中，汇聚节点往往在能量、运算和存储能力等方面都要优于其他传感器节点，因此一跳节点的调度分配可以由汇聚节点统一进行，分配好后再将结果广播给一跳节点。各一跳节点只需要将自身节点ID以及相邻节点中的一跳节点ID提供给汇聚节点即可。调度分配的关键在于如何获得一跳节点中的最大不相交非邻集和最大不相交非邻节点数。在此给出一种寻找一跳节点最大不相交非邻集的工程算法，其伪代码如图5所示。图5 寻找最大不相交非邻集算法3.2.2 全网调度分配全网调度分配过程主要是针对网络一跳节点以外的各跳节点进行。对于多跳传输的网络，上一跳节点的接收时隙即为下一跳节点的发送时隙。因此一跳节点调度分配后，两跳节点在每个周期中可发送的时隙也已经确定，未定的只不过是由哪些节点来进行发送。同理，一旦两跳节点的接收时隙确定，则三跳节点的可发送时隙也就确定了。因此，按照“由上至下”的顺序对各跳数层节点进行调度，即上层节点将自己的调度结果广播给下层节点，由下层节点按照某种规则进行传输时隙的分配。网络中除叶节点外的各跳节点都需要承担数据转发的任务，即不仅需要将数据发送给上一跳节点，还需要从下一跳节点接收数据。经过一跳节点调度分配，各一跳节点以Cs个时隙为一个周期，在每个周期内可互不干扰的各完成一次数据收发。由于各跳节点的数据都要由一跳节点转发给汇聚节点，因此各跳节点调度过程也以Cs个时隙的周期为单位，并规定在每个周期内各节点或者不进行数据通信，或者完成数据收发各一次（叶节点除外）。同时各节点进行发送接收时隙分配时，还应该避免发生数据碰撞。由于是逐层进行调度，因此各节点需要保证自身的发送和接收时隙不会干扰本层及上层节点的传输。将数据碰撞的情形概括为以下3种：上层发送干扰下层接收。由于在汇聚传输中数据都是由下层发送至上层，因此如果节点在接收数据时其上层邻居节点发送数据则将发生数据碰撞。下层发送干扰上层接收。节点接收数据时，如果其不止一个下层邻居节点进行数据发送则产生数据碰撞。同层发送、接收相互干扰。同样由于数据总是由下至上的传输，因此节点进行数据接收时其同层邻居节点都不能进行数据发送。针对上述3种数据碰撞情形，定义如下节点传输调度分配的规则。1) 节点必须在获得所有上一跳邻居节点的调度结果后再进行自身调度分配。2) 节点必须在其所有比自己节点ID小的同跳数邻居节点完成调度分配后再进行自身调度分配。3) 调度分配时节点在所有可能的发送时隙中选取最早的时隙进行数据发送。4) 同周期内，子节点接收、发送时隙的间隔与父节点相同。5) 节点确定自己在一个周期中接收发送时隙的分配后，将调度结果进行广播；其所选择的父节点接收到子节点的调度结果后，也需要广播一个应答消息。规则1)、2)是节点启动调度分配的条件，其中规则1)是为了保证节点能够在全面掌握上一跳节点信息基础上进行调度，规则2)则是为了避免多个节点同时进行调度分配从而可能产生的数据碰撞。规则3)是出于对数据传输实时性的考虑。规则4)、5)则是为了避免上述的3种数据碰撞。定理3 按照规则1)、4)进行全网节点调度可以避免数据碰撞情形的出现。证明 定义同周期内节点接收、发送时隙间隔k =节点接收时隙数节点发送时隙数。如表 1中节点1的接收发送间隔为1，节点2的间隔为1。因此如果在第p个周期中，节点ni的父节点接收时隙为j，(p1)CsjpCs。则ni的在该周期的发送时隙为j，接收时隙为q。(1)图6 节点i第p周期调度分配算法上层节点发送对下层节点接收的干扰可以分为父节点干扰和非父节点干扰2种。规则1)保证节点ni在全面掌握上一跳节点信息基础上进行调度，因此可以避免非父节点的干扰。而如果按照规则4)确定收发时隙，则父节点干扰只有当下式成立时才会出现。(2)根据图4的时隙分配方法，在同一周期内节点的接收时隙数减去发送时隙数结果只可能为1、1和2，因此间隔k对Cs取模后也只可能为1、1和2。由于Cs3，因此只有k取值2且Cs=2nm=4时式(2)才能成立。n和m都为自然数，且mn，则只有n=3、m=2和n=4、m=4两种情况可满足2nm=4。但此时k都不等于2，因此也不会出现父节点干扰。根据定理3，规则1)、4)避免了数据碰撞情形的出现。而规则5)则针对数据碰撞情形和。由于规则2)保证各节点不会同时进行调度分配，因此完成调度的节点广播其调度结果可以使其他未进行调度的同层邻居节点分配收发时隙时避免出现数据碰撞情形；而父节点广播对子节点调度结果的应答消息，可以使父节点其他未进行调度的下一跳邻居节点得知该节点接收时隙已被占用，从而避免出现数据碰撞情形。按照上述规则，图 6给出了节点i在第p周期的调度算法的伪代码，其中第13和18步所用到的节点i在第p周期传输时隙分配策略如图 7所示。该调度算法可由汇聚节点周期性的触发一跳节点广播自身调度结果来进行，第i个调度周期针对第i个传输周期进行分配，直到汇聚节点在一个调度周期内没有收到任何一个一跳节点的接收时隙占用消息（这表明在下一个传输周期各一跳节点都没有数据需要发送或转发给汇聚节点）。图3 节点i第p周期传输时隙分配算法 另外，图6中第12步的“接收上层调度结果定时器”是为了满足规则1)，其超时时间可以根据网络节点规模事先确定。而第17步的“接收同层调度结果定时器”是为了满足规则2)。为了避免调度分配过程中的数据碰撞，该定时器的超时时间可以与各节点ID成正比。例如假设网络中节点完整发送一个数据分组所需时间为t，再考虑到节点调度广播和父节点应答的过程，则超时时间可以等于3t节点ID。3.2.3 周期长度调整在一跳节点调度分配过程中，假设下层节点总是有数据需要各一跳节点进行转发，但在实际应用中并非如此。如图8所示网络，Cs=220=4。但由于节点1在2个传输周期后就不再进行数据传输，因此节点2的后3个传输周期的长度可以减少为3个时隙，从而进一步调高汇聚传输的实时性。图8 网络示意图针对这种情况，需要汇聚节点在全网调度分配过程中记录各一跳节点在各传输周期是否进行了数据发送，以及所发送数据源节点跳数（这些信息可以在一跳节点广播的传输时隙占用消息中获得）。然后当全网调度分配完成后，汇聚节点根据记录统一的对各传输周期的时隙长度进行调整，并将调整结果广播至各下层节点，从而遵照执行。4 仿真分析为了对调度算法进行评估，通过glomosim模拟器进行了仿真验证，并与DCS10和文献11的算法进行了比较。模拟网络部署区域面积为，其中，R为各节点通信半径。节点分布为随机均匀分布，即先将网络部署区域均匀的划分为N个面积相等的方格（N为网络节点个数），然后在每个方格中随机放置一个节点。分别考虑网络中有36、49、64、81和100个节点的情况，每种情况利用不同的随机数各模拟10次，统计调度后完成一次全网数据收集所需要的平均时隙数。通过模拟发现，算法不仅可以保证每个节点的数据都能传输至汇聚节点，而且所需的传输时隙要明显少于DCS算法，具体结果如表2所示。表2仿真模拟结果网络节点数本文算法平均传输时隙数DCS平均传输时隙数3661.387.84981.8112.064109.7175.481139.4240.5100180.5252.1如表2所示，在各种网络规模下，本文的调度算法可以比DCS调度算法节省30%左右的传输时隙。如果假设网络节点数为N，利用本文的调度算法完成一次全网汇聚传输需要的总时隙数基本在1.6N到1.8N左右。这一结果虽然略高于文献11中的1.5N，但文献11的调度算法要求各节点掌握网络拓扑中分支总数、各分支长度、节点与各分支相互间的传输干扰关系等多种信息才能进行调度分配，而本文的调度算法只需要节点了解一跳节点的ID和跳数即可。因此在算法复杂度以及对无线传感器网络分布式特性的适应程度上，本文算法比文献11更具有优势。5 结束语本文针对无线传感器网络汇聚传输的实时性，提出了一个基于TDMA的分布式节点调度算法。通过该算法进行一次全网数据收集基本可以在1.6N到1.8N个时隙之间完成，并且能够有效避免各节点传输的数据碰撞。另外该算法调度时只需要各节点掌握一跳相邻节点信息，而在传输过程中节点最多只要缓存2个数据分组，因此非常适用于无线传感器网络分布式、节点存储空间有限的特点。不过本文的算法对网络局部区域突发性信息传输的实时性支持不够，也无法为多种不同级别的数据传输提供不同的实时性保证。这也将是下一步工作的重点。参考文献：1AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. Wireless sensor networks: a surveyJ. Computer Networks, 2002, 38(4): 393-422.2任丰原, 黄海宁,林闯.无线传感器网络J. 软件学报, 2003,14(7):1282-1291.REN F Y, HUANG H N, LIN C. Wireless sensor networksJ. Journal of Software, 2003,14(7):1282-1291.3孙利民,李建中,陈渝等. 无线传感器网络M. 北京:清华大学出版社,2005.SUN L M, LI J Z, CHEN Y, et al. Wireless Sensor NetworksM. Beijing: Tsinghua University Press, 2005.4HUANLI P S, RAMAMRITHAM K. Scheduling messages with deadlines in multi-hop real-time sensor networksA. Proc IEEE Real Time and Embedded Technology and Applications SymposiumC. San Francisco, CA, 2005. 415-425.5RAY S, CARRUTHERS J B, STAROBINSKI D. RTS/CTS-induced congestion in ad hoc wireless LANsA. Proc Wireless Communications and Networking Conference (WCNC)C. 2003, 3:1516-1521.6RHEE I, WARRIER A, XU L. Randomized Dining Philosophers to TDMA Scheduling in Wireless Sensor NetworksR. Computer Science Department, North Carolina State University, Raleigh, NC, 2004.7HOHLT B, DOHERTY L, BREWER E. Flexible power scheduling for sensor networksA. Proc the Third International Symposium on Information Processing in Sensor NetworksC. ACM Press, 2004, 205-2