低能耗节点位置未知无线传感器网络控制方案

摘要：介绍了一种低能耗节点位置未知的网络控制方案，根据不同的网络运行轮数设定网络节点的通信半径，使网络具有良好的能量有效性。网络中基站经过构建阶段的启动过程、节点信息收集过程和节点信息上报过程，获得了整个网络节点的相对位置分布，然后整合节点-节点信息支路，得到具有回路链接的簇首节点集，其他节点根据自己邻居信息选择簇首节点，实现网络近似最小能耗拓扑的构建。通过仿真与同类典型算法LEACH-C、MCLB进行比较，结果显示该方案应用于网络运行时具有更长的网络生命周期、更少的信息总数和更低的网络构建代价。
关键词：无线传感器网络；低能耗；节点位置未知；能量有效性

0 引言
    无线传感器网络是由一个基站和大量的传感节点构成。传感节点通常被随机放置在监测区域内，基站负责指导传感节点工作并且收集传感节点检测到的信息，并将环境信息报送至监控中心。通常，传感节点体积很小且具有感知周围环境信息、数据处理与存储和无线数据收发三个基本功能。无线传感节点在应用时受到很多限制如处理速度慢、存储容量小、电能有限等，而基站具有外部电源支持，处理能力比传感节点强大很多，它负责收集传感节点的监测信息并转发给用户。由于无线传感节点的能量有限性，降低能量消耗、延长网络生命周期，成为无线传感器网络通信协议设计的首要目标。
    分簇算法应用于无线传感器网络通信协议设计，被认为是一种减少网络能量消耗的有效办法。它通过选择一部分传感节点作为簇首节点形成一个暂时固定的网络构架，各簇首节点接收邻居簇首节点、簇内节点感知的环境信息，进行数据融合，剔除冗余信息，并转发至基站。这一类的经典算法有：文献LEACH-C是一种集中的聚类算法。在启动阶段，基站接收网络中所有节点发送来的包含他们位置以及能量状态的信息。基站运行本地算法获得簇首以及分簇表，然后广播包含簇首ID信息给每一个节点。簇头确定后，普通节点选择离其最近的簇头加入该簇头所管辖的区域，进而形成簇区域。协议维护阶段与LEACH是一致的。簇的建立过程在每一轮里都需要进行一次，从而产生了很多的能量消耗和传输延迟。文献MCLB算法首先找出网络中的冗余节点作为临时簇头，并随机选择一定数量的具有高的剩余能量的节点为簇头，临时簇头和簇头构成了一个数据转发层，而其他节点构成了一个数据收集为主要功能的底层，簇头广播hello消息并找到属于本簇的节点从而完成对网络的分簇。在数据转发上，存在节点-节点、节点-簇头和簇头-簇头多跳转发至基站的混合模式，该算法中由于簇头的位置具有随机性，为了保
证数据转发的可靠连通，因此每个节点必须以较大的发射功率进行数据转发而产生了不必要的能量浪费。文献提出的算法CDC将网络进行分簇，每一簇自行选择一个簇头。簇头承担起收集簇内成员信息并进行数据融合，然后再将数据转发给基站，并且依据信息选择下一轮的簇头。一旦簇内有节点死亡，簇首将发送信息给基站，对整个网络进行重新分簇，否则簇首选择能量最多的节点作为下一轮的簇首。
    本文提出一种新的网络控制方案由网络构建阶段和网络维护阶段组成。在网络构建阶段本文借鉴了文献的思想，设计了一种节约能耗的构建方法，首先由基站发出拓扑构建信息，每个节点完成对父节点和邻居节点信息的收集并将信息在特定的时刻传输给自己的父节点，基站通过获得的全网节点信息选择一部分具有冗余连接的簇头节点集，完成了一种期望的网络拓扑特性并保证了网络的连通性。一旦网络构建完成，就进入网络维护阶段，在该阶段每个节点根据网络的需要转换到特定的角色，当簇头节点集中的一节点能量下降到一定值时，由它提出网络重构，网络运行的两个阶段状态交替进行直到网络不能正常运行。本文设计的网络控制方案与文献LEACH-C算法和文献的MCLB算法进行仿真比较网络的生命期、网络构建信息交替情况和网络的构建代价。结果显示本文提出的方案应用于网络运行时具更长的生命周期、更少的构建阶段信息总数和更低的网络构建代价。

1 系统模型
    在本算法中，传感节点周期性的充当簇头节点或者普通节点，进行环境监测及数据转发。无线传感器网络监测区域内随机均匀放置N个传感节点，其中有一个节点为基站，在本文所提出的控制方案中，进行了以下几点假设：
    (1)每个传感节点被赋于一个惟一的标号，传感节点的能量有限，而基站有专门的供电系统。
    (2)每个传感节点可根据需要调整自己的发射功率，最大发射功率满足它们连接网络中离它最远的传感节点。
    (3)所有传感节点的位置不会发生移动，位置未知，具备通过接收信号的衰减程度来计算与信号发送方的距离。

2 LEPN网络控制方案
    LEPN控制方案下的网络运行是基于轮的，每轮包含网络构建和网络维持两大阶段。在每一轮里，由基站定义各节点以一个特定的相同发射功率进行数据转发，构建一个基于UDG(Unit Disk Graph)模型的分簇网络来感知周围环境信息并将信息可靠的由簇头-簇头多跳转发至基站的过程，本方案主要针对应用在任务艰巨、节点随机布置的一些场合，因此设计时需满足两个基本的约束条件：形成的簇头节点集可提供一个可靠的数据包多跳转发能力；本方案具备的能量有效性应该和现有的基于分簇的网络控制方案相当或者更好。为了满足这些约束，LEPN网络控制方案所确定的簇头最终形成一条连通的闭合回路保证信息成功多跳转发至基站，具有可靠性和能量有效性，因为基站节点获得信息转发路径是闭合回路，具备的冗余性以防止信号在传输过程由于链接失败而造成信息传输失败；而该方案的另一个优点是不需要节点的位置和方向信息，从而节约了节点的硬件成本投入。
2．1 LEPN网络构建阶段
    每一轮的LEPN网络构建阶段分为四个子过程，首先由基站设定本轮节点通信的发射功率，发起网络构建，接下来各个节点根据接收信号的衰减程度判断与信号发送者的距离以完成信息的收集，当每个节点都完成信息的收集，就进入了信息上报过程，直至基站，基站根据接收到的信息情况选择簇头节点集，再将包含簇头节点的消息逐层传递给网络中的每一个节点，节点通过接收到的信息来判断自己在接下来的几轮里是否成为回路中的簇头节点以承担环境信息监测和数据转发的任务还是普通簇头节点融合本簇内的监测数据再转发，或者普通节点。用(如图1)一个13节点的网络构建过程来简单描述(粗实线表示可以构成父子关系的簇首链接，细实线表示构成邻居关系的簇首链接，虚线表示构成簇首与簇内成员的链接)。

2．1．1 基站启动过程
    当无线传感器网络刚刚布置完毕或者基站接收到某节点请求网络重构的消息，并且基站中保存的簇头节点集已经使用完毕(若基站中尚有未使用的簇头节点集，那么网络构建阶段直接进入网络拓扑构建过程，这样有效的减少了网络构建代价)，基站进入了启动过程，首先它根据网络已运行的轮数设定下一轮各节点通信所采用的发射功率，基站节点以该发射功率广播hello消息(HM)并启动一个定时器1以等待它的子节点发来的HM，一帧完整的HM包含父节点标号、本节点标号、发射功率值、本节点的剩余能量以及充当簇头的最低剩余能量值，基站发出的HM里父节点的内容为基站本身的标号。见图1(a)，节点B，C，E，I，J，K，L，M接收到了基站A发来的HM。
2．1．2 节点信息收集过程
    一旦节点接收到HM，就表明网络构建阶段到了节点信息收集过程，如图1(a)中，节点B，C．E，I，J，K，L，M接收到一个HM，就开始判断本节点与HM发送者之间的相对距离，如果该距离小于本轮通信距离的一半(R／2)，则认定该HM发送者为自己的簇首节点，如节点I，K，L认定A为它们的簇首，于是它们向A发送一帧簇首确认消息，就进入了睡眠状态，关闭发射模块，等待网络的维持阶段到来再转换到数据监测状态。离A较远(相对距离大于R／2)的节点M，B，J，E，C，如果节点的剩余能量足够充当簇首节点的，则广播一帧包含本节点剩余能量信息的竞争簇首消息(CM)并启动一个定时器2(定时时间小于定时器1)，定时器2到达后，各节点对R／2范围内的节点信息进行判断，如果得知本节点能量最大，则设定自己为簇首节点并成为A的子节点，然后广播发送HM，如M，J，E，D，A将接收到B节点的HM，M，J认定B为簇首，见图1(b)，而A接收到B节点得知B为自己的子节点；节点C在定时器2结束后，发现R／2范围内无其他节点与之竞争，也设自己为簇首节点并认A为父节点发送HM；假使J也在E的R／2范围内，且能量高于E节点，E接收不到J的HM，却接收到其他父节点为A节点的HM(如B，C)时，E节点认定自己为簇首节点，并发送HM消息，此时BE，EC之间接收到HM消息，即认定相互之间为簇首间的邻居成员并计算存储他们之间的相对距离与邻居节点的剩余能量，见图1(c)；如果某节点的能量太小，不足以充当簇首节点，那么，它会选择离自己较近的一个簇首节点，加入该簇。某节点一旦有了父节点，就认定该节点处于被覆盖状态。而且当一个节点有了子节点，那么它就进入了活跃状态，开始等待信息上报过程的到来。按照这种方式，所有的节点都接收到HM消息，但是如图1(d)所示，节点G，F，H，C广播HM后，在设定的定时器1时间到达内未接收到任何认定它们为父节点的HM，因此它们认为信息收集过程结束，并由它们发起进入信息上报过程。
2．1．3 节点信息上报过程
    在节点信息上报过程中，只有充当父子关系的节点，同时，也是扮演簇首角色的节点，发送它的邻居序列给自己的父节点。在本例中，完成信息收集过程后，A，B，C，D，E，F，G，H成为簇首成员。簇首F是G的邻居。因此，簇首G发送{FG}以及FG的相对距离的消息给它的父节点D。这些节点的组合方式为构成一定性质的簇头-簇头链接的提供了可靠的信息，每个父节点都在等待着它的所有子节点发来的上报消息，再添加自己的信息，发送给自己的父节点。如簇首节点D接收到它的子簇头节点G发送来的消息后，它就发送有{FGD}，{FD}，{ED}路径信息给节点B，依次进行信息传递，最终的信息将汇聚至基站。当基站节点接收到所有子节点发来的上报信息，则网络构建进入了下一过程。在信息上报过程中，节点发送完上报消息后就进入睡眠状态，关闭发射模块以保存能量。
2．1．4 网络拓扑构建过程
    网络拓扑构建过程在基站节点上进行，当基站A接收到所有子簇头节点(BCE)发送来的上报信息，就开始对支路进行整合，如果两条数据通路有共同的节点，如{ABDF}和{AEFD}两条支路有两个共同的节点A，F，那么可以组合出一个具有闭合回路的数据通道ABDFEA，对于不同的回路也根据判断是否有共同节点而对它们进行整合成更大的闭合回路。一旦基站完成选择多个构成回路的簇头集，它开始为其他簇头节点以尽少的步数连接到某一回路簇头节点，在基站A处，将形成多个具有回路性质的簇头-簇头节点集，基站将选择其中一个簇头集信息广播给网络中的每一个节点。网络中的节点通过判断基站的广播信息(簇头-簇头之间数据转发的路由信息)，决定自己是充当回路簇头或支路簇头节点进行数据收集、融合、转发，或者充当普通簇内节点实现对周围环境的监测。至此进入了网络维持阶段。
2．2 LEPN网络维持阶段
    网络维持阶段，簇头将根据簇内的节点数目为每个簇内节点分配TDMA时间表。簇内节点持续采集周围环境信息，并在自己的通信时隙内以单跳通信的方式将数据传送给相应的簇头。为了有效节约节点能耗，普通节点的发送器在不属于自己通信的时隙进入睡眠状态；而簇头必须使自己的接收器时刻处于开启状态，以便接收簇内节点发送过来的所有数据。簇头节点接收到簇内所有的数据后，将对数据进行必要的数据融合处理，然后根据路由信息将数据经簇头-簇头多跳传输至基站。

3 仿真实验
    无线传感节点的能量有限性决定节点能量的高效使用是网络控制设计的首要目标，也是延长网络生命周期的一种有效手段。本文仿真设定在30 km×30 km的监测区域内，将200个节点随机分布，节点的通信半径在5～45 km内可调。为了便于计算节点收发信息的能量消耗，使用文献所描述的无线通信模型：
    以通信半径为d发射n比特的数据所需要的能量消耗：
   
    仿真参数如表1所示。LEPN协议运行过程节点的通信半径和网络运行轮数之间关系如图2所示。

    图3～图5分别显示了网络构建阶段的节点初始分布图、基站获得的父子关系链接图以及一个有效的簇头-簇头以及与普通节点之间关系的链接图。为了对比LEPN方案的有效性，本文分析了LEACH-C、MCLB算法的运行情况，并对比了网络生存周期、网络运行的能量消耗、网络构建代价等情况，如图6～图8所示。

    通常用网络第一个节点死亡的时间、一半节点死亡的时间和最后一个节点死亡的时间来分析网络的生存时间长短。因为基于分簇算法需要多个节点才能正常运行，因此本文中用60％的节点死亡时间代替最后一个节点死亡时间。如图6所示，MCLB的第一个节点死亡比较早，这是因为MCLB里有一部分簇头节点一直承担数据转发任务而快速消耗能量，而LEACH-C和LEPN的第一个节点的死亡时间相差不多，从图中可见在相同节点死亡时LEPN比MCLB和LEACH-C经历的轮数都要多，从而验证了该方案可以更有效地延长了网络的生存周期。
    图7显示了基站在网络运行过程接收到的监测数据包的总数，在LEACH-C、MCLB和LEPN协议中每个监测数据包均经过单跳传输至簇头，然后在簇头节点经过数据融合，LEACH-C协议中簇头将处理过的信息经单跳发给基站，而MCLB和LEPN经簇头间多跳并数据融合再传输至基站，这样大大地减少了传输到基站的数据包数量。由图7可以看出LEPN优于LEACH-C和MCLB。

    图8显示了平均每轮网络构建阶段的能量消耗，由本论文所提出的方案无需在每一轮的开始都经历构建阶段中比较耗能的节点信息收集过程和节点信息上报过程，因此大大减少了本方案的网络构建代价，LEPN的网络构建代价只有LEACH-C的74．6％，MCLB的47．1％。

4 结语
    本文介绍了一种低能耗的节点位置未知的网络控制方案，根据不同的网络运行轮数设定网络中节点的通信半径，使得网络具有更好的能量有效性。基站通过构建阶段中的启动过程、节点信息收集过程和节点信息上报过程，获得了整个网络节点的相对位置分布，然后基站整合节点信息支路，得到若干具有回路链接的簇头节点集，保证网络在数据传输上具有更好的可靠性。本文所提出的方案，通过仿真实验与同类典型算法LEACH-C，MCLB进行比较，表明LEPN可以延长网络的生存周期，减少监测数据包总数和有效的降低网络构建代价。但是本文提出的方案中，网络运行轮数与通信半径之间的关系暂缺乏一定的依据，在相同的网络运行轮数下，网络节点采用不同的通信半径，较大地影响了运行结果，在接下来的工作中，将对该方面进行更深入的探讨。