基于Grid-VFACO的数字化车间WSNs路由算法*

朱绍文， 纪志成， 王 艳， 吴定会

(江南大学 物联网工程学院，江苏 无锡 214122)

0 引 言

数字化车间是现代化车间信息化发展的新阶段，及时正确地采集车间数据是实现数字化车间的重要前提。无线传感器网络(WSNs)具有支持拓扑变化、节点移动等特点[1～3]，特别适用于数字化车间数据采集过程中。车间涉及到产品制造过程中的各个生产步骤，数据类型[4]不同，采集能耗不均，数据冗余大，由于每个传感器节点的能量有限，任一节点失效会导致服务器无法实时得到该节点采集范围内的数据，而在车间这种特殊的需要长时间连续工作的系统中,停止当前工作给节点更换电池或充电的成本较高。因此,如何构建一个高效节能的路由协议[5]，提高节点的平均生存时间成为WSNs面临的主要问题。基于分簇的路由[6]结合了数据融合技术，能显著降低数据冗余，提高能量有效性和网络的可扩展性。

围绕分簇机制，目前已经有大量的研究工作。Heinzelman等人提出了LEACH[7]的算法，是以循环的方式随机选择簇首节点，将整个网络的能量负载均衡平均分配到每个传感器节点中，从而降低网络能耗。Younis O等人[8]提出的HEED算法考虑了节点的剩余能量，并引入主从关系多个约束条件作用于簇首的选择过程。Inbo Sim等人[9]提出一种簇头选举过程中考虑节点能量和当选为簇头节点的次数的改进协议ECS。罗四维等人[10]提出了一种在簇首选举中综合考虑节点消耗速率和普通节点到Sink节点距离局限性的分簇路由协议EDRMC。上述协议简单易于实现，但存在没有考虑节点剩余能量或缺乏对位置因素的考虑等一些缺陷，不能适合数字化车间数据采集对WSNs的需求。

本文针对应用中存在的上述问题，提出了一种基于网格和虚拟力导向蚁群优化(Grid-VFACO)算法的高能效路由策略，先将车间数据采集区划分成网格，并基于节点位置和剩余能量的考虑选举簇首，优化簇首分布。在簇首节点形成一个上层网络中采用VFACO算法求出最优数据转发路径，通过多跳的方式将数据发送到Sink节点，平衡簇首的能耗，并满足应用中要求的传输时延。

1 网络模型

在车间数据采集区M×M中分布N个传感器节点，部署后位置不发生移动，应用场景为传感器节点周期地获取监测数据并不断地将数据向Sink节点汇集。网络具有以下性质：1) Sink节点位于网络外侧，计算能力和能量不受限制，传感器节点和Sink节点在部署后位置不发生移动；2)传感器节点具备数据融合功能，能感知自己的剩余能量，并且具有全网唯一ID；3)已知对方的发送功率，节点可以根据接收信号的强度计算发送者到自己的近似距离；4)采用与LEACH协议相同的无线通信能耗模型。节点将一个lbit的数据传送距离d，则发送数据能耗

(1)

接收数据消耗模型

ERx(l)=Eelec·l.

(2)

Eelec为发射和接收电路每发送或接收单位bit数据的能耗，εfs和εamp分别为自由空间和多路衰减模型中天线增益所消耗的能量。

2 Grid-VFACO算法的设计

2.1 Grid的划分

将数据采集区用网络来覆盖的目的是为了实现簇的均匀分布。划分网格时，在连通度上要求任意相邻的簇首都能直接通信，用R表示通信半径，则网格的边长d需满足

(3)

在覆盖度上要求合适的分簇数量可覆盖监测区域。根据文献[12]的分析，综合考虑分簇对能耗和网络时延的影响，推导出最优分簇数kopt

(4)

式中λ为能耗和时延的权重因子，Tslot为时隙长度。对kopt取整后求出网格的边长

(5)

d越大，则被包含在一个网格内的节点数将越多，这对节省网络能耗是有益的，因此,d取值为

(6)

基站将计算出的网格边距通过“HELLO”报文广播至全网节点，节点接收到边距广播消息后根据自身的地理坐标(xi,yi)计算出网格编号(Girdx,Girdy)

(7)

网络节点会因能量耗尽而失效，存活节点数在整个过程中不断发生变化，当减小到一定的比例时，基站会重新计算最优簇数目，调整簇的个数和网络的边长后再次发送广播报文，完成簇的重构。

2.2 候选簇首的选举

为了防止区域边缘的节点成为簇首，在网格质心位置的一定范围内，选择出候选簇首。具体步骤为：

1)先计算每个划分网格中质心点的位置坐标

(8)

式中n为每个网格内节点的个数，i表示节点的ID号。

2) 以所得质心点位置为圆心，选择半径为Rc内的节点，作为候选簇首参与簇首的竞争，并对候选节点进行标记

(9)

其中，dmax,dmin分别为簇内节点到簇质心点距离最大和最小值，daverage是簇内节点到质心的平均距离，c∈(0,1)。

2.3 簇首的选举

在候选簇首中进一步选择簇首，为保证簇首的能量达到完成一轮通信所消耗最小能量，并使簇首位置尽量靠近该网格的质心，目标函数为

Pch=(e-di)k1·(Eiresidual/Eave)1-k1，Eiresdual≥Eth,

(10)

式中dmi为网格中的节点到该网格质心点的距离，Eiresidual为节点i的剩余能量，Eave为候选节点的平均能量，Eth为能量门限值，当节点的剩余能量低于Eth时不能担任簇首。由于节点的能量损耗主要用于接收、发送消息以及数据融合，因此，Eth值为

(11)

式中Ncollect为一次循环中数据收集次数，Caverage为簇内节点数，l为数据包长度,EDA为融合单位比特数据能耗。选择Pch值最大的节点作为簇首。

当所有簇首确定后，广播消息通知其它节点，具有相同网格编号的节点自组织成簇。

在每一轮的最后一帧，簇首的所有邻居节点将剩余能量值报告给簇首，如果有簇首的剩余能量值低于Eth，原簇首在候选簇首集中选择Pch最大的节点作为下一轮的簇首;否则,下一轮簇首不更换。

2.4 基于VFACO的数据转发

簇首选举之后，利用VFACO算法进行路径搜索，目标是寻找从各个簇首到Sink代价最小的多跳路由。

定义f(i,j)表示节点j相对于节点i的虚拟吸引力为

(12)

(13)

将f(i,j)作为蚁群算法中转移概率规则启发因子，则位于节点i的蚂蚁k选择下一节点j进行访问的概率为pk(i,j)

(14)

如果簇首chi和chj是选择路径上的节点，根据公式更新边e(chi,chj)间的信息素浓度

τij(t+1)=(1-ρij)τij(t)+Δτij,ρij

=ρinit(Dj-sink/Di-sink),

(15)

式中 Δτij为路径ij上的信息素浓度增量，ρij为信息素的蒸发率，与簇首到Sink节点的距离D密切相关，靠近Sink节点的信息素蒸发率的值较小，留在边上的信息素较多，保证蚂蚁能够较快地到达Sink节点，提高数据传输的实时性。

当Sink节点收到从一个簇首发来所有前向节点后，通过对每个节点包里面记录的路径节点个数和各节点剩余能量值，计算各路径平均剩余能量Eaverage进行比较，最终选出一条从该簇首到Sink节点的Eaverage最大的最优路径

(16)

其中,route-i为节点i所走过的路径。当Sink节点选出最优路径后，立即产生一个反向蚂蚁按照最优路径返回到簇首，并对信息素进行全局更新，更新公式如下

τij(t+1)=τij(t)+Δτ(t),Δτ(t)=Q/lk，

(17)

式中Q为系统参数，lk为最优路径长度。当簇首发生变化后，与上一轮簇首交换路由表信息，并重新计算信息素和概率。最终数据包经过簇首间的多跳路由从源点传送到Sink节点。

3 算法仿真结果及分析

为了评价本文算法的性能优势和有效性，在200 m×200 m的数字化车间数据采集区域分布100个传感器节点，初始能量为0.5 J，通信半径为180 m，Sink节点的位置为(100,275)m。εfs和εamp分别为10 pJ/bit/m2和0.001 3 pJ/bit/m4，Eelec和EDA分别为50，5 nJ/bit，数据包大小为2 kB，信息素蒸发率初始值ρinit为0.9，α和β值分别为1和2，Q值设为100。利用Matlab R2010a对本文Grid-VFACO算法和LEACH算法从网络存活节点数和能耗2个方面进行仿真比较与分析。

图1是本文算法首次数据采集区网格划分和簇首选举后的效果。从图中可以看出:目标区域被划分成9个网格，每个网格中选举产生1个簇首(图中“*”标记的节点为簇首)，靠近网格质心，簇首分布均衡，有助于平衡整个网络的能耗。

图1 首次网格的划分与簇首选择

3.1 生命周期对比分析

图2为200×200的数字化车间数据采集区域中WSNs生命周期图，在使用LEACH算法的网络中，从474轮节点开始死亡，直到813轮节点全部死亡。在本文算法中，节点从653轮开始死亡，直到978轮节点全部死亡，由此说明:Grid-ACO算法在延长网络生命方面的性能比LEACH算法有明显的提升。

图2 网络生命周期的比较

3.2 能量消耗对比

图3为2种算法的能量消耗图，由图可以发现，随着运行轮数的增长，本文对簇首的分布和簇间路由进行优化，使能量消耗值比LEACH算法减小约20 %以上，由此证明:本文算法能显著降低网络能耗，加强网络健壮性，提高了网络的整体性能。

4 结束语

本文从数字化车间实际环境和现场应用的实时性考虑，提出了基于Grid-VFACO高能效路由算法，综合考虑

图3 网络能耗的比较

节点分布位置和剩余能量，优化了簇首选择机制，并利用VFACO算法实现了簇首间多跳路由性能的改善。仿真结果表明:本文Grid-VFACO算法能平衡网络能耗，可以快速、准确地将数据传输到与数据库服务器相连的Sink节点，使管理人员可以及时掌握车间生产信息。

参考文献:

[1]李晓维，徐勇军，任丰原.无线传感器网络技术[M].北京：北京理工大学出版社，2007:2-5.

[2]Haiying Shen,Ze Li,Lei et al.Efficient data collection for large-scale mobile monitoring applications[J].IEEE Transactions on Parallel and Distributed Systems,2013,99(1):1-10.

[3]凡高娟，郭拯危.无线传感器网络节点部署研究进展[J].传感器与微系统,2012,31(4):1-4.

[4]林国富.离散制造车间数据采集系统的研究与开发[D].南京：南京理工大学,2011.

[5]Pantazis N A,Nikolidakis S A,Vergados D D.Energy-efficient routing protocols in wireless sensor networks: A survery[J].IEEE Communications Surveys & Tutorials,2013,15(2):551-591.

[6]由文凯.基于Zig Bee的无线传感器网络路由协议的研究[D].南京：南京邮电大学,2012.

[7]Heinzelman W R,Chandrakasan A P,Balakrishnan H.An application specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communication Networks,2002,1(4):660-670.

[8]Younis O,Fahmy S.HEED: A hybrid,energy efficient,distributed clustering approach for Ad Hoc sensor networks[J].IEEE Transactions on Mobile Computing,2004,3(4): 366-379.

[9]Sim I,Choi K,Kwon K,et al.Energy-efficient cluster selection algorithm in WSNs[C]∥Proceedings of the International Confe-rence on Complex Intelligent and Software Intensive Systems,CISIS,2009:584-587.

[10] 罗四维，侯孟书，周益民.一种新的基于能量消耗速率模型的分簇路由协议[J].计算机科学,2012,39(6):47-50.

[11] 朱 敏，肖 震，刘昊霖,等.WSN中基于虚拟网格的分簇路由算法[J].四川大学学报：工程科学版，2011，31(2):324-327.