搜索
蚁群算法在无线传感器网络中的应用综述姓名：张梦寒导师：刘剑飞（河北工业大学信息工程学院，天津，300401）摘要：大量的具有无线通信和数据处理能力传感器器件通过一定的协议构成自组织网络-无线传感器网络。这种网络可以有效的进行传感数据收集和传输。然而由于无线传感器网络具有自身的特点比如：通信、存储和处理能力较弱，有限的能量等，使得关于无线传感器网络的路由研究成为热点。本文中对该网络的特点以及路由算法要考虑的影响因素进行了分析，然后给出蚁群优化算法在无线传感器网络路由中的应用。该路由方法易于实现、基于局部信息、将多种影响因素以信息素形式表现出来。该路由方法的自组织、动态和多路径的特性比较适合应用于无线传感器网络的路由。关键词：无线传感器网络；蚁群算法；路由算法；信息素Abstract:Withalargenumberofwirelesscommunicationanddataprocessingcapacitysensordevicethroughthecertainagreementconstituteaself-organizingnetwork-wirelesssensornetwork.ThenetworkcanbeWitheffectiveforsensingdatacollectionandtransmission.However,duetothewirelesssensornetworkhasitsowncharacteristicssuchas:communication,storage,andhandlingabilityisweak,thelimitedenergy,etc.,makeaboutwirelesssensornetworkroutingresearchbecomehot.Inthispaperthecharacteristicsofthenetworkandtheroutingalgorithmtoconsidertheinfluencefactorsofthepoints.Analysis,thengivetheantcolonyoptimizationalgorithmintheapplicationofwirelesssensornetworkrouting.Keywords:Wirelesssensornetwork;Antcolonyalgorithm;Routingalgorithm;pheromone中图分类号：TP18文献标识码：A1引言随着微电子技术，计算技术和无线通信技术的进步，制造低功耗的传感器在技术上和成本上已经成为可能。传感器具有信息采集、数据处理和无线通信多种功能。通常传感器探测它周围的环境并生成电信号，并且处理这些信号使它们表现为传感器监测的目标或发生事件的属性。无线传感器网络(WirelessSensorNetwork)包含了很多传感器节点，这些传感器可以相互通信或是与外部的基站通信。大量的传感器可以保证精确探测一个很大的区域。通常传感器节点有传感器模块、处理模块、无线通信模块和能量模块。传感器模块负责监测信息的采集和数据转换；处理模块负责传感器的操作，存储和处理自身采集的数据以及其他节点发来的数据；无线通信模块负责与其他传感器节点进行无线通信，交换控制消息和首发采集数据；能量供应模块为传感器节点提供所需的能量[1]。为实现了减小能量消耗这个目标，一方面可以把已有的路由技术应用到无线传感器网络中，另一方面也可以设计专门适用于该网络的路由方法。例如：数据收集方法，簇方法，给每个节点分配不同任务，以数据为中心的方法。根据网络的结构，路由协议一般可以分成扁平网络和分层网络。在扁平网络中，每个节点都有相同的功能，而在分层网络中，局部的节点组成簇，簇头节点可以调整数据量的大小来达到节约能量的目的。基于位置的路由使用节点的位置信息来中继数据到目标区域。2无线传感器网络中路由的影响因素（1）节点部署传感器节点部署因应用情况而定，它影响路由协议的性能。节点部署情况分为确定部署和随机部署两种。在确定部署中，传感器被按照要求放置，数据经事先设计好的路径传输。在随机部署中，传感器被随机放置，整个网络是是一种对等方式的结构。如果整个网络中的节点分布式处理困难，那么局部节点优化成簇会是一个比较好的解决方法，它可以有效的使用能量保证网络的连接。由于传感器节点能量和带宽的限制，它们之间通常只能在比较短的距离内进行通信，因此一条路径由多跳组成。（2）能量消耗在无线环境下，传感器节点使用有限的能量进行计算和数据传输，因此要为这些通信和计算保证能量，而节点使用时间取决于电池的寿命。在多跳的无线传感器网络中，每个节点既是数据发送者也是数据接收者，因为能量耗尽导致节点失效会改变网络的拓扑结构，从而改变路由情况，重新组织网络路由[2]。（3）数据报告模型在无线传感器网络中，数据感知和报告取决于数据报告的应用和时间关键度。数据报告可以分为时间驱动，事件驱动，查询驱动以及混合型。时间驱动模型适用于对周期性监测数据的应用。传感器节点周期性的启动传感器和数据发送机制以探测环境传输数据。在事件驱动和查询驱动模型中，对于监控对象属性值突然发生剧烈变化或是基站发出的查询，传感器节点要立刻做出反应。这两种模型适用于对时间关键度十分敏感的应用。同时，这些模型还可以结合起来运用。（4）节点连接异构根据实际应用，一个传感器节点可能会有不同的任务和功能，异构的传感器节点会引起一些技术上的问题，这些专用的传感器可以单独部署，或是多个功能集成于一个传感器节点。而在这些节点中也因为不同服务的要求，数据读取和报告的速率也不相同，这种差异也会带来使用数据报告模型的不同。（5）容错性一些传感器节点因为能量耗尽，遭到破坏，或是环境的干扰失效，这些失效不能影响整个网络的正常运行。这时路由协议必须有机制重新建立路由。（6）网络动态性许多网络结构假设传感器节点是静态的，然而在有的应用中基站和节点有时是需要移动的，移动节点发送和接收路由消息是一个具有挑战性的课题，因为此时路由稳定性变得十分重要。3基于蚁群算法的路由蚁群算法是来源于对自然界蚂蚁群行为的观察和抽象。蚁群觅食时可以找到蚁窝与食物间的最短路径，这有赖于一种叫信息素的化学物质，蚂蚁来往于两者之间，它们释放信息素，为后来的蚂蚁提供路径向导[4,5,6,7]。这样的行为是对现实情况很好的反应，这种思想也适用于无线传感器网络。（1）路由模型模型中设无线传感器网络拓扑结构为一张无向图EVG,，vi表示传感器节点，V表示所有传感器节点的集合，如果两个节点可以vi和vj相互通信，则两者存在一条边eij，网络中所有边的集合表示为E。)(tij表示t时刻在边eij上沉积的信息素的浓度。每个节点维护一张信息素表，记录和它相连的边上信息素的浓度。各边信息素浓度更新按照以下公式进行：在t+1时刻，eij上的信息素值等于蒸发后残留信息素加上信息素增量之和。1,0表示信息素蒸发系数，1表示残留信息素系数，tij表示信息素增量。eij的信息素通过HELLO信息和回溯蚂蚁(BackwardAnt)进行更新，信息增量tij使用以下公式计算:Pi是当前节点vi的能量值，Pimax是vi能量最大值，Tij是一跳的往返时间(RoundTripTime)，Ni是vi的当前连接数，如果一条确定的路由通过该节点，则称该节点有一个连接。Tmax和Nmax是往返时间和连接数的阈值，，是往返时间和连接数的系数，它们共同限定信息素的值。该公式表明对于能量比较多，往返时间短，连接数少的节点信息素的增量比较大。(2)路由过程当源节点d希望与目的节点s通信，但是没有关于d的路由信息，s必须寻找一条从s到d的路径。通常s广播一个后应前行蚂蚁(reactiveforwardant)dsFA,，每dsFA,包含族群ID，代数，时间戳，源节点和目的节点信息，以及一个空栈，时间戳和栈用于记录前行路径情况。第一代蚂蚁作为自己族群的蚁后，每个族群都有一个ID。当中间节点接收到一个dsFA,时，它会将节点ID加入dsFA,堆栈中，同时查找路由表，找到信息素最高的下一跳。如果有几个结果可选择，则当前代蚂蚁生成相应数量新一代蚂蚁发送到这些节点。通过以上方法，蚂蚁可以很快扩散整个网络，从不同路径到达目的节点。这里有可能中间节点接收到同一族群中的蚂蚁，而且蚂蚁代数年轻，这种情况叫路由循环，这种情况下，节点直接丢弃蚂蚁，另外，如果蚂蚁前行时间或是跳数超过限制，节点也丢弃蚂蚁。为了防止一些节点过度使用，使网络资源得到充分使用，目的节点应当获得整条路径的境况，以便按照标准选择一条最佳的路径。在这里，中间节点不能对路由情况进行比较和决策，只有目的节点可以终止前进蚂蚁的路由过程，并且可以发出回溯蚂蚁来确定路径。蚂蚁到达目的节点后，目的节点获取蚂蚁中路径信息，并计算路径信息素的值与其它蚂蚁的路径信息素值进行比较。整条路径的信息素计算如下：Tsd整个路径的往返时间，Hsd是路径的跳数，Tt和Ht是相应的阈值，a,b是调节因子，它们共同决定了路径的信息素值。目的节点都有一个对应于源节点的计数器，用于记录时间和蚂蚁的数量。计数器以第一只到达目的节点的蚂蚁到来之时进行计数，当数量或时间超过阈值,目的节点将停止接受来自该源节点的蚂蚁。目的节点通过比较各路径上信息素的值，得出最优路径，并且向该路发送回溯蚂蚁，按照路径节点反向顺序到达源节点，并更新经过连接的信息素值。源节点接收到回溯蚂蚁开始发送数据，如果在限定时间内没有收到回溯蚂蚁，源节点将发送前行蚂蚁，重新进行路由发现。(3)路由信息的更新通过上述方法进行的路由一旦建立，源节点将向目的节点发送数据，但是网络的拓扑结构是变化的，因此各节点需要更新信息。传感器节点以一定速率发送前应蚂蚁(proactiveant)来探测路径。这种蚂蚁像数据包一样单播出去，有两个作用：一是证实路径依然有效，另一个作用是更新源节点和目的节点的信息素表。当该蚂蚁到达路径上的节点，它就收集上面的信息素的信息，当到达目的节点后，就用这些信息更新它的信息素表。然后，目的节点就会发送回溯蚂蚁，它的任务是更新源节点的信息素表，这样源节点可以按照新的信息素表进行路由。无线传感器网络中每个节点需要知道它相邻节点的信息，包括每一连接的往返时间，可用带宽，以及信息素的值。为了能够及时准确反映网络状况，需要发送HELLO消息探测与邻居的连接状况，更新路由信息。HELLO消息包括发送节点ID，时间戳，以及可用带宽。HELLO消息每隔一段时间(比如1秒)广播一遍。接收到这个消息的节点，用当前时间减去时间戳来计算RTT，然后检查该消息发送节点是否在邻居表中，如果在就更新邻居表中相应的值，如果不在就在邻居表中添加该节点信息。该节点再发送一个HELLO信息给发送节点以更新它的邻居表。以此方式，每个节点都会周期性的收到这样的信息，及时了解邻居节点的情况。在网络中，每个节点通过与邻居交换HELLO信息更新来跟新信息，如果某个连接失效，也能很快的发现。一个节点可以通过收到邻居节点的HELLO信息或发送过来的包来证实邻居节点的存在。节点通过邻居间发送HELLO消息来更新路由信息，因此也能很快的发现连接失效。如果邻居节点在一定时间内没有返回消息，则可以简单的把该节点从邻居表和路由表中删除。相应的，该失效节点两端的节点发送信息给源节点和目的节点，它们将从路由表删除这条路径。4结束语本文介绍了无线传感器网络概念和特点，分析以及设计网络路由协议所面临的挑战，给出了了基于蚁群优化算法的无线传感器网络由算法。该路由算法考虑了网络的特点，具有自组织性，动态性。信息素的计算方法考虑了能量，往返时间，跳数等多种因素。因此比较适合无线传感器网络的路由。最后，衷心感谢河北工业大学夏克文教授在百忙中审阅此论文，同时感谢夏克文老师对本工作的指导。参考文献[1]Akyildiz,W.Su,Y.Sankarasubramaniam,andE.Cayirci,Asurv