基于二叉树的无线传感器网络分簇能量均衡路由确定方法

1.一种基于二叉树的无线传感器网络分簇能量均衡路由确定方法，其特征在于操作步骤如下：
a.在某一轮的形成簇的阶段时，每一个节点都先处于等待状态，并生成一个随机变量R＝rand(0，1)；根据网络中每个节点此时自身的剩余能量Enow，每个节点初始时的最大能量Einitial，在过去的所有轮数中该节点当选过簇头的次数Times_Head，网络中簇头节点所占总节点数目的百分比P和当前的轮数r，以及整个传感器网络到本轮为止所经历的循环次数生成每个节点在本轮的阈值T′(n)，如果某个节点产生的R小于该节点的T′(n)，则当选为本轮的簇头；如果某个节点产生的R大于该节点的T′(n)，则成为本轮的簇头的成员节点；
b.当选的簇头节点向网络中其它节点广播各自簇头广告包，在广告包中有一个剩余能量cost域是用来保存簇头的Enow，供非簇头选择自己的簇所用；在整个广播的过程中，其它非簇头节点全部处于接收状态，用来接收来自簇头的数据；非簇头节点有可能会收到来自不同簇头节点的广告包，根据簇头节点的剩余能量cost域，非簇头节点收到簇头信号的强弱S_intensity，得到不同簇头节点的COST，选择COST最大的簇头节点作为自己的簇头节点；
c.成员节点选定自己的簇头后，设定一个加权的随机退避定时器，权值的设定依赖于节点所收到的簇头信号的强弱，也就是根据成员节点与簇头之间的距离dCommunication与每个节点的通信半径DMax，求出定时时间Delay，定时时间到，每个成员节点向选定的簇头发出应答包，数据包的帧格式中要包含成员节点的ID；
d.簇头节点根据时间先后，会收到来自不同成员节点的应答包，基于成员节点数目，会产生一个TDMA时隙表；时隙表的建立与应答包到达的先后顺序有关；建立一棵二叉树的数据结构，来安排成员节点的标示ID放入二叉树的每个结点；越先到达的应答包所对应的成员节点在整个二叉树内就要越靠近根结点也就是簇头节点，即最先到达的2个应答包对应的成员节点作为簇头的2个子节点也就是根结点的2个子结点，随后到达的4个应答包对应的成员节点作为刚才2个子结点的子结点，以此类推，直到将所有的应答包对应的成员节点全部分配完毕；生成的二叉树对应簇内多跳通信时，数据发送的方向，数据总是由子结点向父结点发送；
e.二叉树建立完毕之后，对其进行后序遍历，将遍历的结果依次放入TDMA时隙表，并将TDMA时隙表和二叉树的结构广播给簇内所有成员节点；
f.每个成员节点收到TDMA时隙表后，在时隙表内查找自己的标示ID；在属于自己的时隙范围内，根据收到的二叉树的结构将数据发送给二叉树数据结构中的父结点；在不属于自己的时隙范围时，关闭射频模块以减少能量消耗；
g.二叉树后序遍历序列的最后一个结点必定是根结点也就是簇头，所以当TDMA时隙运行到最后一个时隙时，簇头将前面若干时隙中收到的数据发送给汇聚节点，本轮结束，进入下一轮。

技术领域\n本发明涉及一种无线传感器网络的路由确定方法，特别是一种基于二叉树的无线传感器网络分簇能量均衡路由确定方法。\n背景技术\n无线传感器网络是由一组传感器节点以自组织方式构成的无线网络，其目的是协作地感知、采集和处理网络覆盖的地理区域中被监测对象的信息，并发布给观察者。它综合了传感器技术、嵌入式技术、分布式信息处理技术和通信技术，在军事、工业、医疗、交通、环保等诸多方面有着巨大的应用价值。由于无线传感器网络节点数目众多，每个节点的能量有限，处理能力、存储能力和无线通信能力相对有限。如何高效利用这些能量和资源，建立合适的路由，尽可能地延长网络生存周期，成为无线传感网研究的热点之一。相关研究表明，随着集成电路工艺的进步，处理器和传感器模块的功耗变得很低，绝大部分能量消耗在无线通信模块上，因此无线通信的次数和通信距离直接影响了整个网络的路由，也决定了整个网络的能量消耗和生存周期。\n无线传感器网络通常使用多跳技术，每个节点监测采集的数据沿着其他节点逐跳地进行传输，在传输过程中数据可能被路由中的多个节点处理、存储和转发，经过多跳后路由到汇聚节点，最后通过汇聚节点传达给用户。这样选择路由，必然导致部分节点因为负载过重而提前失效，从而将整个网络分割成若干个互不相连的孤岛，缩短了整个传感器网络的生存期。因此，在设计传感网路由中，提出了分簇确定方法，其基本思想是把网络划分成互不重叠的若干部分(簇)，使得数据通信形成簇内通信和簇间通信的不同层次，每个簇选出一个节点负责簇的管理，并形成全网的骨架，周期性动态成簇，随机产生簇头，使得各节点等概率地担任簇头，使得网络中的节点相对均衡地消耗能量，延长网络生存周期。目前代表性的分簇确定方法有Leach(LowEnergyAdaptive Clustering Hierarchy)法等。\n尽管Leach法的设计初衷是使各节点等概率地分担簇头任务，相对均衡地分担负荷。但是实际上如此设计路由，依旧会导致部分节点能量提前耗尽。这是因为产生簇头的随机性导致整个网络中簇头分布的不均匀，或者因为随机选择簇头时，仅仅考虑了概率因素，故有可能存在某一节点的剩余能量已经很小但仍被选为簇头节点的情况，并且由于簇内进行单跳通信，远距离的单跳通信会导致能量最快能以四次方的速率被快速消耗殆尽。\n发明内容\n本发明的目的在于针对现有技术的不足，采用了数据结构中的二叉树结构和它的后序遍历，结合传感网节点的能量均衡机制，提出一种基于二叉树的传感网分簇能量均衡路由确定方法，该方法能够有效地减少和均衡整个无线传感器网络中节点的能量消耗，延长整个网络的生存周期。\n为实现上述目的，本发明的构思如下：\n能量均衡机制中，节点根据自身的剩余能量和节点过去被选为簇头的情况对产生的随机数进行调整，这样，每个节点都能够考虑到自身的能量因素而自适应地被选为簇头，避免出现剩余能量很小的节点被随机选举为簇头。\n树是计算机科学中的模拟现实树干和树枝的一种，如同树的树根一样，树结构都有一个根结点，根结点之下如同树的树枝一样，可以拥有0到n个子结点，也就是根结点的分支。树结构的种类非常多，使用最广泛的就是二叉树，，一颗二叉树的节点最多只能拥有2个子结点。可见，每个节点和它结节点之间的关系如同簇头和它的成员节点之间的层次关系非常类似，因此二叉树结构用在无线传感器网络路由中的分簇多跳确定方法具有很好的优势。\n在本发明提出的方法中，在簇内采用多跳通信，避免了由于单跳通信导致的远距离通信大大消耗节点能量的情况，减轻了最远节点的能量消耗负担，通过相互之间的简单交流使整个网络群体达到复杂的最优，适用于大规模的无线传感网。\n根据上述发明构思，本发明所采用的技术方案如下：\n一种基于二叉树的无线传感器网络分簇能量均衡路由确定方法，其特征在操作步骤如下：\n(1)在某一轮的形成簇的阶段时，每一个节点都先处于等待状态，并生成一个随机变量R，R＝rand(0，1)；根据网络中每个节点此时自身的剩余能量Enow，每个节点初始时的最大能量Einitial，在过去的所有轮数中该节点当选过簇头的次数Times_Head，网络中簇头节点所占总节点数目的百分比P和当前的轮数r，以及整个传感器网络到本轮为止所经历的循环次数生成每个节点在本轮的阈值T′(n)，如果某个节点产生的R小于该节点的T′(n)，则当选为本轮的簇头；如果某个节点产生的R大于该节点的T′(n)，则成为本轮的簇头的成员节点。\n(2)当选的簇头节点向网络中其它节点广播各自簇头广告包，在广告包中有一个剩余能量cost域是用来保存簇头的Enow，供非簇头选择自己的簇所用。在整个广播的过程中，其它非簇头节点全部处于接收状态，用来接收来自簇头的数据。非簇头节点有可能会收到来自不同簇头节点的广告包，根据簇头节点的剩余能量cost域，非簇头节点收到簇头信号的强弱S_intensity，得到不同簇头节点的COST，选择COST最大的簇头节点作为自己的簇头节点。\n(3)成员节点选定自己的簇头后，设定一个加权的随机退避定时器，权值的设定依赖于节点所收到的簇头信号的强弱，也就是根据成员节点与簇头之间的距离dCommunication与每个节点的通信半径DMax，可以求出定时时间Delay，定时时间到，每个成员节点向选定的簇头发出应答包，数据包的帧格式中要包含成员节点的标示ID。\n(4)簇头节点根据时间先后，会收到来自不同成员节点的应答包，基于成员节点数目，会产生一个TDMA时隙表。时隙表的建立与应答包到达的先后顺序有关。建立一棵二叉树的数据结构，来安排成员节点的ID放入二叉树的每个结点。越先到达的应答包所对应的成员节点在整个二叉树内就要越靠近根结点也就是簇头节点，即最先到达的2个应答包对应的成员节点作为簇头的2个子节点也就是根结点的2个子结点，随后到达的4个应答包对应的成员节点作为刚才2个子结点的子结点，以此类推，直到将所有的应答包对应的成员节点全部分配完毕。\n(5)二叉树建立完毕之后，对其进行后序遍历，将遍历的结果依次放入TDMA时隙表，并将TDMA时隙表和二叉树的结构广播给簇内所有成员节点。\n(6)每个成员节点收到TDMA时隙表后，在时隙表内查找自己的标示ID。在属于自己的时隙范围内，根据收到的二叉树的结构将数据发送给二叉树数据结构中的父结点。在不属于自己的时隙范围时，关闭射频模块以减少能量消耗。\n(7)二叉树后序遍历序列的最后一个结点必定是根结点也就是簇头，所以当TDMA时隙运行到最后一个时隙时，簇头将前面若干时隙中收到的数据发送给汇聚节点，本轮循环结束，进入下一轮。\n本发明与现有技术相比较，具有如下的优点：在每轮的路由建立阶段，根据能量均衡机制和节点过去的情况，使得剩余能量较大并且当选次数较少的节点成为簇头的概率大大提高，相对平均地使各节点分担了网络负荷，避免了某一节点的剩余能量已经很小但仍被选为簇头节点的情况。同时在路由建立阶段，每个非簇头节点选择自己的簇头时，也非完全根据信号强弱，而是根据能量均衡机制和通信距离，选择了COST较大的簇头，保证了在通信距离和剩余能量中取得更好的平衡。最后在簇内进行多跳通信时，在路由建立阶段的TDMA时隙分配中，根据与簇头的距离远近先后加入簇头，簇头根据到达时间的先后分配二叉树，并根据对二叉树的后序遍历分配每个节点工作的时隙，实现了通信距离上的最小化，有效地降低了一部分相对离簇头较远的节点的能量消耗。\n本发明能够全局平衡网络节点间的能量消耗，避免了出现由于部分节点过早失效而整个网络被分割成若干个互不相连的孤岛的情况，延长了整个传感器网络的生存周期，并且本方法较为简单，易于实现，可用于各种以数据为中心的无线传感器网络的应用场合，具有较好的社会效益和经济效益。\n附图说明\n下面结合附图和实例对本发明做进一步说明。\n图1为某一轮网络还未成簇的示意图；\n图2为网络在成簇之后的示意图；\n图3为簇内多跳通信的示意图；\n图4为簇内TDMA时隙分配建立的二叉树示意图；\n图5为整个网络形成若干个多跳的簇，进行数据传输的示意图。\n具体实施方式\n本发明的一个优选实施例子结合附图详述如下：\n在本实施例中，在选择路由时基于二叉树的无线传感器网络分簇能量均衡路由确定方法，实现了网络系统能量消耗的有效降低和均衡，延长了整个网络的生存周期。\n首先整个网络系统满足如下的假定：\n(1)每一个节点都有唯一标示(唯一ID)，并且初始的能量都相同。\n(2)每一个节点都具有相同的无线覆盖半径，并且是对称信道。无线电信号在各个方向上能量消耗完全相同，并且采用一阶无线电模式。\n建立路由的具体方法如下所示：\n(1)在其中某一轮的形成簇的阶段时，每一个节点都先处于等待状态，并生成一个随机变量R，\nR＝rand(0，1)\n(2)此时，参见图1，节点B的剩余能量为EB，节点C的剩余能量为EC。并且可以根据公式计算出此轮C和D的门限阈值。\n其中：Enow是节点此时的剩余能量，Einitial是每个节点的初始能量，Times_Head是在过去的所有轮数中该节点当选过簇头的次数。\n公式不仅考虑了节点的能量因素，采用正比例函数降低了将能量过小的节点成为簇头的概率，同时也考虑了该节点过去曾经当选过簇头的次数与整个网络到本轮为止所经历的循环次数，增加了本次循环中还未当选簇头的节点成为本轮簇头的概率。\n(3)节点B的随机变量RB和节点C的随机变量RC均小于它们的门限阈值，均当选为本轮簇头。而节点A因为能量过低或者已经在本次循环中担任过簇头，导致RA大于阈值而没有成为本轮的簇头。\n(4)节点B和C还有网络中其它簇头节点，向网络中其它节点广播各自簇头广告包。在整个广告的过程中，运用CSMA中的MAC层协议，所有的簇头节点都用同样的发射功率发送广告包。在广告包中有一个cost域是用来保存簇头的Enow，供非簇头选择自己的簇所用。\n(5)在步骤(4)中，其他非簇头节点的射频模块始终处于接收状态，用于接收来自簇头节点的广告消息。每个非簇头节点都有可能会收到来自不同簇头节点的广告包。在图1中，节点A处在簇头B和簇头C的通信半径中，因此都收到了这2者的广告包。\n(6)节点A根据公式求出来自不同簇头的COST，并选择COST较大的那个簇头加入。其中，cost是簇头节点的剩余能量，S_intensity是非簇头节点收到簇头信号的强弱，因为所有的簇头用同样的发射功率发送广告包，所以S_intensity也代表了非簇头节点距离簇头的距离。公式不仅考虑了信号强弱，同时也考虑了簇头节点剩余能量，得到了簇头距离与能量之间的均衡，降低了离得很近但是能量偏低的簇头成为该节点簇头的概率。节点A一共收到簇头B和C的COST，虽然从距离上而言A更靠近B，但计算了COST之后，选择C作为自己的簇头加入，这样可以在能量和距离上获得更好的均衡，平衡了簇头之间的能量消耗，此时整个网络系统形成的各个簇如图2所示。\n(7)节点A选定簇头后，设定一个加权的随机退避定时器，权值的设定依赖于节点A所收到的簇头信号的强弱也就是与簇头之间的距离。\n$\mathrm{Delay}=\exp (-\frac{d_{\mathrm{Communication}}}{D_{\mathrm{Max}}})$\n其中：dCommunication是节点与自己的簇头之间的距离，DMax是每个节点的通信半径。由此可见距离簇头越近的节点，定时时间越短。在各自的定时时间到达之后，簇中每个节点都向簇头发出应答包，数据包的帧格式中要包含节点的ID。\n(8)簇头在步骤(6)和步骤(7)内一直处于休眠状态，以便减少能量消耗。但收到第一个非簇头节点的应答包后，会根据簇头的剩余能量设置一个定时时间，其中定时时间和剩余能量成正比，即剩余能量越大的节点它的定时时间会越长。在定时时间内，会收到来自簇内的各个节点的应答包。按照时间先后顺序，把这些应答包存入自己的buffer内。定时时间到了以后，关闭簇头的射频接收模块，此时就算收到应答包，也直接丢弃，而不存入buffer。\n(9)簇头在收到簇内节点的报到消息后，基于成员节点数目，会产生一个TDMA时隙表，告诉成员在什么时刻可以发送数据，什么时刻进入休眠状态以减少能量消耗。TDMA时隙表的建立与(8)中的应答包到达的先后顺序有关。需要建立一棵二叉树的数据结构，buffer内越先到达的应答包所对应的节点在二叉树内就要越靠近根节点，也就是最先到达的2个应答包对应的节点作为簇头的2个子节点也就是根节点的2个子节点，随后到达的4个应答包对应的节点作为刚才2个子节点的子节点，以此类推，直到将buffer内所有的应答包对应的节点全部分配完毕。\n(10)二叉树建立完毕之后，对其进行后序遍历，将遍历的结果作为TDMA时隙表，广播给簇内所有节点。在发送阶段，属于自己的时隙内，成员节点把数据发送给簇头，而在不属于自己的时隙内，关闭射频模块以节约能量。而簇头节点在步骤(10)一直处于接收状态，用于接收来自不同成员节点的数据。当一轮的数据传输完毕之后，进入下一轮的路由建立阶段，重新回到步骤(1)。\n如图3所示，节点A和节点D都是节点C的成员节点，它们的应答包如步骤(8)，先后到达簇头C。由于A距离C的通信距离更近，按照步骤(7)，产生的延时更短，因此C更早地收到来自A的应答包，随后不久又收到来自D的应答包。根据步骤(9)，由于A的应答包早于D的应答包，所以A在二叉树内可以作为D的父结点，生成的二叉树参见图4。\n对二叉树进行后序遍历，每一路分支上层数越是大，也就是越靠近叶节点的话，遍历时其时隙分配越靠前，D是A的子节点，因此D在整个TDMA的时隙表中的位置肯定比A靠前，也就是D先向A发送数据，接着A将自身的数据与D的数据一起发送给簇头C。\n节点C与节点D之间的距离为x，节点C与节点A之间的距离为y，节点A与节点D之间的距离为z，采用一阶无线电模式，如果按照原有一跳通信的方式的话，在数据发送阶段所消耗的能量如下：\nD发送kbit数据所消耗的能量为：Esend＝k×Estatic+k×εamp×x2\nA发送kbit数据所消耗的能量为：Esend＝k×Estatic+k×εamp×y2\nC接收2kbit的数据所消耗的能量为：Erecv＝2k×Estatic\n三个节点一共消耗能量：Etotal＝4k×Estatic+k×εamp×(x2+y2)\n其中：k×Estatic＜＜k×εamp×d2，因此Etotal＝k×εamp×(x2+y2)\n如果采用多跳通信并根据二叉树分配TDMA时隙的话，在数据发送阶段所消耗的能量如下：\nD发送kbit数据所消耗的能量为：Esend＝k×Estatic+k×εamp×z2\nA发送2kbit数据所消耗的能量为：Esend＝2k×Estatic+2k×εamp×y2\nC接收2kbit的数据所消耗的能量为：Erecv＝2k×Estatic\n三个节点一共消耗能量：Etotal＝5k×Estatic+k×εamp×(z2+2y2)\n其中：k×Estatic＜＜k×εamp×d2，因此Etotal＝k×εamp×(z2+2y2)\n如图2所示，显而易见，x2＞y2+z2，因此采用多跳通信并且根据二叉树分配时隙，不论是最远端的叶节点还是整个簇，消耗的能量都大大降低了。另外，单跳通信时，发送距离增加到一定长度，发送方还需要消耗额外功率来弥补多径衰弱的影响，此时需要把距离的平方变为四次方，这更体现了采用多跳通信并利用二叉树分配TDMA时隙对于能量消耗的合理利用。