一种适用于无线传感器网络的组播路由的组播树调整方法

具体实施方式

下面结合附图对本发明做进一步的说明。

本发明是一种适用于无线传感器网络的组播路由的组播树调整方法，该调整方法可以对通过任意策略构建的无线传感器网络组播路由的组播树进行调整优化，首先使用增叶策略来优化该组播树，以减少组播过程的能耗；最后使用旁路休眠策略实现该组播树中各节点的能耗均衡，延长整个无线传感器网络的存活时间。

为了方便陈述本发明的组播树调整方法，对于组播树中的任意一个节点N_i(简称为任意节点N_i)将存储如下信息：

①父节点在本发明中，该父节点是任意节点N_i的父节点。

在本发明中，如果任意节点N_i为根节点，则表明该N_i不会有父节点。

②子节点集

在本发明中，该子节点集中存储的是任意节点N_i的所有子节点编号，用数学表达形式为其中，表示节点N_i的第一个子节点，表示节点N_i的第二个子节点，表示节点N_i的第l个子节点，也表示节点N_i的任意一个子节点。

在本发明中，如果节点N_i是叶节点，则节点N_i的子节点集为空集合。相应地，当节点N_i的子节点集不为空集合时，又称节点N_i为非叶节点。

③备用父节点集

在组播树维护过程中，备用父节点集中存储的是任意节点N_i的备用父节点编号，用数学表达形式为其中，表示节点N_i的第一个备用父节点，表示节点N_i的第二个备用父节点；表示节点N_i的第m个备用父节点，也表示节点N_i的任意一个备用父节点。

在本发明中，当任意节点N_i没有备用父节点时，则节点N_i的备用父节点集为空集合。

在本发明中，任意节点N_i在加入组播树之前，子节点集和备用父节点集都为空集合。当任意节点N_i为根节点时，可用TNode标记，如图1所示。

一般地，在一棵组播树中，节点可能会存在多重身份，即一个节点可能是另外一个节点的子节点，同时，又可能是其他某些节点的父节点或备用父节点。

参见图1所示的一个具有分层结构的组播树结构，在该组播树中：

A节点是根节点(代表传感器网络中的基站节点)，B₁节点、B₂节点、N_j节点、节点、……、B_b节点分别为A节点的子节点，相应地，A节点就是B₁节点、B₂节点、N_j节点、节点、……、B_b节点的父节点；

C₁节点、C₂节点、……、C_c节点分别是B₁节点的子节点，相应地，B₁节点就是C₁节点、C₂节点、……、C_c节点的父节点；

D₁节点、D₂节点分别是B₂节点的子节点，相应地，B₂节点就是D₁节点、D₂节点的父节点；

E_e节点是N_j节点的子节点，相应地，N_j节点就是E_e节点的父节点；

N_i节点是节点的子节点，相应地，节点就是N_i节点的父节点；

F_f节点是B_b节点的子节点，相应地，B_b节点就是F_f节点的父节点；

G₁节点、G₂节点分别是E_e节点的子节点，相应地，E_e节点就是G₁节点、G₂节点的父节点；

节点、节点、……、节点分别是N_i节点的子节点，相应地，N_i节点就是节点、节点、……、节点的父节点；

G₁节点和G₂节点在D₂节点的通信范围内，但D₂节点并不是G₁节点和G₂节点的父节点，则D₂节点为G₁和G₂节点的备用父节点；

C₁节点、C₂节点、……、C_c节点、D₁节点、D₂节点、F_f节点以及节点、节点、……、节点都没有子节点，则它们是叶节点；

A节点、B₁节点、B₂节点、节点、……、B_b节点以及N_i节点都有一个或多个子节点，则它们是非叶节点。

在本发明中，对于网络中的任意两个节点N_i和N_j，组播树的维护执行如下维护执行步骤：

维护执行步骤1)：网络中的任意节点N_i，如果N_i是某些节点的父节点(简称父节点N_i)，即N_i的子节点集不为空集合，则N_i会周期性地通过广播的方式发送子节点维护报文以及接收其任意子节点的应答报文并根据在该周期内收到子节点应答报文的情况不同，执行维护执行步骤5)；同时，网络中的每个节点都会接收网络中的子节点维护报文，当收到子节点维护报文时，执行如下的维护执行步骤2)；当一个维护周期结束时，执行维护执行步骤6)；

维护执行步骤2)：当另一任意节点N_j收到子节点维护报文时，首先根据CMT报文中的判断节点N_i是否为自己的父节点如果是，则执行维护执行步骤3)，否则执行维护执行步骤4)；维护执行步骤3)：节点N_j检查所收到的子节点维护报文中的子节点集判断自己的编号是否在子节点集中，如果是，表示节点N_i是节点N_j的父节点，则节点N_j向节点N_i发送一个应答报文用于维持组播树结构；否则，执行维护执行步骤7)，加入组播树；

维护执行步骤4)：发送子节点维护报文的节点N_i不是节点N_j的父节点，节点N_j将节点N_i加入到它的备用父节点集中；

在本发明中，由于父节点对子节点发送子节点维护报文是采用广播的方式，所以每个节点都有可能接收到不是自己的父节点(非父节点)发送的子节点维护报文。所以，对于任意另一节点N_j，如果N_j接收到了N_i发送的子节点维护报文CMT，那么能够得知N_j在N_i的通信范围之内。如果N_j不在N_i的通信路径(在本发明中，节点N_i的通信路径是指组播报文从根节点传至N_i所经过的节点序列)里，称N_i为N_j的一个备用父节点。

维护执行步骤5)：当节点N_i收到了其它任意子节点的应答报文，则维持N_i与的父子关系不变；

维护执行步骤6)：在一个维护周期结束后，节点N_i扫描其子节点集对于在该维护周期内未收到应答报文的子节点该N_i将把从中删除，结束与这些子节点的父子关系；如果子节点在一个维护周期内没有收到来自其父节点N_i的子节点维护报文，则子节点执行“节点加入组播树”的处理方式。

在本发明中，对于网络中的任意节点N_i，当其需要加入一个组播树时，则执行如下处理步骤：

步骤001：设置节点N_i的子节点集和备用父节点集均为空集合；

步骤002：节点N_i广播父节点请求报文其中，TYPE_PRQ表示报文类型为父节点请求报文，表示节点N_i的编号；

步骤003：组播树中的另一任意节点N_j收到报文后，向节点N_i发送子请求报文其中，TYPE_CRQ表示报文的类型为子请求报文，是节点N_j的编号。

步骤004：节点N_i收到后，向节点N_j回复应答ACK，并将设置为N_j，从而节点N_i成为节点N_j的子节点。

在本发明的组播过程中，所有非叶节点既发送组播报文也接收组播报文，但基站、非叶节点除外，因为基站仅发送组播报文，叶节点只接受而不转发组播报文。本发明采用增叶策略对组播树的结构进行优化，在不影响网络连通性的情况下，将非叶节点转换为叶节点，从而减少组播报文的转发次数，减低系统的总能耗。

组播树维持一段时间后，部分节点能量过低。在本发明中，采用组播树的能量均衡策略进行休眠状态判断。如果节点是可替代的，则进入休眠状态，从而防止节点过早死亡，以增加整个无线传感器网络的存活时间。

在本发明中，通过以下算法实现组播树的优化。对于网络中的任意节点N_i，它有l(l＝2，即节点G，节点H)个子节点其优化步骤如下：

步骤101：节点N_i检查其备用父节点集是否为空集合，如果不是，表示节点N_i存在备用父节点，则节点N_i向它的父节点发送发现备用父节点报文其中，TYPE_BPD表示报文类型为发现备用父节点报文，是节点N_i的节点编号。同时，如果节点N_i的任意子节点也会检查的备用父节点集如果不为空，会向它的父节点(即节点N_i)发送发现备用父节点报文，节点N_i会接收来自它的所有子节点的发现备用父节点报文；

在本发明中，由于父节点对子节点发送子节点维护报文是采用广播的方式，所以每个节点都有可能接收到非父节点发送的子节点维护报文。所以，对于任意节点N，如果N接收到了其他任意节点Q发送的子节点维护报文CMT，那么能够得知N在Q的通信范围之内，Q为非叶节点(只有父节点发送子节点维护报文CMT)。如果N不在Q的通信路径(在本发明中，节点Q的通信路径是指组播报文从根节点传至Q所经过的节点序列)里，称Q为N的备用父节点BP。

步骤102：当节点N_i收到它的任意子节点的发现备用父节点报文BPD后，在N_i的子节点集中标记为可释放状态。

步骤103：如果节点N_i的所有子节点均处于可释放状态的，那么节点N_i向其所有子节点发送释放请求报文其中，TYPE_RRQ表示报文类型为释放请求报文，是N_i的节点编号，进入等待释放状态。

步骤104：子节点收到节点N_i的广播释放请求报文RRQ后，向其备用父节点集中的所有备用父节点发送父请求报文其中，TYPE_PRQ表示报文类型为父请求报文，是节点的节点编号。

步骤105：对于节点的任意备用父节点如果它并非自由节点且未处于等待释放状态，则向节点回复应答报文ACK；否则，向节点回复否定回答报文NAK。

步骤106：如果子节点收到备用父节点发送的应答报文ACK，则向父节点N_i发送应答报文ACK，并将收到的第一个应答报文ACK的发送备用父节点标记为如果节点收到的所有备用父节点的报文均为否定回答报文NAK，向N_i发送否定回答报文NAK。

步骤107：节点N_i收到所有子节点的应答报文ACK后，向其所有子节点发送释放子节点报文其中，TYPE_RNF表示报文类型为释放子节点报文，是节点N_i的节点编号。子节点收到释放子节点报文RNF后成为备用父节点的子节点。优化前是非叶节点的节点N_i则成为叶节点。由于为非叶节点且消息广播发送，让节点做节点的子节点，并不增加BP_i能量消耗。N_i节点变为叶节点，降低了能耗。所以系统总能耗降低了。

对于无线传感器网络组播路由而言，有以下几个特点：(1)发送报文远比接收报文消耗能量，能耗正比于报文发送次数；(2)可以采用广播的方式，将消息一次发给自己所有的子节点；(3)广播报文和单播报文具有相同的能耗。对于每一个组播报文的转发，每个中间节点需要广播一次报文，而叶节点只需要接收报文。因此，为了降低系统的总能耗，需要让尽可能多的节点成为叶节点。如图2所示，图中非叶节点的数目比图1减小了1个，当有组播报文需要通过该网络的时候，图2所示的组播树将比图1中组播树少转发1次报文，从而减小了能耗。

当网络中某些节点由于长期工作能量过低时，为了防止节点过早的死亡，需要调整组播树，使该节点进入休眠状态，或者仅接收组播报文。

在本发明中，采用旁路休眠策略进行能量均衡处理，对于网络中的任意节点N_j，步骤如下：

步骤201：节点N_j发现自己能量低于预设的阈值时，向根节点TNode发送休眠请求报文其中，TYPE_SRQ表示报文类型为休眠请求报文，为N_j的节点编号，为节点N_j的剩余能量值。

步骤202：根节点TNode收到休眠请求报文SRQ后，广播该条SRQ报文。

对于组播树中的任意一个节点N_i，节点N_i收到SRQ报文后(该报文来自根节点TNode的广播，或者来自步骤202-2、步骤202-3和步骤202-4的广播)，有如下处理子步骤：

步骤202-1：如果N_i就是节点N_j，则丢弃报文；否则，转步骤202-2。

步骤202-2：如果N_i为非叶节点，广播该报文；否则，转步骤202-3。

步骤202-3：N_i为叶节点，如果节点N_i的剩余能量值不大于SRQ报文中的即丢弃该报文；否则广播该报文。转步骤202-4。

步骤202-4：如果N_i为N_j的子孙节点，且不是N_j的子节点，则广播该报文；否则，转步骤202-5。

节点N_i为节点N_j的子孙节点是指，从根节点TNode到节点N_i的组播路径中包含节点N_j。由于节点N_j不对SRQ转发，所以该报文不可能通过组播得到。

步骤202-5：如果N_i为N_j的子节点，则广播该报文，并向N_j节点回复应答报文ACK。

步骤203：如果N_j收到所有子节点的应答报文ACK，进入休眠状态，执行步骤204；否则节点N_j不能进入休眠状态而继续工作。

步骤204：N_j的子孙节点脱离了组播树，重新申请加入组播树。

在本发明中，节点可能收到多个节点发送的CRQ报文，此时只能向一个节点发送应答报文。可以选择通讯路径最短且接收到CRQ报文时间最早的节点。通过使用以上方法，当节点N_j进入休眠状态前，可以使N_j的每个子孙节点都能找到新的父节点，保证了网络的覆盖度。

经过旁路休眠策略调整后，组播树的变化如图2中虚线所示：B₂节点成为叶节点，D₂节点成为N_j节点的子节点，E_e节点成为D₂节点的子节点。图中可以看出叶节点的个数增加了，减少了报文转发次数，从而降低了无线传感器网络的总能耗。

本发明中各个字母的物理意义为：