基于链路权重的无线传感器网络蚁群路由算法

2017-05-18◆李璐

网络安全技术与应用 2017年5期

关键词：路由时延链路

◆李璐

(大连海洋学校实验中心辽宁 116023)

安全模型、算法与编程

基于链路权重的无线传感器网络蚁群路由算法

◆李璐

(大连海洋学校实验中心辽宁 116023)

本文针对无线传感器网络存在网络拥塞进而造成网络服务质量急剧下降的问题，提出了一种基于链路权重的无线传感器网络蚁群路由改进算法。该算法通过分析可用带宽、传输时延两个影响链路状态的因素来计算链路的权重，根据链路权重来调整信息素的大小，直接反映了网络中节点的当前状况，避免了网络的局部拥塞，均衡了网络流量；通过自适应地调整链路权值的挥发系数，提高了算法的全局搜索能力。仿真结果表明，该算法有效控制了网络拥塞，均衡了网络负载分布。

无线传感器网络；路由协议；蚁群算法；链路权重

0 引言

随着计算机网络技术和传感器技术的快速发展，无线传感器网络技术（WSNs）已被广泛应用于各个领域，包括环境监测、军事安全和医疗监护等方面。这些领域的应用对传感器信息传输的服务质量（QoS）提出了更高的要求，而路由算法是无线传感器网络提高QoS的关键因素之一。因此，设计有效的无线传感器网络路由协议是提高QoS的重要手段。

本文从已有的无线传感器网络蚁群路由算法出发，提出了一种基于链路权重的无线传感器网络蚁群路由改进算法，依据每两个节点之间链路的可用带宽、时延等因素来综合计算链路权重，根据当前链路权重大小来改变信息素的值，从而避开拥塞链路，达到负载均衡的目的。

1 链路权重分析

传统的路由算法以路径长度作为路由评价标准，而没有考虑链路的状态，导致最短的路径未必最优。因此，在原有算法的基础上，引入每一跳的代价（权重），选择权重最小的路径，可以优化路由选择，提高无线传感器网络的QoS。而带宽和时延是影响链路状态的主要性能参数，本文利用这两个参数来计算链路权重。

两个节点之间链路的可用带宽、时延都不相同，节点与链路的负载越大，缓冲队列越接近饱和，其与邻居节点间的链路将越繁忙，可用带宽越少，传输时延越长，因而通信传输代价也就越高。

将无线传感器网络视为相互关联的无向图，设 G=(V,E)表示无线传感器网络，其中，V表示网络节点，E表示由节点集合组成的双向连接的链路。任意链路e E∈ 与QoS相关的主要指标为带宽B()e和时延D()e。从节点i到任意节点j的带宽和时延计算公式分别为：

其中， ()Be表示链路e E∈ 的带宽，D()e和D(n)分别表示链路e E∈ 时延和节点n V∈ 时延。

节点i到邻居节点 j之间链路的权重ijw 计算如下：

路由建立以后，路由层采用周期发送HELLO包的机制来维护路由。周期发送HELLO包可及时更新邻居节点表和对应的信息素分布，并更新与其邻居节点间的链路权重。

2 基于链路权重的蚁群路由改进算法

为了提高蚁群算法搜索全局最优解的能力，并有效避开拥塞链路，依据链路权重的变化来更新信息素的大小。在进行路径选择过程中，根据当前链路权重与设定的阈值的比值大小来更新路径的信息素，即：当链路权重小于阈值时，信息素强度Q就加上该链路的权重，否则就减去此链路权重。这样权重较小的链路增加的信息素就较大，增加了被选中的可能性。第k只蚂蚁在本次循环中留在路径(i,j)上的信息素的更新规则由式（6）表示。

其中， wij表示链路(i,j)的权重；w表示链路权重的阈值，初始值为 w0；Q表示信息素的增强系数；表示第k只蚂蚁走过路径(i,j)的长度。

所有蚂蚁经过链路后，各路径的信息素根据（7）式和（8）式进行更新：

式中，ρ表示信息素挥发系数，则1 - ρ表示信息素残留因子；表示本次循环中路径(i,j)上的信息素增量，初始时刻

3 仿真分析

采用典型无线传感器网络结构对该算法的有效性进行仿真验证，每个顶点用n〈d〉表示，其中n表示节点标号，d表示节点时延，节点时延假定为 1；每条链路用〈bw，dl〉表示，其中 bw表示链路的带宽，dl表示链路的时延。假定源节点为11，目的节点为20，开始时每条相连链路的初始信息素浓度相同，蚂蚁随机地选择路径，每次选择一个节点之后，对两个节点间链路依据路径的时延、带宽情况进行信息素更新，此后的蚂蚁选择路径会受前代蚂蚁的影响，经过n代更迭进而找到最优路径。