带有局部簇重构的非均匀分簇路由算法.pdf

(19)中华人民共和国国家知识产权局*CN102970723A*(12)发明专利申请(10)申请公布号CN102970723A(43)申请公布日2013.03.13(21)申请号201210417357.0(22)申请日2012.10.26(71)申请人合肥工业大学地址230009安徽省合肥市屯溪路193号(72)发明人唐昊刘静苗刚中周雷洪薇刘和来张芹(74)专利代理机构安徽合肥华信知识产权代理有限公司34112代理人余成俊(51)Int.Cl.H04W40/10(2009.01)H04W40/02(2009.01)权利要求书权利要求书2页2页说明书说明书44页页附图附图22页(54)发明名称带有局部簇重构的非均匀分簇路由算法(57)摘要本发明公开了一种带有局部簇重构的非均匀分簇路由算法，根据节点到达汇聚节点的跳数对网络划分层次,综合考虑节点剩余能量和位置等因素的影响,在每个层次中通过竞选方式产生簇头，在每轮的数据传输阶段,根据距离汇聚节点的远近程度,各个层次以不同的频率在本层内部进行局部的簇重构,从而减少因簇重构产生的能量消耗。最后,构建了多跳传输路由负责簇内和簇间的数据转发。本发明能有效地均衡网络负载和延长网络生命周期。CN102973ACN102970723A权利要求书1/2页1.一种带有局部簇重构的非均匀分簇路由算法，其特征在于，通过基于权值的竞选方式产生簇头，控制簇头与簇成员的通信范围形成规模不同的簇，在每一轮的数据传输阶段，以层次为单位按照不同的频率进行局部的簇头重选；具体包括以下步骤：（1）局部信息收集：从每一轮的建立阶段开始，采用洪泛法算法的方法使所有节点获取基本的局部信息，每一个节点只需要通过一次标志消息的转发就可以获得其近似的位置信息及邻居节点的信息；（2）候选簇头的选取：在选择剩余能量较高的节点作为候选簇头的基础上，提出一种探索策略：即在每个网络层次中增加若干个剩余能量较低的节点成为额外的候选簇头；（3）最终簇头的产生：在选择竞选权值时综合考虑节点的剩余能量和邻居节点的信息，选择出尽可能处于中心位置的簇头；（4）局部簇重构机制：以轮为单位周期性的在整个网络中进行簇头重选，在稳定阶段，每个网络层次以不同的频率在本层内部进行局部的簇头重选。2.根据权利要求1所述的带有局部簇重构的非均匀分簇路由算法，其特征在于，步骤（1）所述洪泛法算法是Sink节点用一个较小的发射功率向网络广播一个HELLO消息，由网络中只有最靠近Sink节点的节点开始标志消息的转发，具体的操作步骤如下：Step1如果该节点第一次收到HELLO消息，转到Step2；否则，转到Step5；Step2如果HELLO消息来自Sink节点，转到Step3；如果来自节点j，转到Step4；Step3设Hi=1，转到Step6；Step4把节点j设为上跳节点，令Hi=Hj+1；Step5根据接收到的信号强度计算出dij，并与节点j的ID一起保存至Si；Step6判断该节点是否转发过HELLO消息，如果没有，转发此消息；否则，继续接收其他节点发送来的消息；最终，通过HELLO消息的接收和发送，每个节点获得其到达Sink节点的跳数以及其周围邻居节点的信息，节点i根据其跳数被划分到相应的网络层次中。3.根据权利要求1所述的带有局部簇重构的非均匀分簇路由算法，其特征在于，步骤（2）中所述的探索策略是Sink节点将剩余能量大于其所属的层的平均剩余能量的节点设定为该层的簇头候选，在剩余能量低于该层平均剩余能量的节点中随机选择个节点成为额外的候选簇头，Nl为层次l包含的节点总数，为层次l中剩余能量高于该层的平均剩余能量AEl的节点的数量，Pl为第l层中能够成为额外候选簇头的比例在确定了所有的候选簇头后，Sink节点通过CANDIDATE_ID消息向网络广播候选节点的ID。4.根据权利要求2所述的带有局部簇重构的非均匀分簇路由算法，其特征在于，步骤（3）中节点i的邻居节点的数量为，节点i与其各个邻居节点距离的总和为Di=Σj,j≠idij，节点i的剩余能量为REi，α、β和γ为加权因子；如果节点i被选为簇头候2CN102970723A权利要求书2/2页选节点，则其竞选簇头的权值为：。5.根据权利要求2所述的带有局部簇重构的非均匀分簇路由算法，其特征在于，步骤（4）中网络层次的总数为lmax，每一轮的运行时间为TR；最小的执行簇重构的时间间隔为T0,T0＜TR，第l层执行局部簇重构的时间间隔为Tl：在每一轮开始时，Sink节点会启动一个计时器tr，当tr=TR，网络进入到新的一轮，开始整个网络的重新分簇，当网络进入到稳定阶段后，每个层次各自的计时器tl=Tl时，第l层开始本层的局部簇重构操作，并令tl=0重选开始计时；首先，第l层中的所有簇头向所有的邻居节点发送开始簇头重