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

1、无线传感器网络时间同步与成簇算法    0引言融合了传感器技术、信息处理技术和网络通信技术的无线传感器网络(wirelesssensornetworks，WSNs)由分布在物理空间上大量传感器节点通过自组织的方式构建网络，节点通过集成各种微型传感器来感知环境或监测对象信息，协作地处理感知信息，并以自组织多跳无线通信方式将信息传送到用户，从而实现随时获取感兴趣区域信息。WSNs在军事、工业、农业、医疗及环境监测等领域有广泛的应用前景，在我国"国家中长期科学和技术发展0引 言融合了传感器技术、信息处理技术和网络通信技术的无线传感器网络(wirele

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

3、节点时间同步的基础上，获取节点的邻居信息，根据邻居信息，对全网节点进行自组织成簇，在簇内进行数据融合，减少网络的数据流量，以延长网络的寿命。     1相关研究工作文献1通过动态选举簇头来平均网络节点能耗，其他节点根据簇头信号的强度来作为判断是否加入该簇的依据；文献2在文献1的基础上进行了改进，通过设立软、硬门限进一步降低了能耗，只有当节点感知数据或其增幅超过预先设定的阈值时，节点才发送数据；文献3提出了一种随机簇组织局部算法，并在此基础上，提出了建立层次化簇结构的思想；文献4提出的簇组织算法，使各簇作用域无重叠且大小基本相等，并且，在旧节点失效和新节点

4、加入时，簇具有一定程度的自愈能力；文献5提出了一种基于时间触发的簇组织算法，仅当特定事件发生时，才启动簇组织过程，簇成员同簇头之间，允许多跳通信；文献6着重解决簇组织完毕后，相邻簇之间的连通和簇问路由建立问题，在成簇以后，簇头和簇头之间借助非簇头节点进行通信。但是，上述的算法中没有考虑成簇消息发送过程中的冲突问题，簇头间借助中间节点通信将带来很多的交换消息，且问题过于复杂。本文在提出一种时间同步算法的基础上，利用时隙划分，有效地克服成簇消息传输过程中的冲突问题；再基于节点的度、节点的剩余能量等参数加权选取簇头。成簇以后，通过动态改变簇头节点的通信功率和通信频率，以实现簇头间一跳通信，且其他的节

5、点不会串听簇头问的通信，有效降低节点的能耗。     2时间同步过程描述同步机制采用CS模式，由传感器网络中的Sink节点以多跳方式周期性地广播时间同步消息，所有节点在收到该同步消息后，充分考虑可能造成消息传输延时的原因，对消息中携带的时间进行纠正，然后，将纠正结果作为本地时间，同时记录收到消息的同步序列号，如果再次收到相同序列号的消息，则直接丢弃不做处理。2.1 同步消息扩散过程中的偏移量在WSNs中，将消息在节点间传递的过程分为如下6个部分：1)发送节点构造一条消息所需要的时间，包括内核协议处理和缓冲时间等，设为tsend；2)消息等待传输信道空闲所

6、需时间，即从等待信道空闲到消息开始发送时的延迟，设为taccess；3)发送节点按位(bit)发射消息需时间，该时间取决于消息长度和发射速率，设为ttrans；4)消息在2个节点之间传输介质中的传播时间，设为tprop；5)接收节点按位(bit)接收消息并传递给MAC层的时间，设为treccp；6)接收节点重新组装消息并传递给上层应用所需的时间，设为treceive。从发送节点生成同步消息到接收节点接收到同步消息，总的用时t如公式(1)所示在实际的应用中，可以根据所采用的无线传感器节点的型号，计算同步消息扩散过程中的时间偏移量，以有效地进行时间偏移纠正。2.2 同步消息扩散过程中的冲突避免机制

7、在网络初始化时，Sink节点广播时间同步消息，所有节点在收到同步消息后，对该消息中的时间域进行偏移量纠正，将纠正后的时间作为节点的本地时间，但是，并不立即转发，而是随机延时一段时间，以避免因多个节点同时转发该消息而造成再次冲突，随机延时后根据信号强度指示器RSSI的值判断节点信道是否空闲。如果信道空闲，节点将转发纠正后的同步时间，当所有节点仅转发一次时间同步消息时，全网节点将保持时间同步。基于NesC语言定义的时间同步消息格式如下所示：2.3 同步时间更新周期由于不同节点的时间晶振频率存在细微差异，在上次节点时间同步的基础上，经过一段时间后，不同节点的本地时间又会出现新的偏差，当这种偏差超出协

8、议要求的时间同步精度时，需要重新对全网节点进行时间同步，时间同步的更新周期的推导公式如下f+=f(1+)，式中，f为节点的基准晶振频率；为晶振误差率系数；f+为全网节点中最大频率，最小频率为f_，则f_=f(1-)；T为所有节点间的最大周期差，则设T为时间同步更新的周期，当t为所要求时间同步精度时如式(2)所示，在已知晶振误差率和同步精度的前提下，能计算节点时间同步的更新周期。3成簇算法在全网时间同步后，对全网进行成簇。为了使研究更具有针对性，同时，使解决的问题更加突出，本文设WSNs中的节点随机部署，部署后节点不可移动，每个节点有全局唯一的ID标识，全网的ID标识是连续递增的，节点的部署密度

9、够保证全网的可靠连通，每个节点能够实时读取自身的剩余能量。3.1 邻居节点信息获取过程设计2个交换消息完成此阶段：Energy(u)消息用来交换节点的ID标识、节点的剩余能量以及节点可能的邻居个数；Degree(u)消息用来交换节点的度(即是该节点的邻居节点的数目)。Energy(u)的消息格式为：邻居节点信息获取过程如下：1)为了避免在邻居节点信息的交换过程中消息的传输发生冲突，在完成时间同步后，为每个节点分配一个时隙t，根据ID标识由小到大，每个节点只在自己的时隙广播消息；2)节点在自己的时隙广播一次Energy(u)消息，在一跳通信范围之内的邻居节点接收到该消息后，保存该消息中所携带的源

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

11、及骨干网的建立提供了较好的先决条件；缺点是每一次获取邻居表的等待时间可能会比较长，但是，由于邻居表获取时交换的消息短，这样，每次消息发送所耗费的时间和能量均比较小，在分配时隙一定的情况下，可以初步对全网的性能做出评价。     3.2成簇过程描述在簇头的选取过程中，每个节点比较其自身节点的权值与其邻居节点的权值的大小，如果节点发现有邻居节点的权值大于其自身的权值时，那么，它将等待其他节点成为簇头的消息；反之，它将宣布自己成为簇头，并且，广播自己已经成为了簇头的消息，它的邻居节点在接收到消息以后，记住自己所在簇的簇头，且在这个周期内不再竞争簇头。为了进一步减少网络通信的数据量，当节点已经成为某个簇的成员后，它将不会再次成为其它簇的成员。如图1所示，设全网