无线传感器网络中多移动sink的选择策略.doc

第11期程龙等：无线传感器网络中多移动sink的选择策略19无线传感器网络中多移动sink的选择策略程龙1，陈灿峰2，马建2（1北京邮电大学 网络与交换技术国家重点实验室，北京 100876；2诺基亚（中国）研究中心，北京 100176）摘 要：针对移动终端作为无线传感器网络中的移动sink情况下，提出了具有多个移动sink的稀疏无线传感器网络体系结构M2S2N。考虑到移动终端广泛存在的特性，为了有效地收集传感数据，提出了无线传感器网络中对移动sink的选择策略，并在此基础上提出了一种适合于M2S2N的基于功率控制的机会传输调度算法。仿真和分析表明选择最佳的移动sink可以有效地提高传感器节点的能量有效性和数据传输成功率。关键词：无线传感器网络；移动sink；选择策略；传输调度中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2008)11-0012-07Selection scheme of mobile sinks in wireless sensor networksCHENG Long 1, CHEN Can-feng 2, MA Jian 2(1. State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China；2. Nokia Research Center, Beijing 100176, China)Abstract: Using mobile devices as sinks for efficient data collection in wireless sensor network (WSN), the architecture of multiple mobile sinks sparse wireless sensor network (M2S2N) was introduced. By taking the ubiquitous nature of mobile devices into consideration, different selection schemes of mobile sinks in M2S2N were compared, and an opportunistic transmission scheduling algorithm (OTSA) for M2S2N was further proposed. Simulation results indicate that the proposed sink selection scheme in OTSA-M2S2N is effective and can significantly improve the performance such as energy efficiency and successful transmission ratio.Key words: wireless sensor networks; mobile sink; selection scheme; transmission scheduling1 引言收稿日期：2008-06-24；修回日期：2008-10-26基金项目：国家自然科学基金资助项目（60673178, 60873241）；国家高技术研究发展计划（“863”计划）基金资助项目（2008AA01Z217）Foundation Items: The National Natural Science Foundation of China (60673178, 60873241); The National High Technology Research and Development Program of China (863 Program) (2008AA01Z217)尽管无线传感器网络起源于军事领域的应用，近年来，无线传感器网络在民用领域的应用研究也受到了越来越多的关注。其在环境监测、医疗护理、建筑物状态监控、交通监控等领域具有广泛的应用前景1,2。随着传感器成本的持续降低，可以预测不久的将来，人类会处在一个传感器无处不在的世界。因而如何有效地收集无线传感器网络产生的大量数据成为值得研究的问题之一。文献35提出了利用移动sink收集传感数据。移动sink的引入可以平衡传感器网络中各节点的能量消耗，有效地避免“路由空洞”问题，因而提高了整个网络的吞吐量，延长了网络的生存时间。随着通信技术的进步，移动终端也将进入几乎随时随地可以接入互联网的时代。通常移动终端具有以下4个特性：1）具有广泛存在的特性；2）与传感器网络之间具有间断的连通性；3）有空闲的通信与计算资源可以利用； 4）可充电、相对充足的电量。因此，关于如何利用移动终端充当无线传感器网络中的移动sink并有效地收集传感数据的研究引起了研究人员越来越多的重视6,7。利用移动终端收集传感数据同时也体现了Web 2.0的思想，众多的移动用户既是传感数据的传播渠道，同时也是传感数据的受众8。系统会随着越来越多移动用户的参与而积累大量的传感数据，进而为人们提供有价值的信息。本文主要研究当移动终端作为无线传感器网络中的移动sink时，对数据传输调度等方面带来的影响。由于移动终端具有广泛存在的特性，在文献9, 10的基础上，本文提出了具有多个移动sink的稀疏无线传感器网络（M2S2N, multiple mobile sink sparse wireless sensor network）体系结构，与文献9, 10中的网络体系结类似，M2S2N中的传感器节点被稀疏地部署在人们生活的环境中，数据传输仅限于单跳，这样就避免了由于多跳路由所带来的各种能量开销，大大延长了节点的生命周期。此外，M2S2N的部署非常简单并具有很高的可扩展性，使M2S2N在环境监测、建筑物状态监控、交通监控等民用领域具有广泛的应用价值。例如，在交通监控中的应用，如图1所示。传感器节点稀疏地部署在公路中间，当利用来往车辆中的移动终端作为移动sink收集传感数据，有理由推断当节点需要传输数据时，周围会存在多个处于不同运动状态（速度、方向等）的移动sink。 图1 M2S2N在交通监控中的应用M2S2N较文献9, 10的区别在于，M2S2N中的传感器节点周围往往会存在多个移动sink，而以往的研究都是考虑一个移动sink。对于能量受限的传感器节点来说，在数据传输过程中如何有效地节省能量以延长节点的生存时间是传感器网络研究的首要问题。本文的主要贡献在于：针对M2S2N网络模型，提出了无线传感器网络中对移动sink的选择策略，并在此基础上提出了一种适合于M2S2N的基于功率控制的机会传输调度算法（OTSA-M2S2N）。OTSA-M2S2N在确保传感数据正确传输的前提下，以节省能量优先为原则，选择最为合适的移动sink。2 相关工作M2S2N的网络体系结构是在文献9, 10的基础上，结合移动终端广泛存在的特性而提出的。文献9, 10指出基于单跳通信的稀疏无线传感器网络非常适合应用于环境监测、交通监控等领域。与多跳无线传感器网络比较，有以下优势：1）基于近距离的单跳通信，可以最大限度节省传感器节点能量消耗；2）没有路由所带来的各种开销；3）健壮性；4）可扩展性；5）部署简单。但同时也有不足：1）具有一定延迟，因此不适合对实时性要求较高的应用；2）尽力而为的传输，传感器节点周围的移动sink数量及其运动状态影响数据传输的有效性。文献9提出了一种适合于稀疏无线传感器网络的传输调度算法 （TSA-MMSN）。在传输过程中，对传感器节点功率控制，随着距离sink的远近调整天线的发射功率，在保证成功传输数据的前提下，最大限度节省传感器节点的能量消耗。TSA-MMSN分析了成功传输数据与节省传感器节点能量消耗之间的约束关系，利用效用函数提出了一种能量有效的传输调度策略。文献10提出了MULE网络体系结构，MULE是一种可容忍延迟（DTN）的机会通信网络。利用MULE收集附近的传感数据并保存在其存储介质中，之后由MULE将数据上传至目的地，因此MULE具有很大的延迟。但随着通信技术的进步，移动终端将进入几乎随时随地可以接入互联网的时代，这样利用移动终端收集传感数据将会大大缩短数据传输的时延。文献6, 7等研究移动终端在无线传感器网络中的应用，利用前面提到的移动终端所具有的特性来构建移动无线传感器网络。但大部分研究只是考虑如何利用移动终端的移动特性，而没有提到本文所关注的问题，即如何充分利用移动终端广泛存在的特性。事实上，本文所讨论的问题可以抽象为一个传感器节点与多个移动sink之间的传输调度问题，并且选择最佳的移动sink以有效地提高传感器节点的能量有效性和数据传输成功率。3 移动sink选择策略3.1 假设与问题描述在分析移动sink选择策略之前，做出以下合理的假设：1）移动sink可以获得自己当前的运动状态（速度、方向等）；2）传感器节点是静止的，具有有限的通信半径，并且储存有传感数据等待移动sink收集；3）传感器节点以DT（s）为一个工作周期，周期性地打开收发器以节省能量消耗。在DT（s）内，收发器的打开时间最长为BT（s）。如果没有发现移动sink，或在数据传输过程中所选择的移动sink运动状态发生变化不再适合传输数据，则进入休眠状态；4）通过移动sink广播位置信息以及采用测距技术，传感器节点可以知道自己的位置信息；5）移动sink与传感器节点之间通过握手消息交换当前的运动状态及等待传输的数据包数量等信息；6）在数据传输过程中，移动sink正确收到数据包后会反馈确认ACK报文，在ACK中包含有当前移动sink与传感器节点的距离等信息；7）数据传输过程中采用功率控制技术。图2 传感器节点通信范围内存在多个移动sink关于移动sink的选择问题可以描述为：在一个工作周期内当有数据需要传输时，传感器节点广播一个查询请求报文（scanning）以发现周围存在的可以利用的移动sink（当移动终端作为移动sink时，周围可能会存在多于一个的移动sink），移动sink收到此请求后返回一个携带有其当前运动状态的响应报文。因此传感器节点可以知道周围所存在的移动sink数量及其运动状态。由于各移动sink所处的运动状态不同（并非距离越近越好），据此传感器节点可以选择一个最佳的移动sink进行数据传输。以上过程可以建模成以传感器节点为圆心，其通信范围为半径的圆。当有数据需要传输时，传感器节点对恰好位于此圆内的移动sink做出选择。如图2所示, ti表示第i个数据包传输时刻；表示初始时刻第i个sink所处位置；表示根据初始时刻第i个sink的运动状态，预测其移出传感器节点通信范围时所处位置。表示第i个sink的运动矢量；表示第i个sink从初始时刻起在其通信半径范围内的停留时间。将传输一个数据包及ACK所需的时间作为一个时间单位其中，、分别表示传感数据及ACK报文的大小；R表示数据传输速率。U表示传感器节点所发现的移动sink集合。 初始时刻传感器节点有Ksensor(t0)个数据包需要传输，其所需要的传输时间为Tsensor(t0)。接下来，将比较M2S2N中可能的几种移动sink选择策略。3.2 随机选择（RS）在所有发现的移动sink中，传感器节点随机地选择一个移动sink进行数据传输。这里仅作为与其他选择策略比较的对象。3.3 最长时间优先（LDFS）LDFS选择在其通信范围内具有最长停留时间的移动sink进行数据传输。由于移动sink的运动状态是在t0时刻做出预测，还可能在数据传输过程中改变，LDFS仅最大限度保证了数据传输的可靠性。ldfs表示LDFS选择的sink序号，以图2为例，LDFS会选择sink 1进行数据传输。3.4 最近距离优先（PFS）PFS选择在t0时刻距离最近的移动sink进行数据传输。当sink处于静止状态，PFS能保证以最小的发射功率进行数据传输，然而对于移动sink情况并不是这样，是否是最佳选择还取决其移动速度、方向等因素。pfs表示PFS选择的sink序号，以图2为例，PFS会选择sink 2进行数据传输。3.5 平均距离最短优先（SADFS）V表示传感器节点所发现的移动sink集合中，在传感器节点通信范围内的停留时间大于Tsensor(t0)的sink，即SADFS根据初始时刻各移动sink的运动状态，在集合V中选择具有最短平均距离的移动sink，同时确定数据传输的最佳时刻。这里“平均距离”指在数据传输过程中传感器节点与移动sink之间的平均距离。如图3所示，SADFS可以分为Back-off和无Back-off两种情况。主要取决于t0时刻传感器节点需要的数据传输时间Tsensor(t0)。Ti_near表示在t0时刻起第i个sink移动到距离传感器节点最近位置Li_near所需要的时间。当时，传感器节点可以选择Back-off，确定最佳时刻再进行数据传输。当时，传感器节点数据传输的(a) Back-off (b) 无Back-off图3 平均距离最短优先选择策略中的两种情况最佳时刻就是初始时刻t0。从某种程度上来说，传感器节点选择Back-off是有风险的，因为移动sink的运动状态可能会有所改变。因此引入了效用函数的概念以确定SADFS中数据传输的最佳时刻。将第i个移动sink 在 tj时刻所处的状态表示为，tj+1时刻所处的状态表示为。只与的状态有关而与tj时刻之前的状态无关，因此第i个移动sink 在各个时刻所处的状态可以认为是一个Markov过程。为了简化模型，当移动sink 的状态变化超过一定范围，才认为该状态有变化，p表示运动状态（速度、方向）改变的概率；e(l)表示引入Back-off传感器节点可以节省的能量；Tbackoff表示传感器节点当前工作周期内Back-off 的时间上限；是加权系数，表示在Tbackoff时间范围内实际的Back-off 时间与Tbackoff的比值。在Tbackoff时间内可以传输个数据包。因此效用函数可以表示为式(9)由两部分组成，是引入Back-off所带来的增益，是关于的增函数，表示由于移动sink运动状态改变所导致的损失。的取值与M2S2N部署的应用场景有关。文献11也指出了在实际场景中人的移动轨迹往往取决于所处环境。例如图1中M2S2N应用于交通监控所示，通常移动sink会沿道路直线运动，运动速度短时间内也不会有很大的变化。因此当时，这种情况下传感器节点可以选择退避Tbackoff时间，即的值取1。4 机会传输调度算法在上一节对M2S2N中移动sink选择策略分析的基础上，提出了一种适合于M2S2N的基于功率控制的机会传输调度算法，算法描述如图4所示。OTSA-M2S2N在节省传感器节点的能量消耗的同时，可以最大程度地提高网络数据传输成功率。在每个工作周期的初始时刻t0，传感器节点首先选择合适的sink，如果所发现的移动sink中有在其停留时间内能够将传感器节点的数据全部传输完毕，即，则采用平均距离最短优先策略。否则，当时，采用最长时间优先策略，即尽最大努力传输数据以提高数据传输成功率。将OTSA-M2S2N中的选择策略称为OTSAS（OTSA selection）。如果没有发现sink，则进入休眠状态直到下一个工作周期。经过对移动sink的选择，传感器节点与该sink建立连接，进入数据传输阶段。在数据传输过程中，随着移动sink与传感器节点距离的不同，根据Friis自由空间功率公式12计算天线的最小发射功率，传感器节点不断调整发射功率以达到节省能量的目的。图4 机会传输调度算法 (OTSA-M2S2N)其中，Rt为接收节点的接收门限；Gt、Gr分别为发射、接收天线增益；为波长；d 为发射端与接收端的距离；L为损耗因子，L1。5 仿真结果与分析为了具体分析移动sink的选择策略对M2S2N所产生的影响，在NS-2中对移动sink的不同选择策略进行了仿真实验。仿真场景如图1所示，M2S2N部署在公路中间，因此假设移动sink在短时间内保持直线运动，移动速度在小范围内不会有很大的变化，传感器节点选择退避Tbackoff时间。在M2S2N中对移动sink的选择主要会影响到传感器节点的能量消耗和单位周期内成功传输数据包的数量。因此，对OTSA-M2S2N中的移动sink选择策略OTSAS与PFS、RS和LDFS进行比较，将传感器节点的能量有效性和数据传输成功率作为主要衡量指标。定义1 能量有效性(energy efficiency)：为一个工作周期内传感器节点消耗的能量与成功传输的数据包数量的比值。定义2 数据传输成功率(successful transmission ratio)：为一个工作周期内传感器节点成功传输的数据包数量与缓存中待发送数据包数量的比值。5.1 参数设置传播模型设置为FreeSpace模型，MAC层协议采用IEEE 802.15.4。如表1所示，主要参数设置均参考802.15.4规范。(x, y)表示某个移动sink的坐标值，假设x在(r, r)内服从均匀分布，y在内服从均匀分布，移动sink的运动速度v在10, 25(m/s)内服从均匀分布。表1NS-2仿真实验中的参数设置参数单位值range (r)FdFbRmbitbitbit/s5020 000根据与移动sink距离的不同，传感器节点天线的发射功率设置为10个不同等级，分别为(11)5.2 仿真实验结果首先比较了随着传感器节点周围sink数量的变化，不同移动sink选择策略对M2S2N性能的影响。是仿真结果如图5、6所示，其中K表示一个工作周期内传感器节点缓存中待发送数据包的数量。从图5可以看出，当K较小时，LDFS的性能最差。这是由于在传感器节点通信范围内接触时间最长的sink往往距离传感器节点较远。而最近距离优先策略（PFS）选择最近的sink，由于K较小，数据传输在很短时间内完成，因而有较高的能量有效性。随机选择策略（RS）则介于两者之间。由于选择最佳的时机传输数据，OTSAS具有最高的能量有效性。图5 sink数量与传感器节点能量有效性关系（K=10）从图6可以看出，当K=50时，LDFS的性能仅次于OTSAS。这是由于传输完50个数据包需要较长时间，PFS和RS不仅能量有效性较低，而且还会出现在sink移动传感器节点通信范围前没有传完50个数据包的现象。同样，OTSAS具有最高的能量有效性。本文还比较了随着传感器节点内需要发送的数据包数量的变化，假设存在5个移动sink情况下，图6 sink数量与传感器节点能量有效性关系（K=50）不同移动sink选择策略对M2S2N性能的影响。仿真结果如图7和图8所示。从图7可以看出，随着待发送的数据包数量的增多，PFS、RS和OTSAS的能量有效性也会随之上升。这是由于数据包数量的增多，在传感器节点距离移动sink较远时也需要传输数据，因此传输一个数据包所消耗的平均能量会有所增加。值得注意的是图中LDFS的能量有效性反而随着数据包数量的增多而下降，并最终与OTSAS接近。这是由于当待发送数据包数量增加到一定程度时，OTSAS往往会与LDFS选择同一个sink。图7 传感器节点待发送数据包的数量与能量有效性关系图8显示了随着传感器节点待发送数据包数量的增加，各选择策略数据传输成功率均会降低。这是由于移动sink在传感器节点通信范围内的停留时间有限，实验结果表明OTSAS与LDFS能够最大程度地保证数据的成功传输(如图8所示，OTSAS与LDFS的数据传输成功率曲线重合)。在数据传输成功率方面，OTSAS与LDFS性能相同，但OTSAS在能量有效性方面要优于LDFS。图8 传感器节点待发送数据包的数量与数据传输成功率关系图5、图6与图7、图8的结果产生于不同实验中，由于sink的位置、运动速度均为随机产生，其实验数据会存在细微差别。仿真结果显示OTSA-M2S2N在节省传感器节点的能量消耗的同时，可以最大程度地提高数据传输成功率。6 结束语本文研究将移动终端应用于无线传感器网络中，利用移动终端充当无线传感器网络中的移动sink并有效地收集传感数据。考虑到移动终端广泛存在的特性，提出了具有多个移动sink的稀疏无线传感器网络体系结构M2S2N，仿真和分析表明M2S2N中有必要对移动sink进行选择以提高性能。选择最佳的移动sink可以有效地提高传感器节点的能量有效性和数据传输成功率。参考文献：1AKYILDIZ I F, SU W L, YOGESH S, et al. A survey on sensor networks J. IEEE Communications Magazine, 2002, 40(8): 102-114.2孙利民, 李建中, 陈渝等. 无线传感器网络M. 北京：清华大学出版社, 2005.SUN L M, LI J Z, CHEN Y, et al. Wireless Sensor Networks M. Beijing: Tsinghua University Press, 2005. 3GANDHAM S R, DAWANDE M, PRAKASH R, et al. Energy efficient schemes for wireless sensor networks with multiple mobile base stationsA. IEEE Global Telecommunications ConferenceC. San Francisco, USA, 2003.377-381.4EKICI E, GU Y, BOZDAG D. Mobility-based communication in wireless sensor networksJ. IEEE Communications Magazine, 2006, 44(7): 56-62.5SOMASUNDARA A , KANSAL A, JEA D, et al. Controllably mobile infrastructure for low energy embedded networksJ. IEEE Transactions on Mobile Computing, 2006 5(8):958-973.6WESTPHAL C. Little tom thumb went straight home: asymptotic behavior of a routing protocol in ad-hoc networks with a mobile access pointA. The 26th IEEE International Conference on Computer CommunicationsC. Alaska, USA, 2007. 1847-1856.7JAYARAMAN, PREM P, ZASLAVSKY, et al. Sensor data collection using heterogeneous mobile devicesA. IEEE International Conference on Pervasive ServicesC. Istanbul, Turkey, 2007. 161-164.8 KANSAL