一种基于演化博弈的分簇协作路由方法

摘要

本发明公开了一种基于演化博弈的分簇协作路由方法，定义虚节点剩余能量作为簇头确立的指标，然后通过动态演化博弈为簇联盟问题建立模型。剩余节点选择不同簇头结成联盟，可获得不同的收益，收益由簇头的能力、簇成员节点个数等因素决定。每个节点都可以根据自身得到的信息有限理性的选择簇结成联盟，直到网络中所有节点改变簇联盟都不能获得更高的收益。实验结果表明，本发明与协作多输入多输出路由方法相比，CCREG方法的网络生存周期在两个簇头情况下延长14％到70％，三个簇头情况下延长5％到80％。

主权项

一种基于演化博弈的分簇协作路由方法，其特征在于，包括邻居发现部分、簇头确立部分和簇联盟部分：所述邻居发现部分包括以下步骤：1)对于无线传感器网络中的任一节点u，在邻居表中选择剩余能量最高的k‑1个邻居节点作为节点u的备选伙伴；将节点u与节点u的备选伙伴{v_k‑1,v_k‑2,…,v₁}组成的节点集定义成虚节点u’；虚节点u’的剩余能量等于所述节点集的平均剩余能量(R_u+R_{v_k‑1}+…+R_{v_1})/k；其中，k为簇头个数；R_u，R_{v_k‑1}，…，R_{v_1}分别为节点u，v_k‑1,v_k‑2,…,v₁的剩余能量；2)当无线传感器网络中除节点u之外的任一节点v成功申请到信道，节点v就以一个固定的功率发送一个Hello消息给它的邻居节点，其中Hello消息包含节点v的ID、剩余能量、邻居表和虚节点v’的剩余能量，收到Hello消息的节点u检查自己的邻居表是否含有节点v的项，如果没有，则将节点v及节点v的相关信息添加到邻居表中；否则，找到节点v的项，比较邻居表中的信息，如邻居表中的信息不同则更新节点u的邻居表；当节点u收到一个新的邻居节点发送的Hello消息时，节点u更新它的邻居表并广播给该新加入的邻居节点；当节点u收到节点v的Hello消息，且节点v的邻居表中没有包含节点u时，节点u发送Hello消息告知节点v；3)若在一段时间内，没有事件促使节点u发送更多的Hello消息，则节点u重复邻居发现部分步骤1)，重新确定虚节点u’及重新确定的虚节点u’的剩余能量，若无线传感器网络中的所有节点均不再发送hello信息，则进入簇头确立部分的步骤1)；所述簇头确立部分包括以下步骤：1)所有节点都被初始化成“待定”状态；2)节点u和节点u的邻居节点比较各自对应的重新确定的虚节点u’剩余能量，若重新确定的虚节点u’的剩余能量是所有“待定”状态下邻居节点所对应的虚节点剩余能量中最高的，则确立节点u为“主簇头”，节点u的备选伙伴设定为“从簇头”；3)主簇头和从簇头广播簇头信息给各自的邻居节点，收到消息的邻居节点把自己的状态设定为“成员”；4)对于剩下的“待定”节点，重复簇头确立方法的步骤2)和步骤3)，直到确定所有节点的状态；所述簇联盟部分包括：1)每个“成员”节点初始时都随机选择一个簇联盟；2)初始化完成后，进入动态演化博弈阶段：簇头节点通过公式计算出簇内成员节点可得到的收益π_i，并广播给所有成员节点，通过公式计算得到无线传感网络任一子区域a的平均收益表示当前时刻区域a中选择簇i联盟的节点比率，表示当前时刻区域a中选择簇i联盟的成员节点可得到的收益；所述簇头节点包括“主簇头”和“从簇头”；N_{host_i}表示簇i的簇头个数；表示簇头节点的剩余能量之和，n＝1,2,…N_{host_i}；N_i表示簇i的节点总数；为簇内通信的平均链路能耗，R_intra为单位时间内单个簇成员节点触发的簇内通信量，为簇间通信的平均链路能耗，R_inter为单位时间内单个簇成员节点触发的簇间通信量；3)如果成员节点收益小于上述平均收益，则进行策略调整，随机选择收益高于平均收益的簇联盟；4)所有成员节点做出一轮策略调整后，重复簇联盟部分的步骤2)和步骤3)，直到所有成员节点不再修改其簇联盟策略，即达到演化博弈均衡点。