蚂蚁算法在无线传感网络通信中的研究

杨琦

1.引言

无线传感网络的广泛应用背景，更需要开展对其通信性能等理论研究工作，尤其在航空、军事、生产控制等方面，不容有半点失误，因此，如何保障传感器网络之间的性能安全可靠、稳定，以及动态自调整等是关键问题，但目前在无线传感网络领域尚缺仿真方面的理论研究。本文认为能实现对无线传感网络的通信模拟，可以避免无线传感网络通信应用后工作效率不高、预估各种问题、以及问题出现后的解决方案等。

2.无线传感网络通信的修正仿真算法

为了使用蚂蚁算法进行无线传感网络通信仿真，必须有效地进行算法中的各个参数和无线传感网络通信描述的对应。本文设置给定的n个传感器结点的集合为图中的节点，传感器结点之间存在流转，则设对应的图上有有向边存在，边上记录权：是若干条件规则因素组合的代价Cij（1≤i≤n，1≤j≤n，i≠j），并以此为信息素，这些信息素是根据上述算法的得出的已运行的无线传感网络通信或者根据用户经验实现赋值的，然后当无线传感网络通信的结点有变化时变迁应设计相应的算法使得它能够在原来的基础上集成原来的知识而快速寻出各种新的可能的无线传感网络通信。

（1）无线传感网络通信仿真的修正蚂蚁算法的数学基础

若将每个传感器结点看成是图上的顶点，代价Cij为连接顶点Vi、Vj边上的权，从第n个传感器结点之间向第一个传感器结点引一条有向边，且边上的权值为0信息素，则无线传感网络通信仿真系统最终希望得到的是在一个具有n个节点的完全图上找到一条有效无线传感网络通信的回路，其中假若无线传感网络通信执行中有任务反馈再执行，也由于其前驱结点的不同而认为是不同的结点。蚁群由m>n个蚂蚁组成，它们独立地按下面的步骤工作，所完成的算法就是无线传感网络通信仿真的修正蚂蚁算法（Sensor Correct Ants：SCA）。

（2）FCA算法描述

FCA算法的设计是：

1）m个蚂蚁独立选择一个起始传感器结点（初始化）;

2）应用状态转移规则及局部修正规则寻出一个无线传感网络通信路选上的环;

3）进行全局信息素的修正。

本文的蚂蚁算法可归纳如下：

1）分别对其在图G中各边上的信息度进行初始化;

2）取一组蚂蚁（由M个不同种类的蚂蚁组成），将其中每一个都随机地放到设定为起始初始节点的传感器结点;

3）令每个蚂蚁分别根据下面的转移概率准则寻找下一个新传感器结点，在选路过程中，若一个蚂蚁在未到达目的节点前发现此次路径已行不通，则其退回上一节点（年龄减去所退回的路径对应的时延），重新选择其他路径;若某一个蚂蚁未到达目的节点就已死亡，则应在初始点重新发送一个同类的蚂蚁。当成功地完成了任务流转，则利用下面的局部调整准则修改这两个节点间路径上的信息素（称为局部信息素修正）。重复该步骤直到流转至第n个传感器结点，最后回到初始状态。

4）对所有边上的信息素进行修正（称为全局信息素修正 ）。

5）在这N组中，依据选取综合效应最佳（即代价函数值最小）的一组蚂蚁所选择的无线传感网络通信路径结果，利用下面的全局调整准则对其进行信息度的全局调整;

6）重复（3）～（5），直到所有蚂蚁的收敛至同一最优的无线传感网络通信路径为止。

值得说明的是，上述蚂蚁仿真无线传感网络通信路选算法在初始一段时间内寻找有效无线传感网络通信路径的速度相对要慢些，这是由于随机选择无线传感网络通信路选过程中会出现蚂蚁死亡（传感器尚失通信能力等）的情况。为了加快蚂蚁的路径选取速度，可以对上述算法加以适当调整，即在初始时，对每个传感器结点，构造满足其时延条件的路由表，并在上述蚂蚁算法执行过程中，限制蚂蚁在规定的规则库表中选取通信路径中针对当前结点的下一个结点，这样就避免了蚂蚁死亡所造成的时间浪费，从而在很大程度上节省了各蚂蚁成功地选取其所对应的有效无线传感网络通信路径所需的时间。

（3）算法的伪代码表示

Begin：

初始化

Repeat for i ：=1 to m do

状态转移、局部修正、构造无线传感网络通信路径（每个蚂蚁都构造）

全局信息素修正（对最好的无线传感网络通信路径）

Unitl 结束条件

End

（4）算法中的状态转移规则

在FCA中需要进行传感器结点的状态转移，依据的是状态转移规则，也即蚂蚁选择下一传感器结点的概率（公式1[7]）是由两传感器结点连接边上的代价和信息素决定的。

（1）

式中表示蚂蚁 K从第r个传感器结点流转至第s个传感器结点的概率;表示蚂蚁储在边上的信息素;，表示边对应的代价;表示蚂蚁K在第r个传感器结点时还没有流转至的传感器结点集合;β>0为由信息素与代价的相对重要性来确定的参数。

式（1）表明蚂蚁从状态r转移到状态s所选传感器结点的概率随着信息素的增大而增大，随着代价的增大而减少，即状态转移规则是蚂蚁喜欢朝信息素大代价小的下一个传感器结点转移。

（5）算法中的全局信息素修正规则

为了分配更多的信息素到最佳的无线传感网络通信路径所在边上，必须修正信息素。另外一个目的就是模仿真实的蚂蚁不仅存储信息素还适当蒸发它们。因此，一旦m个蚂蚁按照公式（1）完成了一次图的遍历（即找到一个较佳的无线传感网络通信仿真结果）后，则必须用公式（2）修改各边上的信息素量。

（2）

其中，0<α<1是用来蒸发储在边上的信息素的参数，LK是蚂蚁K得到的无线传感网络通信所对应的路径上的代价和。全局修正规则不是由个别蚂蚁来实现，而是通过图的边来存储，起到了一个分布式长期记忆的效果。

（6）变异FCA算法

上述蚂蚁算法对较小规模的传感器结点（n个）情况下求解最佳仿真无线传感网络通信十分有效;但随着n的增大，效果明显下降。针对这一问题，本文又提出了变异FCA算法。该算法同前一算法描述一致，改进之处就是在状态转移，修正规则中引进了变异运算，以避免原算法在大规模的传感器结点情况出现局部最优。

1）FCA的状态转移规则

一个蚂蚁在传感器结点r执行后将按照下面的式子确定转移至的下一个传感器结点s：

S2随机地从JK（r）中选取，q为[0，1]上的随机数，q0为参数（0

2）FCA的全局修正规则

FCA的全局修正规则如下：α是信息素消散参数。0<α<1，Lab是m个蚂蚁中最好遍历代价之和。

与前一算法比较，FlowNAA的全局修正规则只是让实现最好遍历的蚂蚁释放信息素。它只是在已有的无线传感网络通信程内搜索出新的无线传感网络通信，这不仅适应实际的情况（无线传感网络通信仿真是在若干可以选择的无线传感网络通信中选择一条较优的，或者根据需要对原有的无线传感网络通信进行修改），从而提高求解的速度。

3）FCA的局部修正规则

若蚂蚁从节点r向结点s转移，则规定蚂蚁在这条边上存储一定的信息素修正规则如下：

这个局部修正规则保证避免搜索陷入局部极小陷阱，同时又给最佳的无线传感网络通信路径各边增加信息素。