基于分布式与联合优化的无线传感器网络数据汇聚机制

刘韬，李天瑞，谈文蓉，殷锋

（1. 西南民族大学 计算机科学与技术学院，四川 成都 610041；2. 西南交通大学 信息科学与技术学院，四川 成都 610031）

1 引言

无线传感器网络(WSN)中，数据汇聚是指将不同源节点的数据收集到汇聚节点（sink），显然，数据（信息）汇聚是无线传感器网络典型的传输形态[1]。根据数据汇报方式，无线传感器网络大致可以分为事件驱动型和周期汇报型2类网络[2]。在事件驱动型传感器网络，节点平时很少产生数据，仅在待监测的事件发生时才产生事件报告；而在周期汇报型传感器网络中，所有节点周期性地向汇聚节点报告采集到的信息，直到网络生命周期结束。与事件驱动型网络相比，周期汇报型网络中对节点汇报信息实时性要求往往较低，但每个节点都需要向汇聚节点周期性地发送信息，网络的数据量大，节点能耗高，且节点的无线信号冲突概率高，节点之间的无线信号相互干扰，MAC层设计复杂。

本文针对这些难点，提出了一种适用于周期汇报型网络的数据汇聚机制(DDSM)。该机制在“梯度汇聚”模型的基础上，联合优化MAC层和网络层功能，采用节点周期性睡眠/工作的节能调度方法，分布式地建立每个节点的优化路由及工作时隙。本文的主要贡献在于以下几点。

1) 提出一种完全分布式的由各个节点自行确立优化路由和工作时隙的机制，使该机制具有很强的实用性，并且采用该机制的网络具有良好的可扩展性和可维护性。

2) MAC层采用分布式TDMA的机制，并采用联合优化的思想，融合网络层、MAC层，使节点优化路由的建立、发送时隙的分配以及节点的时钟同步在一个过程中完成，放弃了单层优化、各层独立设计的手段，显然具有更高的效率，且节约了能量。

3) 由于节点间的相互干扰，节点发送时隙的确立是一个难题。DDSM采用RTS/Final_RTS/CTS的办法来解决该问题，即通过多次向邻居节点广播试探性RTS消息，直至没有收到否定应答帧NAK来确定发送时隙。

2 相关工作

不同于传统网络协议栈的层次结构，无线传感器网络的协议栈一般被分为4层[3]:应用层、网络层、媒体介质访问控制（MAC，medium access control）层和物理层。近年来，研究人员提出了许多数据收集协议，例如:网络层上，LEACH[4]是比较有代表性的分簇路由算法，而朱红松等提出了一种精细化梯度的数据汇聚机制 FGS[1]；MAC层上，经典的S-MAC[5]协议通过采用周期性侦听/睡眠工作方式来减少空闲侦听；文献[6]提出了一种由发送节点发起建立连接的异步低占空比、低碰撞的PB-MAC协议算法。这些网络协议大都采用单层优化的方案，各层相互独立。这种单层优化的方法虽然给网络协议的模块化带来了方便，但各层之间的相互独立、不能协作，导致网络的整体性能不能达到最优[2]。

联合优化设计的方法是近几年来提出的主要用于无线网络的设计方法，其设计思路是融合网络层、MAC层和物理层设计网络协议，多个层综合考虑优化，打破层与层之间的独立性，从全局的角度对系统的资源进行整合，能最大程度地节约节点的能量[7]。王辛果等在文献[2]中提出一种时延受限且能量高效的跨层路由协议，该协议在做出路由决定时考虑MAC层的相关信息。但该协议为事件驱动型网络而设计，在设计中较少考虑节点间信号的冲突和干扰问题，显然不适用于周期汇报型网络。李方敏等基于跨层优化的策略提出了一种易于实现能动态适应网络变化的能量有效的链路稳定成簇算法[8]，但该算法没有分析簇头到汇聚节点的优化路由，且没有考虑信号冲突问题。文献[9]结合MAC层协议与网络层路由协议，提出了AIMRP协议。该协议根据节点到汇聚节点的跳数，形成一个以汇聚节点为中心的多层环形结构，数据信息从外环逐环向内环传递。AIMRP协议同步精度要求高，但动态适应性差，只适用于小范围的事件驱动型传感器网络。

文献[10]提出了一种基于TDMA调度策略的跨层设计方案，该方案采用了分簇的结构，并通过构建涉及网络层、MAC层和物理层的跨层优化模型来获得高能效的调度方案。该方案证明了传感网的MAC层上采用TDMA机制具有零冲突、高能效的特点。但该方案是一种集中式的优化方案，即由汇聚节点集中计算每个节点的路由或调度方案，再把优化路由或调度方案发送给每个节点。集中式的算法缺乏可扩展性，网络也不具备可伸缩性[11]且汇聚节点收集源节点自身信息和发布优化方案的过程中会消耗大量能量。

文献[12]提出了一个基于TDMA机制的跨层优化数据收集协议 LEEMA，建立以汇聚节点为根的路由树，再通过该路由树为节点分配工作时隙。LEEMA采用的是最小跳数路由，该路由虽然建立简单，但是不一定是最小能耗路由，其节能效果不一定最优。另外，LEEMA没有考虑负载均衡，容易形成能量空洞。

尽管在近几年来，对无线传感器网络的数据汇聚机制已经有了相当的研究成果，但大都或多或少地存在一些缺陷与不足。本文在此基础上展开研究，在网络层和 MAC层上进行联合优化，提出了一个完全分布式、高能效与低成本的数据汇聚机制。

3 系统模型

3.1 网络模型

与文献[1]和文献[9]类似，本文中的传感器网络采用“梯度汇聚”模型将节点的数据传递给汇聚节点。假设网络中所有的节点均匀分布于监控区域中，sink位于区域中心，节点密度为p。所有的节点具有相同的最大无线传输距离R。网络被划分为以sink为圆心的n个相邻的环状区域，也称为“梯度”，d为每个圆环的宽度，所有节点位于各圆环内。从圆心向外，各圆环依次表示为C1，C2，…，Cn，如图1所示。

图1 网络模型(n=3)

针对周期汇报型传感器网络的特点，做如下说明。

1) 网络中的每个节点周期性的采集和发送数据。每个工作周期，每个节点产生一个固定大小的感应数据分组发往汇聚节点。

2) 节点路由采用“梯度汇聚”模型，处于圆环(梯度)Ci中的节点只能选择圆环Ci-1中的节点作为下一跳的数据转发节点(1

3) 所有节点能够动态的调整其发射功率，例如，Berkeley Motes 节点就具有100个发射功率等级[13]。

4) 所有节点的时钟能够保持同步。

为了增加网络的连通性，使

另外，经信道衰减，无线信号最终能否被成功接收取决于接收端的信号与干扰、噪声功率比SINR[2]。于是，采用式(2)来判断目的节点能否正确接收无线信号

其中，S表示信号接收功率，W表示噪声功率，I表示干扰信号功率。SINRthreshold表示一个门限值，通常它的值被设为10。假设噪声很小，忽略接收端的噪声功率，并假设B为接收节点，T为干扰节点的集合，可得

其中，Pr(B)与Pt(X)分别为接收节点B的接收信号功率和节点X的发送功率，d(X,B)为节点X与B的距离。

3.2 传播模型

根据文献[14]，当节点A发送无线信号到节点B时，节点B的接收信号功率Pr(B)为

其中，Pt(A)是节点A的发射功率，d(A,B)表示节点A和节点B之间的距离。本文假设传感器网络位于自由空间，则β=2。并且

其中，Gt和Gr分别是发射天线增益和接收天线增益，λ是信号波长。

3.3 相关定义

定义 1TRCS：载波监听门限或感应灵敏度。当节点接收信号功率大于等于TRCS时，节点才能感应到有信号发送。

定义 2TRRX：信号接收门限。当节点接收信号功率大于等于TRRX时，节点才能正确接收信号。

定义3RCS：载波最大监听距离。当节点以最大发射功率PtMax发射信号时，另一节点能感应到此次发送的最远距离。根据式(4)可得

其中，β=2。

定义4R：最大无线传输距离。当节点以最大发射功率PtMax发射信号时，另一节点能正确接收此次发送的最远距离。根据式(4)可得

4 若干关键问题

4.1 隐藏节点问题

目前，网络通常采用 RTS/CTS(请求发送/允许发送)协议来解决“隐藏节点”的问题[15]。如图 2所示，节点A欲向节点B发送数据，则：首先，A向B发送RTS信号，B收到RTS后，发CTS信号，表明已准备就绪，A可以发送，而其余收到CTS的节点则暂停发送。此协议认为节点发送CTS的范围能够覆盖所有的隐藏节点，但在实际节点接收模型中，隐藏节点的分布范围远大于节点的发送范围[15]。如图 2所示，若每个节点能以最大发送功率发送无线数据信号，则节点B的干扰节点区域是以节点B的圆心，RCS为半径的圆，位于此圆内的节点发送信号都会对节点B的接收造成干扰。很明显，节点B发CTS信号，最大发送功率为，只有与B的距离小于R的节点才能收到CTS信号，位于图2中阴影区域内的节点无法收到CTS信号，而这些节点又处于节点B的干扰节点区域内，若它们此时发送数据，会对节点B的接收造成干扰，甚至影响接收，形成“隐藏节点”。这说明RTS/CTS协议在较低信噪比要求的情况下可以防止大部分隐藏节点，但是随着信噪比要求的逐步提高，网络中的隐藏节点分布范围急剧增大，RTS／CTS协议防止隐藏节点的效率也随之降低[15]。

图2 RTS/CTS握手协议中的隐藏节点问题

为解决这一问题，本文借鉴文献[16]的方法来改进RTS/CTS协议，即减小节点发送感应数据的最大发送功率，从而减小接收节点的干扰节点区域，确保接收节点以最大发送功率发送CTS信号时，干扰节点区域内的节点都能够接收到 CTS信号。假设节点发送数据的最大发送功率限定为为了确保接收节点的干扰节点区域内的节点都能收到来自接收节点的CTS信号，干扰节点区域的最大半径只能为R，根据式(4)可得

其中，β=2。结合式(7)可得

所以，为了避免“隐藏节点”的问题，“梯度汇聚”模型中每层圆环的宽度d重新调整为

4.2 “梯度汇聚”机制下的最小能耗路由

“梯度汇聚”机制下，节点只能将数据传递给相邻环(梯度)中的节点。例如，如图 3所示，节点D有2条路由到达sink，分别为D→B→A→sink和D→C→A→sink，节点D选择哪条路由首先要判断总能耗的大小。

图3 “梯度汇聚”机制下的最小能耗路由

假设Emin(X)表示网络中任一节点X生成一个感应数据分组到达汇聚节点的最小总能耗，Cos(X,Y)表示一个数据分组从节点X到达节点Y的能耗，则

其中，Pt(X)与Pr(Y)分别表示节点X发射功率和节点Y的接收功率，t表示节点发送或接收一个数据分组所花费的时间。为了进一步降低节点的能耗，尽量减小发送节点发送数据的功率，当接收端的接收信号功率等于信号接收门限TRRX时，结合式(4)，可以获得节点发送信号所需的最小发射功率Ptmin

其中，d(X，Y)表示发送节点X与接收节点Y的距离。根据式(12)与式(13)，可得一个数据分组从节点X到达节点Y的最小能耗

其中，节点的接收功率一般为固定值Pr。若Sn为节点X位于相邻梯度(相邻内层圆环)的邻居节点集合，结合式(14)，Emin(X)可以通过式(15)计算。

如果节点获得了它所有相邻梯度的邻居节点生成一个数据分组到达汇聚节点的最小总能耗，它就能根据式(15)计算得到它相应的最小总能耗，并选择对应的邻居节点为下一跳目的节点。当每个节点都确立了下一跳目的节点后，节点到达汇聚节点的优化路由自然就确立了。所以，DDSM中，节点优化路由的建立过程是由内而外，逐环建立的。即先由第1层圆环的节点先确立下跳目的节点，再由第2层圆环的节点确立下跳目的节点，以此类推，直至最外层。这样做的目的是在内层圆环（梯度）的节点优化路由的建立过程中，通知外层相邻圆环邻居节点其优化路由等信息。当轮到外层相邻圆环邻居节点建立优化路由时，就可以依据这些信息，通过式(15)做出选择。

另外，节点选择其下一跳路由节点时，还要注意平衡节点的负载，避免把某个节点频繁选作路由中继节点，从而过快耗尽能量造成能量空洞。

5 DDSM机制描述

TDMA机制是网络无线信道分配机制之一，具有零冲突、高能效、低时延的特点，可以很好地应用于数据量大的周期汇报型传感器网络，所以DDSM采用TDMA机制实现无线信道分配。

DDSM按轮运行，每轮分为2个阶段。第一阶段是节点优化路由和时隙调度表的建立阶段:每个节点分布式地确立自身到汇聚节点的数据发送路由、所需的发送功率以及相应子阶段内的工作时隙；第二阶段是节点数据汇聚阶段，节点根据分配好的工作时隙，周期性地从休眠状态醒来，发送数据或接收数据，数据则遵循建立好的优化路由，由外而内，逐环(梯度)的方向向汇聚节点传递。每轮都要重新建立每个节点的工作时隙和发送路由是为了适应因个别节点位置变化或节点死亡而造成的网络拓扑结构的变化。

5.1 数据汇聚阶段

每轮的数据汇聚阶段由若干个数据采集周期组成，所有节点在每个数据采集周期都要生成一个感应数据分组，并向汇聚节点发送。为避免冲突，如图4所示，将一个数据采集周期再划分为若干子周期，每个子周期再继续划分为m个时隙，单个时隙的长度等于节点发送一个感应数据分组所需的时间，m也必须足够大使节点能够有时间发送完所有的数据分组。每个子周期分配给一个圆环(梯度)，位于圆环Ci(1＜i≤n)内的节点只能在每个数据采集周期的第n-i+1个子周期内的相应时隙发送数据，而相邻圆环梯度的节点则接收数据。例如，第一个子周期第3层圆环的节点发送数据，第2层圆环的节点则接收数据；而第2个子周期第2层圆环的节点发送数据，第1层圆环的节点则接收数据，以此类推，直至发送到汇聚节点。而节点在相应子周期的发送时隙则由 DDSM 在每轮的节点优化路由和时隙调度表的建立阶段中确立。

图4 一个数据采集周期的时间划分

5.2 节点优化路由和时隙调度表的建立阶段

DDSM在本阶段采用多层次联合优化的思想，建立“梯度汇聚”机制下每个节点发往汇聚节点的优化路由，并同时确立每个节点无冲突的时隙调度表。为了避免不同节点在建立路由和时隙调度表的过程中发生信号冲突，所有节点逐个轮流建立自己的优化路由和时隙调度表。因为优化路由的建立过程与时隙建立过程分别依赖不同方向的累积效应，将该阶段划分为2个子阶段：节点优化路由建立子阶段和节点时隙调度表的建立子阶段。

为了方便节点建立优化路由和时隙调度表，每个节点都建立了2张表，内层圆环的邻居节点信息表和节点的时隙情况表，例表分别如表1与表2所示。

表1中存储的是节点的相邻内层圆环中邻居节点的信息。其中，NodeID是邻居节点的ID，relayed是需要通过本节点中继(转发)数据分组的节点数量。Emin是节点发送一个数据分组到达汇聚节点过程中的最小能耗，dist是本节点到该邻居节点的距离。assigned_slots[m]表示节点在数据汇聚阶段相应的接收子周期内时隙占用情况的数组，1表示该时隙已被占用来接收某节点信号，0表示空闲。注意第1层圆环中节点的表1只需要记录汇聚节点的相关信息。表2中存储的是节点在一个子周期的每个时隙的情况表，包括节点在相应时隙内是否处于接收状态receiving(1表示节点在该时隙内处于接收状态)和每个时隙的累积干扰信号功率Pinterfere，用于计算SINR。网络初始化时，2张表为空表。节点在建立路由和时隙调度表的过程中，不断完善这2张表。

表1 邻居节点信息

表2 节点时隙情况

5.2.1 节点优化路由建立子阶段

以图5所示为例，显示了位于圆环Ci中的节点A使用算法1确立下一跳目的节点的过程，算法1具体步骤描述如下。

1) 节点A从表1中挑选负载（relayed）不超过τ的相邻内层圆环中邻居节点，即relayed≤τ(τ为节点允许通过本节点转发的节点数量最大门限值，这样做的目的是均衡同一层圆环内节点的负载)，并保存到集合Set中。

2) 若集合Set不为空，则以集合Set中的节点为A的中继节点，结合表1中的相关信息，根据式(15)计算Emin(A)，并获得中继节点B，确定该邻居节点B为下一跳目的节点，进入步骤4)。

3) 若集合Set为空，则τ=2τ，返回步骤1)。

4) 节点A设置发射功率为Ptm，发送消息RTS，消息中包含下一跳目的节点B的NodeID、节点A的梯度值(HC)和最低总能耗Emin(A)。

5) 节点B收到消息RTS后，修改表1中相应内容，然后以功率Ptm发送消息CTS。

6) 若节点A相邻外层圆环中的邻居节点收到RTS，如节点D，则据无线信号强度值RSSI（received signal strength indicator）来获得2个节点的相对距离dist，根据式(4)可得

其中，β=2，Precv为接收端接收到的信号功率。

然后，节点D更新其表1中与节点A对应的相应内容（Emin，dist等）。

7) 若节点B相邻外层圆环中的邻居节点收到CTS，如节点F，则更新其表1中与节点B对应的相应内容（relayed=relayed+1）。

节点A完成上述RTS/CTS握手过程后，进入休眠状态直至节点时隙调度表的建立子阶段。

需要注意的是，根据文献[17]的论证，不同层内节点的能耗是不可能完全均衡的，所以算法1确保同一层圆环内节点的负载均衡。

图5 RTS/CTS握手过程

图6给出网络中节点优化路由的建立过程：首先，由第1层圆环中的节点轮流执行算法1，但要注意此时节点的目的节点只能是汇聚节点，并通知第2层圆环中的节点更新相关信息；然后，第2层圆环中的节点轮流执行算法1，确定其位于第1层圆环中的下一跳目的节点，并通知第3层圆环中的节点更新相关信息；接着第3层，…，直至最外层圆环中节点完成此路由建立过程。

5.2.2 节点时隙调度表的建立子阶段

在所有节点均确立了下一跳目的节点后，网络进入节点时隙调度表的建立子阶段。如图6所示，该子阶段与节点优化路由建立的过程相反，所有节点按照由外到内的圆环顺序轮流建立时隙调度表。即先由最外层圆环的节点先轮流确立发送时隙，建立时隙调度表，再由次外层圆环的节点建立时隙调度表，…，以此类推，直至第1层圆环。

图6 节点优化路由及工作时隙的建立顺序

该子阶段中，每个节点都需要维持变量load记录一个数据采集周期内自己需要发送的数据分组数量，包括转发的数据分组和自己生成的数据分组，初始值为1。因为数据汇聚阶段中，一个时隙的长度等于节点发送一个感应数据分组所需的时间，所以节点需要的时隙数量等于load。节点在确立一个发送时隙时，既要判断目的节点在此时隙内是否是空闲的，还要判断此次发送是否会影响该时隙内处于接收状态的非目的节点的接收过程。DDSM 拟采用RTS/Final_RTS/CTS握手的办法来解决该问题，即通过多次向邻居节点广播试探性RTS消息，直至没有收到否定应答帧NAK来确定发送时隙。

位于圆环Ci(1

1) 节点A从表1中选择下一跳目的节点B的最小空闲时隙，并根据式(13)计算节点A发送信号所需的最小发射功率，然后以最大发射功率发试探性的请求消息RTS，消息中包含欲请求的时隙号ReqSlot与的值。

2) 圆环Ci-1中的节点(除节点B)收到该RTS，则判断自己在节点A的请求时隙内是否处于接收状态，若处于接收状态，则将节点A到节点B的信号发送视为对自己的干扰，结合节点A的发射功率，并根据表 2和式(3)计算SINR，若小于SINRthreshold则发否定应答消息NAK。

3) 目的节点B收到该RTS后，也根据表2和式(3)计算SINR，若小于SINRthreshold则同样发否定应答消息NAK。

4) 节点A收到NAK或探测到有冲突发生，则说明该请求时隙被否定，重新从邻居节点信息表中选择下一跳目的节点B次小的空闲时隙，再次以最大功率PtMax发试探性的请求消息RTS，返回步骤2。

5) 节点A发了RTS后在大小为TimeOut的后续时间内没有收到NAK或探测到有冲突发生，说明请求成功，节点A以最大功率PtMax再发最终的请求消息Final_RTS。

6) 目的节点B收到消息 Final_RTS后，修改load（load=load+1）及表2中对应时隙的接收状态（receiving），以最大功率PtMax发送消息CTS；而节点A在相邻内层圆环中的其他邻居节点收到消息Final_RTS后，修改表2中对应时隙的累积干扰信号功率Pinterfere。

7) 节点B的相邻外层圆环中的节点收到消息CTS后，更新其表1中节点B对应的空闲时隙表assigned_slots[m]，把请求时隙的对应位设置为1，表示该时隙已经被占用。

因为一个时隙只能发送一个数据分组，而每个节点有load个数据分组需要发送，所以节点重复执行load次算法2，申请load个时隙。

图7描述了算法2的一次执行过程（节点I与节点J位于圆环Ci-1中，且为A的邻居节点）：首先，A发送请求消息RTS；节点I收到后，经判断，发送否定应答消息NAK；节点A收到NAK后，重新选择请求时隙，并再次发送请求消息RTS；节点J收到后，经判断，再发否定应答消息NAK，…，此过程一直重复，直到没有收到NAK或探测到冲突，于是发消息Final_RTS确认请求时隙，目的节点B发送消息CTS回应。

图7 时隙请求算法中的消息

当第n层到第2层中的节点完成时隙调度表的建立后，第1层圆环中的节点则轮流直接向汇聚节点发送请求消息RTS，汇聚节点回复消息CTS，包含允许节点发送的发送时隙。

6 相关参数分析

6.1 参数m分析

DDSM中，参数m是一个数据采集周期中每个子周期的时隙数量，并且单个时隙的长度等于节点发送一个感应数据分组所需的时间。如果m的值过小，则可能会造成节点在其相应的发送子周期中没有足够的时间发送完所有的数据分组；如果m的值过大，则会增加感应数据传递到汇聚节点的时延。

由于感应数据是按梯度逐级向汇聚节点传递的，每层圆环的节点都需要转发外层圆环中节点的感应数据。很明显，各层圆环中节点所需要发送的数据分组是不相同的，内层圆环中的节点需要发送的数据分组往往较外层圆环中节点的数据分组多，也就需要更多的发送时隙。特别地，第一层圆环中的节点需要发送网络中所有节点的感应数据分组，包括转发的数据分组和节点自身生成的数据分组，而且第一层圆环中的节点只能将数据分组发送给汇聚节点，汇聚节点只能逐个接收每个节点的数据分组，所以第一层圆环中的节点发送数据相应的子周期内需要最多的时隙。所以，m应当满足

其中，N为网络中节点的数量，ρ为节点分布密度，SA为监控区域面积。

6.2 参数ω分析

如图8所示，任一节点Q位于圆环Ci，与sink的距离为r。深色区域为节点Q的下一跳可达区域，即位于该区域的节点才能够接收节点Q的数据，若该区域没有节点，则造成该节点无法连通，并发送数据。根据文献[18]，因节点均匀分布，所以节点的部署服从泊松分布，于是，可通过式(18)计算该节点可以连通的概率p。

其中，Sq为节点下一跳可达区域的面积。显然，p与Sq正相关。根据式(11)，ω（0＜ω＜1）的大小决定了圆环的宽度d。若ω越大，则d越大，网络中的圆环数量越少，但节点的可达区域（尤其是位于圆环外边缘的节点）的面积越小，网络连通性变差；ω变小，节点的可达区域面积增加，网络连通性变好，但是d减小造成网络中的圆环数量增加，网络数据汇聚的总能耗也随之增加。所以，在满足节点的连通的概率p大于门限值pt的情况下，合理选择ω的值。要使p＞pt，则根据式(18)，Sq要满足

图8 任意节点Q的下一跳可达区域

若Q位于圆环Ci的外边缘上(r=id)，结合图8，Sq可通过式(20)获得。

显然，位于圆环Ci的外边缘上节点的Sq小于该圆环内其他节点的Sq，若位于圆环Ci的外边缘上节点的Sq满足式（19），则所有节点的连通性可以得到保证。因网络中圆环数量有限，采用一种启发式算法来快速获得该问题的近似解，描述如下。

1)ω初值取0.99；

2) 利用式(11)计算圆环的宽度d；

3) 利用式(20)计算每层圆环的外边缘节点的Sq，然后利用式(19)判断这些节点的连通的概率p是否大于门限值pt；若均满足条件，则确定ω的值，并退出；否则ω=ω-Δ(Δ为一较小的数，如0.1)，返回步骤2)。

7 性能分析

7.1 模拟实验环境设置和参数

利用 OPNET作为模拟实验平台，对所提DDSM机制进行评估和分析。仿真实验中，所有节点均匀分布于一个半径为L的圆中，汇聚节点位于圆心处，且整个圆被划分为n个宽度为d的圆环。如无特别指定，所有的实验参数设置如表3所示。

表3 模拟参数

根据式(7)和表3中的参数，可以计算出节点的最大无线传输距离R=125 m。正如本文4.1节所述，为了避免隐藏节点问题，需要减小节点发送感应数据的最大发送功率，从而减小接收节点的干扰节点区域。于是，节点发送感应数据的最远距离由R缩短为rm（式(10)），而每层圆环的宽度d也随之调整（式(11)）。

另外，为了确保网络具有很好的连通性，假设节点连通的概率门限值pt=0.95，使用6.2节中的启发式算法来获取合理的ω值，使所有节点连通的概率p大于pt，同时使用式(11)计算此时每层圆环的宽度d。经计算，可得ω=0.6，d=33.5 m。如无特别值，ω和d分别设置为0.6和33.5 m。

根据相应的仿真参数，实验中所采用网络的拓扑结构如图9所示。其中，汇聚节点位于图中心。

图9 网络拓扑结构（n=3）

7.2 实验结果

7.2.1 不同参数取值对网络性能的影响

根据式(11)，ω的取值会改变网络中每层圆环的宽度。首先分析ω的不同取值对网络连通性的影响。

图10反映了不同ω的取值下，通过式(18)与式(20)计算获得的网络中节点最低连通概率。当ω的值越大时，根据式(11)，圆环的宽度也就越大，但是每层圆环外边缘的节点可以选择的下一跳节点的范围也就越小，以至于影响网络的连通性。

图 11反映了不同ω的取值下，网络采用DDSM机制运行120 min后节点数据分组的成功到达率(指到达汇聚节点)。从图中可以看出，当ω＞0.6时，数据分组的成功到达率明显下降，这与分析计算结果吻合，说明分析正确。后面的实验中，为保证网络的连通性，门限值pt取值0.95，ω则取值0.6。

图10 不同ω下的节点最低连通概率（n=3）

图11 不同ω下的数据分组成功到达率（n=3）

接下来分析节点允许转发的节点数量最大门限值τ对数据分组的成功到达率的影响。当τ的取值比较小时，每个节点作为中继节点，允许转发的节点数量得到了严格的限制，避免了个别节点频繁被作为中继节点，从而过早地耗尽了能量。但是如果τ的取值过小，部分节点可能会找不到下一跳目的节点，从而影响了网络的连通性。图 12给出了不同的τ值对数据分组的成功到达率的影响，从τ=2开始，数据分组成功到达率逐渐提高，当τ=4时，数据分组成功到达率达到了90%。

7.2.2 与其他数据收集机制比较

为了评估 DDSM 的性能，比较 AIMRP[9]、S-MAC[5]、LEMMA[12]和DDSM这4种数据收集协议在数据分组成功到达率和功耗方面的性能。S-MAC协议中，假设节点采用最小跳路由到达汇聚节点。

如图13所示，在4种数据收集协议都不允许数据分组发送失败重传的条件下，比较4种协议的数据分组成功到达率。从图 13可以看出，当圆环的数量增加时，即网络的规模扩大时，采用AIMRP和S-MAC这2种协议的数据分组成功到达率不断下降，而DDSM和LEMMA的数据分组成功到达率则基本维持在90%以上。这是因为AIMRP协议每次发送数据分组都需要通过 RTR/CTR/DATA/ACK握手机制实现，过程繁琐，动态适应性差，只能适用于小范围的事件驱动型传感器网络。S-MAC协议采用周期性的侦听/睡眠机制，其侦听/睡眠时间不能根据网络中负载的变化动态调整，而且 S-MAC协议采用退避发送机制来降低节点间碰撞的概率，当网络规模扩大时，网络中数据量增加，采用 S-MAC协议网络的信道碰撞的几率急剧增大，易导致网络堵塞，使网络的数据分组成功到达率急剧下降。而本文所提的DDSM和LEMMA都采用TDMA机制，充分考虑了干扰和冲突避免，数据汇聚阶段没有数据碰撞重传的问题，所以网络规模的扩大对数据分组成功到达率影响不大。

图12 不同τ下的数据分组成功到达率（n=3）

图13 不同圆环总数下数据分组成功到达率

图14给出了网络采用4种数据收集协议在不同的数据采集周期(T)下的数据分组成功到达率。从图 14中可以看出，当数据采集周期变大时，即节点的感应数据分组产生频率降低时，网络采用DDSM 和 LEMMA协议时的数据分组成功到达率基本保持不变，且维持在90%以上，这是由于这2种协议采用TDMA机制；而AIMRP和S-MAC这2种协议的数据分组成功到达率则相应增加，这是由于随着感应数据分组产生频率的降低，节点间碰撞的概率也相应降低。

图14 不同数据采集周期下数据分组成功到达率

图15给出了网络采用4种数据收集协议在不同的节点分布密度下数据分组成功到达率。从图15可以看出，当节点分布密度增加时，即网络中节点数量增加，DDSM和LEMMA变化不大，保持在90%以上。DDSM的数据分组成功到达率甚至略有增加，这是因为节点数量的增加提高了节点下一跳可以连通的概率（式(18)），而AIMRP和S-MAC这2种协议的数据分组成功到达率则不断下降，这是因为节点数量的增加也增加了网络信道碰撞的几率。

图15 不同节点分布密度下数据分组成功到达率

图16给出了网络采用3种数据收集协议时节点平均功耗的比值，分别是AIMRP与DDSM的比值，以及S-MAC和DDSM的比值。图16充分体现了DDSM能量高效的特点，也说明了DDSM中采用的 TDMA机制非常适合无线传感器网络节省能量的要求，当网络中的节点建立了优化路由与时隙调度表后，在感应数据向汇聚节点传输的过程中不需要多余的控制信息，也没有数据碰撞重传的问题；AIMRP协议中的RTR/CTR/DATA/ACK握手机制，过程繁琐且耗能；S-MAC协议要求节点周期性的侦听，并且节点还需要周期性的广播自己的调度信息，这都大量的消耗了节点的能量。需要注意的是，图 16中，在网络中仅有一个圆环时，与网络中具有多个圆环的情况相比，DDSM中节点的平均功耗要远低于其他2种数据收集协议，这是因为网络中仅有一个圆环时，节点不再需要转发来自外层圆环中节点的数据，只需要把自身感应数据发给汇聚节点，所以在DDSM中，此时节点无需进入侦听状态，也就降低了节点的功耗。可见，空闲侦听的能耗在节点的总能量消耗中占据了较大的比例。

图16 采用不同协议时节点平均功耗的比值

图17给出了网络分别采用DDSM和LEMMA协议时，在不同圆环的总数下节点的平均功耗。可以看出，网络采用LEMMA协议时，节点的功耗较高，这是因为LEEMA采用的最小跳数路由并不一定是最小能耗路由，其节能效果不如DDSM。

图18反映了网络分别采用DDSM和LEMMA协议时，在不同圆环的总数下网络的生命周期比较。其中，网络中各节点的初始能量为1 mJ，网络的生命周期值定义为从网络开始运行持续到网络中 1%的节点耗尽能量为止。可以看出，网络采用DDSM 协议时的生命周期较网络采用 LEMMA协议时长，这是因为DDSM中，节点在选择路由时既考虑了路由的能耗，又限制了节点作为中继节点的次数，从而延长了网络的生命周期。

图17 DDSM和LEMMA下节点的平均功耗

图18 DDSM和LEMMA下网络的生命周期比较

8 结束语

本文分析了大规模的周期汇报型无线传感器网络的特点，并针对大规模的周期汇报型无线传感器网络提出了一种基于分布式与联合优化的数据汇聚机制(简称 DDSM)。该机制采用分布式与跨层设计的思想，融合MAC层与网络层功能，设计基于分布式的跨层数据汇聚机制及其实现算法，有效提高了网络的能量利用效率，降低了网络的成本，延长了网络的生命周期。

[1] 朱红松, 孙利民, 徐勇军等. 基于精细化梯度的无线传感器网络汇聚机制及分析[J]. 软件学报,2007,18(5): 1138-1151.ZHU H S, SUN L M, XU Y J,et al. Mechanism and analysis on fine-grain gradient sinking model in wireless sensor networks[J].Journal of Software, 2007, 18(5):1138-1151.

[2] 王辛果, 张信明, 陈国良. 时延受限且能量高效的无线传感器网络跨层路由[J]. 软件学报, 2011,22(7):1626-1640.WANG X G, ZHANG X M, CHEN G L. Delay- constrained and energy-efficient cross-layer routing in wireless sensor networks[J]. Journal of Software, 2011, 22 (7):1626-1640.

[3] LUCAS D P, MENDES, JOEL J P C,et al. A survey on cross-layer solutions for wireless sensor networks[J]. Journal of Network and Computer Applications, 2011, 34(2):523-534.

[4] WENDI B. HEINZELMAN, ANANTHA P,et al. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Trans. Wireless Comm., 2002, 1(4):660-670.

[5] YE W, JOHN H,et al. An energy-efficient MAC protocol for wireless sensor networks[A]. Proc IEEE INFOCOM[C]. 2002.1567-1576.

[6] 李哲涛,朱更明,王志强等.低占空比、低碰撞的异步无线传感器网络MAC协议[J].通信学报, 2013,34(10):9-16.LI Z T, ZHU G M, WANG Z Q,et al. Low duty cycle and low collision asynchronous MAC protocol for wireless sensor network[J].Journal on Communications, 2013,34(10):9-16.

[7] GEOFFREY G. MESSIER, JENNIFER A,et al, DAVIES. A sensor network cross-layer power control algorithm that incorporates multiple-access interference[J]. IEEE Transactions on Wireless Communications, 2008, 7(8):2877-2883.

[8] 李方敏, 刘新华, 徐文君等. 无线传感器网络的链路稳定成簇与功率控制算法[J]. 计算机学报, 2008, 31(6): 968-978.LI F M, LIU X H, XU W J,et al. Link-stable clustering and power control for wireless sensor networks[J]. Chinese Journal of Computers,2008, 31(6):968-978.

[9] KULKARNI S, IYER A, ROSENBERG C. An address-light, integrated MAC and routing protocol for wireless sensor networks[J].IEEE/ACM Transactions on Networking, 2006, 14(4):793-806.

[10] SHI L Q, ABRAHAM O, FAPOJUW O. TDMA scheduling with optimized energy efficiency and minimum delay in clustered wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2010,9(7):927-940.

[11] 郑国强, 李建东, 周志李. 多跳无线传感器网络的高能效数据收集协议[J]. 软件学报, 2010, 21(9): 2320-2337.ZHENG G Q, LI J D, ZHOU Z L. Energy-efficient data gathering protocol for multihop wireless sensor networks[J]. Journal of Software,2010, 21(9): 2320-2337.

[12] MACEDO M, GRILO A, NUNES M. Distributed latency-energy minimization and interference avoidance in TDMA wireless sensor networks[J]. Computer Networks, 2009, 53(5):569-582.

[13] 曾志文, 陈志刚, 刘安丰. 无线传感器网络中基于可调发射功率的能量空洞避免[J], 计算机学报, 2010, 33(1):12-22.ZENG Z W, CHEN Z G, LIU A F. Energy-hole avoidance for WSN based on adjust transmission power[J]. Chinese Journal of Computers,2010, 33(1):12-22.

[14] RAPPAPORT T. Wireless Communications: Principles and Practice[M]. Prentice Hall, New Jersey, 1996.

[15] 张克旺,张德运,杜君.面向多跳无线网络的无冲突MAC协议[J]. 软件学报, 2009,20(7):1895-1908.ZHANG K W,ZHANG D Y,DU J. Collision free MAC protocol for multi- hop wireless networks[J]. Journal of Software, 2009,20(7):1895-1908.

[16] XU K X, GERLA M, SANG B. How effective is the IEEE 802.11 RTS/CTS handshake in ad hoc networks[A]. Proc of the IEEE Global Telecommunications Conf[C]. 2002.72-76.

[17] 吴小兵,陈贵海.无线传感器网络中节点非均匀分布的能量空洞问题[J].计算机学报,2008,31(2):253-261.WU X B, CHEN G H. The energy hole problem of nonuniform node distribution in wireless sensor networks [J]. Chinese Journal of Computers,2008,31(2):253-261.

[18] WANG Y, WANG X D, XIE B,et al. Intrusion detection in homogeneous and heterogeneous wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2008,7(6):698-711.