节点6向节点0发送前向蚂蚁包, 如图1所示。各节点的邻居节点如下, 6:(5), 5:(3, 4, 6), 4:(2, 3, 5), 3:(1, 2, 4, 5), 2:(1, 3, 4), 1:(0, 2, 3), 0:(1)。由于EEABR算法蚂蚁包头中存放的已访问节点只记录蚂蚁上一跳地址, 例如节点3记录的上一跳地址为节点5, 其只能保证蚂蚁包无法“ 回传” , 但如果节点3的下一跳节点为4或2, 就有可能形成像5-3-4-5或5-3-2-4-5等环路, 造成能量的浪费和传输的延迟。

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 节点环路效应Fig.1 Node loop effect

为了改善上述的环路效应, 本文在节点邻居列表中添加pkt_src和sq_num的组合项(下文用< pkt_src, sq_num> 表示), 在发送蚂蚁包时, 在蚂蚁包头中添加下一跳节点地址naddr以及< pkt_src, sq_num> 。节点在广播Hello包时, 除了要广播自己节点地址和能量, 还应该广播邻居列表中的< pkt_src, sq_num> , 这样接收节点就会“ 知道” 自己的邻居节点转发过的蚂蚁包, 避免不必要的回传。假如节点6发送的蚂蚁包的标识为< 6, 1> , 按照假设路径6-5-3-4, 由于4的邻节点5和3都转发过标识为< 6, 1> 的蚂蚁包, 因此4就会优先选择节点2作为下一跳节点, 完成由路径6-5-3-4-2-1转发的蚂蚁包传输过程。

当前向蚂蚁包到达Sink节点时, Sink节点会根据前向蚂蚁包携带的信息计算信息素更新公式, 并发送后向蚂蚁包。当后向蚂蚁包到达发送前向蚂蚁包的源节点时, 从源节点到Sink节点的路径信息素更新完成, 标志着一次完整的蚂蚁包收发过程结束。本文对信息素增量公式进行重新定义, 同时引入节点能量与平均能量的偏离值作为信息素增量公式的参考因子, 用以平衡网络节点的能量。

EEABR算法中路径信息素更新公式如式(1)所示^[9]:

ΔTk=1C-EMink-FdkEAvgk-Fdk1

式中:C为节点的初始能量; E_Mink为蚂蚁包k访问路径上节点的最小能量; Fd_k为前向蚂蚁访问过的节点数; E_Avgk为路径上的节点平均能量。

通过公式推导, 可以得出当E_Mink< E_Avgk时, Δ T_k随着Fd_k的增加而减小, 同时引入E_Avgk和E_Mink可以起到一定的平衡网络节点能量的作用, 但却无法体现该条路径上节点能量是否均匀, 而且Fd_k的增加不意味着路径能量消耗的增加, 尤其在节点分布较为密集的区域更加明显, 因此在路由跳数较多、节点间隔较小的路径会影响Δ T_k更新的准确性。

本文在公式(1)的基础上, 引入节点能量与路径能量的偏离值, 并重新定义信息素增量公式, 如(2)式所示:

ΔTk=1C-EMink-EFdkEAvgk-EFdk+1σk(r)2

式(2)将式(1)中的Fd_k修改为EFd_k, 即前向路径上的能量消耗EFd_k=Fd_k* e* Ant_length, 其中e为发送1比特信息所消耗的能量, Ant_length为蚂蚁包的长度。对式(2)分析得出, EFd_k作为前向路径节点发送蚂蚁包所消耗的能量, σ _k(r)为标识为k的后向蚂蚁从节点s返回到节点r时, 节点r的能量e_r与路径平均能量E_Avgk的偏离值, 由式(3)求得:

σk(r)=(er-EAvgk)23

引入σ _k(r)的意义在于:当e_r与E_Avgk相差过大时, 增加的信息素会相应地减少, 在发送下轮蚂蚁包时, 会避开能量相差过大的路径, 同时1/σ _k(r)作为单跳的更新与前半部分路径上的更新相互补充, 更能体现蚂蚁的学习性。

步骤1 节点周期广播Hello包

节点通过广播Hello包的方式维护邻居列表, Hello包的结构如图2所示, 其中type为数据包类型, Hello_pkt_src为Hello包的源地址, < pkt_src, sq_num> 为本文添加的蚂蚁包标识组合项, 表明地址为pkt_src的节点所有转发过的蚂蚁包。energy为节点的能量, Phero为该路径上的信息素浓度。

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 Hello包结构Fig.2 Structure of Hello package

步骤2 节点向Sink节点发送前向蚂蚁包

节点通过发送前向蚂蚁包来传输信息和优化路径。当节点与邻节点通过收发Hello包的方式建立联系后, 节点会从邻居列表中通过式(4)选取一个节点作为发送前向蚂蚁包的下一跳节点。

Pk(r, s)=T(r, s)αE(s)β∑u∉MkT(r, u)αE(u)β, ifs∉Mk0, otherwise4

式中:P_k(r, s)为节点r下一跳选择节点s的概率; T(r, s)为路径(r, s)上的信息素浓度; E(s)为剩余能量函数, 定义为1/(C-e_s), 其中C为节点的初始能量, e_s为节点s的实际能量; M_k为邻居列表中转发过< pkt_src, sq_num> 蚂蚁包的节点集合; u为节点r的邻居列表中所有节点的集合; α 和β 分别表征信息素和能量的影响程度。节点邻居列表的结构如表1所示, 其中NeighbourAddr为邻居节点的地址, NeighbourEng为邻居节点的能量, Pheromone为本节点与邻节点路径信息素浓度, 需要说明的是, 当在接收方的邻居列表中没有发送方的记录时, 需要赋给Pheromone一个初始值。

表1

Table 1

表1(Table 1)

表1 邻居节点列表结构 Table 1 Neighbor list structure Neighbour List NeighbourAddr NeighbourEng Pheromone < pkt_src, sq_num>

表1 邻居节点列表结构 Table 1 Neighbor list structure

前向蚂蚁包的结构如图3所示。其中Type为数据包类型, pkt_src为数据包源地址, daddr为蚂蚁包下一跳地址, saddr为蚂蚁包上一跳的节点地址。Energy_sum为蚂蚁到达该节点时, 经过所有节点的能量总和, Energy_min为该条路径上节点的最小能量, toSintNode为布尔型变量, 表明蚂蚁包方向, hops为蚂蚁经过的节点数。

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 前向蚂蚁包结构Fig.3 Structure of forward ant package

步骤3 Sink节点向源节点发送后向蚂蚁包

当前向蚂蚁包到达Sink节点后, 会生成后向蚂蚁包, 同时按照式(5)计算更新后的信息素。其中T(r, s)为路径(r, s)上的信息素浓度, ρ 为信息素蒸发系数, Δ T_k为信息素增量公式, 由式(2)得出。

T(r, s)=(1-ρ)Tk(r, s)+ΔTk5

后向蚂蚁包的结构如图4所示, 其中, Energy_avg为路径上节点的平均能量, 结合节点能量e_r, 通过式(3)求得能量差异σ _k。

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 后向蚂蚁包结构图Fig.4 Structure of backward ant package

当后向蚂蚁包到达发送前向蚂蚁包的源节点时, 蚂蚁包随即被丢弃, 本轮蚂蚁包收发结束, 下一轮蚂蚁包收发开始。

图5为源节点向Sink节点发送前向蚂蚁包的流程图, 图6为Sink节点向源节点发送后向蚂蚁包的流程图。

图5

Fig.5

	Figure Option ViewDownloadNew Window
	图5 前向蚂蚁包发送流程Fig.5 Flow chat of forward ant package transmit

图6

Fig.6

	Figure Option ViewDownloadNew Window
	图6 后向蚂蚁包发送流程Fig.6 Flow chart of backward ant package transmit

本论文的实验环境采用的是虚拟机Vmware9.0+Ubuntu10.04+NS2.34, 协议文件包括:eeiabr/eeiabr.cc、eeiabr/eeiabr.h、eeiabr/eeiabr_pkt.h、eeiabr/eeiabr_table.h、eeiabr/eeiabr_table.cc、eeiabr/eeiabr_queue.h、eeiabr/eeiabr_queue.cc。将eeiabr文件夹拷贝在ns-allinone-2.34/ns-2.34下, 并对ns-2.34文件夹下的common/packet.h、trace/cmu-trace.h、trace/cmu-trace.cc、tcl/lib/ns-packet.tcl、tcl/lib/ns-lib.tcl、queue/priqueue.cc进行修改, 并在Makefile文件中添加该协议的可执行文件。保存完成后打开terminal, 进入到ns-allinone-2.34/ns-2.34目录下依次运行make clean和make命令, 编译添加的.cc文件, 生成.o文件^[10]。EEABR协议的添加过程与之相同。实验通过gawk脚本提取trace文件中的节点能量数据, 并通过Matlab进行绘图。

设定该仿真环境为50 m× 50 m, 节点数量为25, 节点的初始能量(InitialEnergy)为20 J, 节点的发送功率(txPower)为0.6 W, 节点的接收功率(rxPower)为0.3 W, 节点空闲能量消耗(idlePower)为0.06 W, 节点通信距离为20 m, 仿真时间为100 s, 图7为节点的平均剩余能量随节点数目变化情况, 图8为节点最小剩余能量随节点数目的变化情况。

图7

Fig.7

	Figure Option ViewDownloadNew Window
	图7 节点平均剩余能量随节点数目变化Fig.7 Node average residual energy vs.node number

图8

Fig.8

	Figure Option ViewDownloadNew Window
	图8 节点最小剩余能量随节点数目变化Fig.8 Node minimum residual energy vs.node number

在图7中, 当节点数目小于35时, 由于节点数目较少, EEABR算法环路效应不明显, 而EEIABR算法在Hello包中增加了< pkt_src, sq_num> 组合项, 增加了发送负担。因此EEIABR算法性能低于EEABR算法, 当节点数目大于40时, EEIABR算法由于削弱了环路效应, 性能开始高于EEABR算法。图8中, 由于EEIABR算法在信息素更新公式中引入了能量差异因子, 节点最小能量提升较为明显, 节点能量分布更为平均。因此EEIABR算法在节点数目较多、分布较为密集的场合对节点能量的平衡具有一定的优势。

为了进一步验证EEIABR算法在多节点时的性能, 保持50 m× 50 m的范围不变, 节点数目为65, 仿真时间范围为50~100 s, 其他设置不变。图9为节点平均剩余能量随时间的变化, 图10为节点最小剩余能量随时间的变化。

图9

Fig.9

	Figure Option ViewDownloadNew Window
	图9 节点平均剩余能量随时间的变化Fig.9 Node average residual energy vs.time

图10

Fig.10

	Figure Option ViewDownloadNew Window
	图10 节点最小剩余能量随时间的变化Fig.10 Node minimum residual energy vs. time

从图9、图10中可以看出, 当节点较多时, EEIABR算法的性能要优于EEABR算法。仿真说明, 蚂蚁包标识组合项和能量差异因子的引入可以更好地避免由于蚂蚁环路而消耗过多的发送能量, 在此基础上提升信息素更新的准确性, 使节点的能量分布更为平均, 说明适用于节点较多的无线传感器网络。