原创 无线传感器网络时间同步与成簇算法

0引 言

融合了传感器技术、信息处理技术和网络通信技术的无线传感器网络(wireless sensor networks，WSNs)由分布在物理空间上大量传感器节点通过自组织的方式构建网络，节点通过集成各种微型传感器来感知环境或监测对象信息，协作地处理感知信息，并以自组织多跳无线通信方式将信息传送到用户，从而实现随时获取感兴趣区域信息。WSNs在军事、工业、农业、医疗及环境监测等领域有广泛的应用前景，在我国"国家中长期科学和技术发展规划纲要"重点领域中，"传感器网络和智能信息处理"被列为"信息产业"中七个主题之一。

时间同步是WSNs应用的重要组成部分，控制消息冲突、数据融合、节点定位等方面都要求节点间保持同步。在保持节点时间同步的基础上，获取节点的邻居信息，根据邻居信息，对全网节点进行自组织成簇，在簇内进行数据融合，减少网络的数据流量，以延长网络的寿命。 1相关研究工作

文献[1]通过动态选举簇头来平均网络节点能耗，其他节点根据簇头信号的强度来作为判断是否加入该簇的依据；文献[2]在文献[1]的基础上进行了改进，通过设立软、硬门限进一步降低了能耗，只有当节点感知数据或其增幅超过预先设定的阈值时，节点才发送数据；文献[3]提出了一种随机簇组织局部算法，并在此基础上，提出了建立层次化簇结构的思想；文献[4]提出的簇组织算法，使各簇作用域无重叠且大小基本相等，并且，在旧节点失效和新节点加入时，簇具有一定程度的自愈能力；文献[5]提出了一种基于时间触发的簇组织算法，仅当特定事件发生时，才启动簇组织过程，簇成员同簇头之间，允许多跳通信；文献[6]着重解决簇组织完毕后，相邻簇之间的连通和簇问路由建立问题，在成簇以后，簇头和簇头之间借助非簇头节点进行通信。

但是，上述的算法中没有考虑成簇消息发送过程中的冲突问题，簇头间借助中间节点通信将带来很多的交换消息，且问题过于复杂。本文在提出一种时间同步算法的基础上，利用时隙划分，有效地克服成簇消息传输过程中的冲突问题；再基于节点的度、节点的剩余能量等参数加权选取簇头。成簇以后，通过动态改变簇头节点的通信功率和通信频率，以实现簇头间一跳通信，且其他的节点不会串听簇头问的通信，有效降低节点的能耗。 2时间同步过程描述

同步机制采用C／S模式，由传感器网络中的Sink节点以多跳方式周期性地广播时间同步消息，所有节点在收到该同步消息后，充分考虑可能造成消息传输延时的原因，对消息中携带的时间进行纠正，然后，将纠正结果作为本地时间，同时记录收到消息的同步序列号，如果再次收到相同序列号的消息，则直接丢弃不做处理。

2.1 同步消息扩散过程中的偏移量

在WSNs中，将消息在节点间传递的过程分为如下6个部分：

1)发送节点构造一条消息所需要的时间，包括内核协议处理和缓冲时间等，设为tsend；
2)消息等待传输信道空闲所需时间，即从等待信道空闲到消息开始发送时的延迟，设为taccess；
3)发送节点按位(bit)发射消息需时间，该时间取决于消息长度和发射速率，设为ttrans；
4)消息在2个节点之间传输介质中的传播时间，设为tprop；
5)接收节点按位(bit)接收消息并传递给MAC层的时间，设为treccp；
6)接收节点重新组装消息并传递给上层应用所需的时间，设为treceive。

从发送节点生成同步消息到接收节点接收到同步消息，总的用时t如公式(1)所示

2.2 同步消息扩散过程中的冲突避免机制

在网络初始化时，Sink节点广播时间同步消息，所有节点在收到同步消息后，对该消息中的时间域进行偏移量纠正，将纠正后的时间作为节点的本地时间，但是，并不立即转发，而是随机延时一段时间，以避免因多个节点同时转发该消息而造成再次冲突，随机延时后根据信号强度指示器RSSI的值判断节点信道是否空闲。如果信道空闲，节点将转发纠正后的同步时间，当所有节点仅转发一次时间同步消息时，全网节点将保持时间同步。基于NesC语言定义的时间同步消息格式如下所示：

由于不同节点的时间晶振频率存在细微差异，在上次节点时间同步的基础上，经过一段时间后，不同节点的本地时间又会出现新的偏差，当这种偏差超出协议要求的时间同步精度时，需要重新对全网节点进行时间同步，时间同步的更新周期的推导公式如下

f+=f(1+ε)，

式中，f为节点的基准晶振频率；ε为晶振误差率系数；f+为全网节点中最大频率，最小频率为f_，则f_=f(1-ε)；TΔ为所有节点间的最大周期差，则

设T为时间同步更新的周期，当tΔ为所要求时间同步精度时

3成簇算法

在全网时间同步后，对全网进行成簇。为了使研究更具有针对性，同时，使解决的问题更加突出，本文设WSNs中的节点随机部署，部署后节点不可移动，每个节点有全局唯一的ID标识，全网的ID标识是连续递增的，节点的部署密度够保证全网的可靠连通，每个节点能够实时读取自身的剩余能量。

3.1 邻居节点信息获取过程

设计2个交换消息完成此阶段：Energy(u)消息用来交换节点的ID标识、节点的剩余能量以及节点可能的邻居个数；Degree(u)消息用来交换节点的度(即是该节点的邻居节点的数目)。Energy(u)的消息格式为：

邻居节点信息获取过程如下：

1)为了避免在邻居节点信息的交换过程中消息的传输发生冲突，在完成时间同步后，为每个节点分配一个时隙t，根据ID标识由小到大，每个节点只在自己的时隙广播消息；

2)节点在自己的时隙广播一次Energy(u)消息，在一跳通信范围之内的邻居节点接收到该消息后，保存该消息中所携带的源节点ID和源节点的剩余能量。在所有节点都广播了一次Energy(u)消息后，全网内的节点均知道自己邻居节点的ID及节点的剩余能量。

3)为了进一步获取邻居节点的度，必须进行二次信息交换。每个节点分别在自己的时隙广播Degree(u)消息，在一跳通信范围之内的邻居节点接收到该消息后，保存该消息中所携带的源节点的度。在所有节点都广播了一次Degree(u)消息后，全网内的节点均准确地获取到邻居节点的信息，该信息包括邻居节点的度、邻居节点ID以及邻居节点剩余能量，然后，该节点根据邻居节点度和剩余能量得到邻居节点的权值。

进行二次控制信息交换的主要优点是得到的邻居表中包含的信息比较全面，为下一步簇头的选取及骨干网的建立提供了较好的先决条件；缺点是每一次获取邻居表的等待时间可能会比较长，但是，由于邻居表获取时交换的消息短，这样，每次消息发送所耗费的时间和能量均比较小，在分配时隙一定的情况下，可以初步对全网的性能做出评价。 3.2成簇过程描述

在簇头的选取过程中，每个节点比较其自身节点的权值与其邻居节点的权值的大小，如果节点发现有邻居节点的权值大于其自身的权值时，那么，它将等待其他节点成为簇头的消息；反之，它将宣布自己成为簇头，并且，广播自己已经成为了簇头的消息，它的邻居节点在接收到消息以后，记住自己所在簇的簇头，且在这个周期内不再竞争簇头。为了进一步减少网络通信的数据量，当节点已经成为某个簇的成员后，它将不会再次成为其它簇的成员。

如图1所示，设全网的每个节点已经成功获取邻居信息，且初始时每个节点的剩余能量相等，即初始时节点的权值只与节点的度相关。成簇的基本过程为： 1)节点1在它的时隙中，比较自身的度与其邻居节点的度，发现没有比它度大的节点，则广播自己成为簇头的消息，节点3，4，5，10在收到该消息后，自动放弃成为簇头的可能，加入到节点1的簇中；

但是，上述成簇过程中，簇头的选取过程是一个寻找局部最大节点的度的过程，是一个局部最优的问题，当出现di<S(di)(其中，di表示节点i的度，S(di)表示节点i的所有邻居节点的度的集合)情况时，簇头的选取过程将转化为一个全局最优的问题，这样导致的严重后果是全网只有一个簇头，并且，此簇将无法包含所有的节点。如图2所示，全网只有一个节点成为簇头，并且，该簇只能覆盖有限数目的节点。解决的办法是：控制搜索局部最大节点的度的深度，如果在搜索了一定深度后发现还没有找到最大节点的度，则回退到此次搜索过程的起始节点，把起始节点作为簇头，然后，重复上述步骤1，2，3，4，直至所有节点均参与成簇。这样做的结果能够保证全网簇分布均匀，且能保证所有的簇集合覆盖全网节点。

3.3簇内节点通信机制

对于簇成员节点与簇头节点的通信，采用基于时分复用和随机退避的混合型算法，以避免簇成员节点向簇头节点传送数据时发生冲突，在簇头充分进行网内数据融合，节点的度越大的节点，它成为簇头时，数据融合度越高，以此减少网络数据流量，降低节点的能耗。

3.4簇间通信机制

文献[6]对簇头节点间的通信机制进行了详细的分析，认为任意相临簇的簇头间达成通信的最大跳数为3跳，但是，在实际情况中，如何选取非簇头节点参与簇头节点间的通信是一个比较麻烦的问题，要交换很多的信息，将消耗很多的能量，同时，如何避免这些交换信息的冲突也是一个比较麻烦的问题。

本文在研究CROSSB OW公司的MICA2节点可以通过编程动态改变节点的发射功率和频率的基础上，利用短时间增大功率和改变频率，以使得簇头节点间可以顺利地进行通信。虽然节点能量的消耗与节点发射功率的大小直接相关，但是，因为发射时间非常短，且只是改变各个簇头节点的发射频率，非簇头节点不会串听(overheard)到簇头节点间的通信，非簇头节点可以转换到休眠状态，从整体上节省全网节点的能量。

同时，为了保证全网的可扩展性，例如：有新节点加入或者旧节点失效，定期的更新节点间的邻居表信息，进而重新成簇是非常有必要的。 4算法性能评估与仿真分析

4.1 能量开销

为了衡量算法的性能，本文采用文献[8]提出的能量模型，即将一个分组长度为kbit的信息传输距离为d，则发送的能耗为

式中 Eelec为每比特数据发送／接收电路的能耗；εamp为传输放大器的系数，接收kbit数据的能耗为ERX(k)=kEelec，一次通信消耗的总能量为

在本文设计的算法中，全网节点进行了2次控制信息交换，设全网有N个节点，则网络中总通信次数为2(N-1)次，消耗的总能量为2(N-1)ET。而对于其他非冲突避免的算法，由于发生冲突时，数据需要重新发送，设可能的冲突概率为α，则总的通信次数为2(N-1)α&，且会带来全网的整体延时。

4.2度量指标

使用如下2个指标对本文提出的算法性能进行分析：

1)节点的能耗：指节点在一个成簇周期内全网节点总的能耗；
2)节点的延时：指全网节点在一个成簇周期内总的用时。

采用仿真的方法对成簇算法的性能进行评估。根据本文前面所述的各种消息类型，加上TinyOs的AM消息头(5bit)，时间同步消息为80bit，邻居节点信息获取的能量交换消息为88 bit，节点的度交换消息为64 bit，节点每发送1bit消息传输1 m的距离能耗为1.0 nJ／bit，每接收1 bit消息能耗为0.6 nJ／bit。

图3是对全网节点数目与全网节点能耗的模拟，从图中的曲线可以看出：随着节点数目的增多，没有引入冲突避免机制的数据通信的能耗将明显多于引入冲突避免机制的数据通信算法，并且，能耗增长的速度要快。

图4是对全网节点数目与全网节点延时的模拟，设每个节点分配的时隙长度为100 ms，从图中可以看出：本文所采用的算法随着节点数目的增大延时呈线性增长，而没有采用冲突避免机制时，随着节点数目的增大，全网节点的延时递增幅度更大。

5结论

降低能量消耗，延长网络寿命是无线传感器网络设计的主要目标，本文在节点随机部署后，采用C／S模式，由Sink节点广播节点时间同步消息，在全网节点同步的基础上，基于时隙划分进行控制信息的交换，以避免消息通信冲突。通过两次信息交换，每个节点均获取邻居节点的信息，然后，综合考虑候选节点的剩余能量、节点的度等参数来进行节点自主成簇以及簇头的选取，并通过节点的簇头的轮换机制，以延长网络寿命。