一种基于粒子的无线传感器网络路由协议优化方法

本发明涉及通信技术领域，尤指一种基于粒子的无线传感器网络路由协议优化的实现方法。

现代信息科学的重要环节是信息的获取，无线传感器网络是由大量满足空间分布的微电子设备组成的网络系统，具备无线自组织的良好特性，目前已应用于各行业的数据采集工作。无线传感器网络节点随机分布在被监控的区域网络范围中，对自身区域半径范围内的监控数据进行收集，临近节点可以进行数据的传输和接收，并进行数据的融合处理。各节点间通过接力协助配合完成监控区域内的信息到的无线方式传送，实现对客观物理世界的覆盖。

无线传感器网络节点物理结构的特性导致其体积较小，处理和存储数据的能力受限，且节点电量是一定的，无线通信过程的节点能耗的优化显得非常重要。无线传感网络的传感器节点由电池供电，因工作环境等原因不能及时对电源进行换新，因此，使节点在网络正常运营的前提下设计能耗低的路由协议可以保证传输功率，并延长网络生存周期。

无线传感器网络路由算法的设计结果直接影响网络系统的可靠性及系统吞吐量等实际关键因素，目前的无线传感器网络路由算法无法平衡能耗和数据传输之间的矛盾，导致无线传感器网络路由的数据传输时延较大，无线传感器网络吞吐量较小,数据的传输过程中发生不必要的碰撞而导致再一次实行发送造成浪费，各个节点无秩序的随意传输占用网络中重要位置的节点，避免造成信道堵塞，信息无法快速传输到。通过汇聚节点向其他传感器节点传递征询目前工作状态的指令和向汇聚节点进行汇报工作状态，从而降低汇聚节点定期进行消息扩散传输过程的能耗，选择吞吐量大的路由进行数据传输，可使各节点之间负载较均衡，极大提升节点的能量利用率。

为解决上述问题，本发明提出无线传感器网络路由协议优化最优化数学模型，并提出基于粒子的路由协议优化方法，可有效减少网络系统的能量消耗，从而提高无线传感器网络生存周期和系统性能，主要包括以下步骤：

建立无线传感器网络路由协议最优化数学模型：

本发明所研究的路由协议主要考虑无线传感器网络通信能耗，假设传感器网络是由 M(m＝1,2,...,M)个传感器节点和L(l＝1,2,...,L)条链路组成的连通守恒系统，通信能耗主要包括发送、接收和融合数据的能耗，采用自适应分簇分层的能耗模型，自由空间模型和多路衰减模型分别针对于不同距离的节点空间。节点发送k比特数据需要消耗的能量Etx如下式所示：

Ee为发射电路消耗的单位能量，εamp1和εamp2表示功放因子参数，分别用于表示自由空间模型和多路径衰减模型，d表示发射出数据节点与接收到数据节点之间的欧氏距离，d0是阈值，用来区分消耗模型。

无线传感器网络路由协议设计中，候选簇首m的优势距离Dm计算如下所示：

其中d(Nsmk,sink)表示竞争半径内不是候选簇首的节点与汇聚节点之间的距离，dm表示候选簇首m与汇聚节点之间的距离，d(Nsmk,m)为竞争半径内不是候选簇首的节点与候选簇首m之间的距离；当一个候选簇首竞争半径内的所有节点距离网络的汇聚节点比较远，而与这个候选簇首之间较近时，表明这个候选簇首位置优越，更适合做簇首收集附近数据。

确定候选簇首m的竞争半径内是否有其他候选簇首，若没有则节点m直接当选簇首，若还存在候选簇首m，则需要根据节点剩余能量、邻居节点集合、与汇聚节点距离和到汇聚节点最短跳数等选举指标构成的影响度函数进行比较，最终决定簇首。由此得到候选簇首m的竞争半径：

其中dmax和dmin分别为候选簇首m竞争半径内节点到汇聚节点sink距离的最大值和最小值， c为控制参数。为保证网络更好的传输，竞争半径需满足：

0≤Rm≤Rmax Rmax为所有候选簇首竞争半径的最大值。

节点接收k比特数据需要消耗能量Erx为：

Erx(k)＝kEe

节点融合k比特数据需要消耗能量Eag为：

Eag(k)＝Etx+Erx

候选簇首m的剩余能量Ei计算过程为：

其中E0代表网络中节点的初始能量，i(i＝1,2,...n)为当前簇首选举的轮数，每个节点的剩余能量可用节点的初始能量减去每轮接收、发送和融合数据所消耗的能量之和，簇首与汇聚节点间的数据传输耗能大，对候选簇首的剩余能量要求高。

无线传感器网络中优化功率能够提高网络系统容量、节省节点功耗和延长节点寿命，但过低功率也会导致通信质量下降，连接不可靠，所以有效实现功率控制是非常有必要的。本发明限制数据信息进行传输时产生的误码率不超过该系统能够承受的限定值，即每条链路上的信号噪声干扰比SIR必须大于限定值βl：

其中SIRl代表的是第l条链路上的信噪比；Gll代表第l条链路上的发送端到第v条链路的接收端所产生的链路增益，Pl是第l条链路上的平均的传输功率；σ2为接收的噪声功率，其主要来自于其他的链路造成的干扰总和。在物理层上功率的控制一般是为了减少造成的干扰， MAC上的功率控制常常是用来实现全网上传输功率达到最小化，以此来提高传感器节点能量效率。

无线传感器网络数据信息的传输，可以直接选择较大的功率来直接进行，也可以选择较小的功率，运用多跳的方式来进行传输，这两种方式的进行都会使得两个节点之间进行直接通信。在链路上的节点成功地接收来自其他节点所传输的数据对功率是有一定的要求的，设限定的节点m接收功率为Pm，满足：

Pmin≤Pm≤Pmax

其中Pmax表示的是该节点的最大传输功率值。成功地接收信息的最小发射功率Pmin。

本发明充分考虑功率与功耗等性能指标，建立满足上述目标函数和约束条件的路由协议优化模型：

max Ei

s.t.Pmin≤Pm≤Pmax

0≤Rm≤Rmax

基于粒子法的路由协议最优化方法

粒子方法属于进化算法，通过模拟自然界中鸟的觅食行为来构造的智能优化算法，具有实现简单、收敛较快和精度较高等优点，适用于多目标寻优问题。粒子算法与其它演化算法的相似之处，就是根据对环境的适应度将体中的个体移动到好的区；不同之处在于它不像其他演化算法那样对个体是用演化算子，而是将每个个体看作寻优空间中的一个没有质量没有体积的粒子，在搜索空间中以一定的速度飞行，通过对环境的学习与适应，根据个体与体的飞行经验的综合分析结果来动态调整飞行速度。

在整个寻优过程中，每个粒子的适应值取决于所选择的优化函数的值，每个粒子具有粒子当前所处位置；到目前为止由自己发现的最优位置，以信息视为粒子的自身飞行经验；到目前为止整个体中所有粒子发现的最优位置，这可视为粒子的同伴共享飞行经验。于是，各粒子的运动速度受到本身和体的历史运动状态信息影响，并以自身和体的历史最优位置来对粒子当前的运动方向和运动速度加以影响，很好地协调了粒子自身运动和体运动之间的关系。

本发明的无线传感器网络路由协议算法中，设X＝{X1,X2,…Xm}是节点体的集合，根据初始簇首适应值函数的值和随机产生的局部最优位置(pxmd,pymd)和全局最优位置(pxgd,pygd)来进行新一轮的迭代，先将候选簇首的位置信息更新，再进行候选簇首适应值函数的值的计算和比较。设(Xxmd,Xymd)表示第m个候选簇首节点集在x、y方向上的位置向量，利用候选簇首的位置计算其适应值函数的值，就可以计算出节点当前的适应值，根据候选簇首适应值的大小来衡量其位置的优劣。设第m个侯选簇首节点集在x和y方向上的速度向量(Vxmd,Vymd)，初始计算时随机生成，后续的每一轮迭代中根据候选簇首节点集前一轮的变化关系确定。设(pxmd,pymd)表示候选簇首m截止到目前搜索到的最好位置，设(pxgd,pygd)表示整个无线传感器网络在循环后搜索到的最优位置。候选簇首m在解空间中跟踪个体极值和全局极值不断搜索，直到达到设定好的迭代次数或在规定的误差之内。

无线传感器网络路由协议最优化方法步骤如下：

Step 1：第一轮分簇时，所有节点的初始能量相同，因此各节点都可以竞选簇首，在之后的分簇过程中，需要将节点的剩余能量与平均水平进行比对，只有满足Ei≥Eavg，即剩余能量高于平均值的节点能成为候选簇首；

Step 2：初始化候选簇首节点集，在网络节点集合X＝{X1,X2,…Xm}中筛选出剩余能量满足要求的候选簇首节点集，并随机设定其初始位置分量Xx0d、Xy0d和速度分量Vx0d、Vy0d，当前个体最优位置为其初始位置；

Step 3：计算出每个候选簇首节点集的适应值函数Zm，每个候选簇首节点集的平均最优函数值可设置为其初始位置下的适应值，数值最大的候选簇首节点集最优函数值当选成为整个网络最优函数值；

Step 4：获得新一轮迭代后候选簇首节点集的速度分量和位置分量，并立即调整候选簇首节点集的位置，到网络中对应节点的位置；对因子c1、c2和权值ω进行换新。

Step 5：调整局部最优候选簇首节点集，对于网络中每个候选簇首节点集，若当前位置的候选簇首节点集的适应值与之前迭代所设定的最优位置的候选簇首节点集的适应函数的值大，则将当前位置更新为新的个体最优位置；调整全局最优候选簇首节点集，网络中每个候选簇首节点集，若当前位置的候选簇首节点集的适应值与之前迭代所设定的全局最优位置的候选簇首节点集的适应值大，则将这个个体当前位置作为全局最优位置；

Step 6：当达到预设的最大迭代次数，选择此时的全局最优位置作为最终簇首节点集的位置，簇首选举完成，否则返回到Step 4继续进行，i＝i+1。

Step 7：根据粒子优化算法确定的簇首广播当选消息，普通节点选择合适的簇首入簇，簇首把普通节点携带来的数据进行融合再发送给根据粒子优化算法确定的下一跳中转节点，通过簇间多跳直至数据包传送到。

与现有技术相比，本发明具有以下优点：

1.针对未来通信技术低时延和低功耗的要求，本发明以优化路由协议和降低总功耗为目标，建立了无线传感器网络路由协议最优化数学模型。为更好适应实际网络情况，模型考虑误码率约束、功率约束和竞争半径等符合实际网络情况的约束。

2.本发明所采用的粒子法，对目标函数形式和优化问题的连续性不做要求，易执行，可有效解决优化问题。在优化解迭代时，通过尽可能地扩大寻最优候选簇头节点集的局部搜索范围，以增强体的多样性，防止因为搜索范围小导致陷入局部最优解，后期迭代侧重全局最优搜索，保证收敛速度和搜索效果的均衡，有效降低了网络能耗，确保了系统具备很强的鲁棒性。

图1：本发明验证基于不同方法的无线传感器网络路由协议对应的剩余节点能量示意图；

图2：本发明验证基于不同方法的无线传感器网络路由协议对应的存活节点个数示意图；

图3：本发明验证基于不同方法的无线传感器网络路由协议对应的网络最优功率收敛示意图。

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述。本实施基于改进粒子的无线传感器网络路由协议的最优方法，通过以下技术方案实现：

建立无线传感器网络路由协议最优化数学模型：

本发明所研究的路由协议主要考虑无线传感器网络通信能耗，假设传感器网络是由 M(m＝1,2,...,M)个传感器节点和L(l＝1,2,...,L)条链路组成的连通守恒系统，通信能耗主要包括发送、接收和融合数据的能耗，采用自适应分簇分层的能耗模型，自由空间模型和多路衰减模型分别针对于不同距离的节点空间。节点发送k比特数据需要消耗的能量Etx如下式所示：

Ee为发射电路消耗的单位能量，εamp1和εamp2表示功放因子参数，分别用于表示自由空间模型和多路径衰减模型，d表示发射出数据节点与接收到数据节点之间的欧氏距离，d0是阈值，用来区分消耗模型。

无线传感器网络路由协议设计中，候选簇首m的优势距离Dm计算如下所示：

其中d(Nsmk,sink)表示竞争半径内不是候选簇首的节点与汇聚节点之间的距离，dm表示候选簇首m与汇聚节点之间的距离，d(Nsmk,m)为竞争半径内不是候选簇首的节点与候选簇首m之间的距离；当一个候选簇首竞争半径内的所有节点距离网络的汇聚节点比较远，而与这个候选簇首之间较近时，表明这个候选簇首位置优越，更适合做簇首收集附近数据。

确定候选簇首m的竞争半径内是否有其他候选簇首，若没有则节点m直接当选簇首，若还存在候选簇首m，则需要根据节点剩余能量、邻居节点集合、与汇聚节点距离和到汇聚节点最短跳数等选举指标构成的影响度函数进行比较，最终决定簇首。由此得到候选簇首m的竞争半径：

其中dmax和dmin分别为候选簇首m竞争半径内节点到汇聚节点sink距离的最大值和最小值， c为控制参数。为保证网络更好的传输，竞争半径需满足：

0≤Rm≤Rmax

Rmax为所有候选簇首竞争半径的最大值。

节点接收k比特数据需要消耗能量Erx为：

Erx(k)＝kEe

节点融合k比特数据需要消耗能量Eag为：

Eag(k)＝Etx+Erx

候选簇首m的剩余能量Ei计算过程为：

其中E0代表网络中节点的初始能量，i(i＝1,2,...n)为当前簇首选举的轮数，每个节点的剩余能量可用节点的初始能量减去每轮接收、发送和融合数据所消耗的能量之和，簇首与汇聚节点间的数据传输耗能大，对候选簇首的剩余能量要求高。

无线传感器网络中优化功率能够提高网络系统容量、节省节点功耗和延长节点寿命，但过低功率也会导致通信质量下降，连接不可靠，所以有效实现功率控制是非常有必要的。本发明限制数据信息进行传输时产生的误码率不超过该系统能够承受的限定值，即每条链路上的信号噪声干扰比SIR必须大于限定值βl：

其中SIRl代表的是第l条链路上的信噪比；Gll代表第l条链路上的发送端到第v条链路的接收端所产生的链路增益，Pl是第l条链路上的平均的传输功率；σ2为接收的噪声功率，其主要来自于其他的链路造成的干扰总和。在物理层上功率的控制一般是为了减少造成的干扰， MAC上的功率控制常常是用来实现全网上传输功率达到最小化，以此来提高传感器节点能量效率。

无线传感器网络数据信息的传输，可以直接选择较大的功率来直接进行，也可以选择较小的功率，运用多跳的方式来进行传输，这两种方式的进行都会使得两个节点之间进行直接通信。在链路上的节点成功地接收来自其他节点所传输的数据对功率是有一定的要求的，设限定的节点m接收功率为Pm，满足：

Pmin≤Pm≤Pmax

其中Pmax表示的是该节点的最大传输功率值。成功地接收信息的最小发射功率Pmin。

本发明充分考虑功率与功耗等性能指标，建立满足上述目标函数和约束条件的路由协议优化模型：

max Ei

s.t.Pmin≤Pm≤Pmax

基于粒子的路由协议最优化方法

粒子方法属于进化算法，通过模拟自然界中鸟的觅食行为来构造的智能优化算法，具有实现简单、收敛较快和精度较高等优点，适用于多目标寻优问题。粒子算法与其它演化算法的相似之处，就是根据对环境的适应度将体中的个体移动到好的区；不同之处在于它不像其他演化算法那样对个体是用演化算子，而是将每个个体看作寻优空间中的一个没有质量没有体积的粒子，在搜索空间中以一定的速度飞行，通过对环境的学习与适应，根据个体与体的飞行经验的综合分析结果来动态调整飞行速度。

在整个寻优过程中，每个粒子的适应值取决于所选择的优化函数的值，每个粒子具有粒子当前所处位置；到目前为止由自己发现的最优位置，以信息视为粒子的自身飞行经验；到目前为止整个体中所有粒子发现的最优位置，这可视为粒子的同伴共享飞行经验。于是，各粒子的运动速度受到本身和体的历史运动状态信息影响，并以自身和体的历史最优位置来对粒子当前的运动方向和运动速度加以影响，很好地协调了粒子自身运动和体运动之间的关系。

本发明的无线传感器网络路由协议算法中，设X＝{X1,X2,…Xm}是节点体的集合，根据初始簇首适应值函数的值和随机产生的局部最优位置(pxmd,pymd)和全局最优位置(pxgd,pygd)来进行新一轮的迭代，先将候选簇首的位置信息更新，再进行候选簇首适应值函数的值的计算和比较。设(Xxmd,Xymd)表示第m个候选簇首节点集在x、y方向上的位置向量，利用候选簇首的位置计算其适应值函数的值，就可以计算出节点当前的适应值，根据候选簇首适应值的大小来衡量其位置的优劣。设第m个侯选簇首节点集在x和y方向上的速度向量(Vxmd,Vymd)，初始计算时随机生成，后续的每一轮迭代中根据候选簇首节点集前一轮的变化关系确定。设(pxmd,pymd)表示候选簇首m截止到目前搜索到的最好位置，设(pxgd,pygd)表示整个无线传感器网络在循环后搜索到的最优位置。候选簇首m在解空间中跟踪个体极值和全局极值不断搜索，直到达到设定好的迭代次数或在规定的误差之内。

无线传感器网络路由协议最优化方法步骤如下：

Step 1：第一轮分簇时，所有节点的初始能量相同，因此各节点都可以竞选簇首，在之后的分簇过程中，需要将节点的剩余能量与平均水平进行比对，只有满足Ei≥Eavg，即剩余能量高于平均值的节点能成为候选簇首；

Step 2：初始化候选簇首节点集，在网络节点集合X＝{X1,X2,…Xm}中筛选出剩余能量满足要求的候选簇首节点集，并随机设定其初始位置分量Xx0d、Xy0d和速度分量Vx0d、Vy0d，当前个体最优位置为其初始位置；

Step 3：计算出每个候选簇首节点集的适应值函数Zm，每个候选簇首节点集的平均最优函数值可设置为其初始位置下的适应值，数值最大的候选簇首节点集最优函数值当选成为整个网络最优函数值；

Step 4：获得新一轮迭代后候选簇首节点集的速度分量和位置分量，并立即调整候选簇首节点集的位置，到网络中对应节点的位置；本发明中对认知学习因子c1、社会学习因子c2和惯性权值ω进行改进：

其中i是本轮迭代的次数，imax是可以迭代的最大次数，c1a,c1f,c2a,c2f分别对应c1和c2的加速度系数的初始值和最终值，通过尽可能地扩大寻最优候选簇头节点集的局部搜索范围，以增强体的多样性，防止因为搜索范围小导致陷入局部最优解，可反应出后期的迭代侧重全局最优搜索，保证收敛速度和搜索效果的均衡。

其中wmin和wmax是惯性权值的最小值和最大值，Zm是本轮候选簇首节点集的适应值函数的值， Zmin是本轮候选簇首节点集的适应值函数值的最小值，Zavg是本轮候选簇首节点集的适应值函数值的平均值。当本轮候选簇首节点集的适应值函数的值大于平均水平时说明此簇首节点集性能优良，本轮速度分量应主要参考上一轮，增加候选簇首节点集的活跃度，反之，速度分量应该主要参考局部最优位置和全局最优位置，加速候选簇首节点集向优势位置靠拢。

Step 5：调整局部最优候选簇首节点集，对于网络中每个候选簇首节点集，若当前位置的候选簇首节点集的适应值与之前迭代所设定的最优位置的候选簇首节点集的适应函数的值大，则将当前位置更新为新的个体最优位置；调整全局最优候选簇首节点集，网络中每个候选簇首节点集，若当前位置的候选簇首节点集的适应值与之前迭代所设定的全局最优位置的候选簇首节点集的适应值大，则将这个个体当前位置作为全局最优位置；

式中r1和r2两个均匀分布在(0，1)上的随机数的序列。

Step 6：当达到预设的最大迭代次数，选择此时的全局最优位置作为最终簇首节点集的位置，簇首选举完成，否则返回到Step 4继续进行，i＝i+1。

Step 7：根据粒子优化算法确定的簇首广播当选消息，普通节点选择合适的簇首入簇，簇首把普通节点携带来的数据进行融合再发送给根据粒子优化算法确定的下一跳中转节点，通过簇间多跳直至数据包传送到。

数值仿真

为了验证本发明方法的有效性,对本发明所提基于改进粒子的无线传感器路由协议优化方法进行仿真实验。考虑无线传感器网络用户随机均匀分布在100m*100m的监测区域内，节点初始能量为0.5，节点数为100，功率最大值为10mW，迭代次数设为I＝100，最大轮数设为i＝1500，所有PSO种大小设为50，PSO参数设为的c1＝2，c2＝2，w＝0.57。

将基于粒子方法(Particle Swarm Optimization,PSO)、改进粒子方法1(Improved Particle Swarm Optimization 1,IPSO1)、改进粒子方法2(ImprovedParticle Swarm Optimization 1,IPSO2)和本发明所提改进粒子方法(ImprovedParticle Swarm Optimization, IPSO)的路由协议优化方法性能进行对比，其中IPSO 1对应的是调整惯性权值w，但认知学习因子c1和社会学习因子c2固定，如下式：

其中wmin和wmax是惯性权值的最小值和最大值，Zm是本轮候选簇首节点集的适应值函数的值， Zmin是本轮候选簇首节点集的适应值函数值的最小值，Zavg是本轮候选簇首节点集的适应值函数值的平均值。

IPSO 2对应的是固定惯性权值w，但对认知学习因子c1和社会学习因子c2改进，如下式所示：

t是本轮迭代的次数，tmax是可以迭代的最大次数，c1a,c1f,c2a,c2f分别对应认知学习因子c1和社会学习因子c2的加速度系数的初始值和最终值。本发明方法对惯性权值w、认知学习因子 c1和社会学习因子c2按照上面两个式子进行同时改进。

图1给出了不同轮数情况下不同方法所对应的剩余能量变化的结果，从图中可以看出，经典PSO算法对应的路由协议节点剩余能量下降斜率最陡，能量消耗最快；IPSO1次之；而本发明基于IPSO的路由协议下降最慢，能量消耗最慢，这是由于本发明所提方法合理选择簇头，有效降低了节点通信能耗的能量。图2给出了不同轮数情况下不同方法对应的存活节点个数，PSO所对应的协议方法节点能耗最大，在较短时间段内，死亡节点个数较多，而本发明所提方法对应的节点个数存活节点个数减少相对缓慢，这是因为调整权值因子可以增加候选簇首节点集的活跃度，从而加速候选簇首节点集向优势位置靠拢，使得节点存活率较 PSO、IPSO1和IPSO2更高。图3出了不同轮数情况下不同方法对应的最优功率，可以看出由于本发明所提方法在优化解迭代时，通过尽可能地扩大寻最优候选簇头节点集的局部搜索范围，以增强体的多样性，防止因为搜索范围小导致陷入局部最优解，后期迭代侧重全局最优搜索，保证收敛速度和搜索效果的均衡，有效降低了网络能耗，从而使得所提路由协议最优化方法具有更优的性能。