基于元胞自动机的AODV能量均衡研究

摘要：AODV是一种按需式路由协议，能快速的找到目的地节点，损耗节点的能量较少，是比较优秀的自组织路由协议。AODV协议从节点的较大看，能量消耗较少，但能量并不均衡，从而导致网络出现空洞，缩短了网络的寿命。本文提出了基于元胞自动机的AODV能量均衡方法，该方法将传感器节点定义为元胞，建立元胞之间的规则，把邻居的能量作为路由的影响因素。利用NS2对加入的元胞自动机模型进行了验证，仿真结果表明该方法能有效的控制网络的能量达到均衡。

关键词：元胞自动机；能量均衡；无线传感器网络；AODV

中图分类号：TP391文献标识码：A文章编号：1009-3044(2011)08-1863-02

Study of Energy-balancing Wireless Sensor Network Based on Cellular Automata

HAN Li-li1, LIU Xiu-ping2

(1.School of Information and Control engineering, Xi'an University of Architecture & Technology, Xi'an 710055, China; 2.School of Xidian University, Xi'an 710071, China)

Abstract: Prolonging the lifetime of wireless sensor network is one of research topic in the field of WSN.we propose energy-balancing control based on Cellular Automata.The energy of node is divide into 4 category.The route depend on energy of node and its neighbor node.The simulation results shows the CA model can benefit from energy-balancing control and prolong the lifetime of wireless network sensor.

Key words: cellular automata; energy-balance; WSN; network performance

随着物联网概念的提出到大量的研究，使得无线传感器网络在环境监测、物联网管理、医疗健康监护和军事领域的战场态势感知等方面都有不同程度的应用。随着传感器节点的增加，无线传感器网络逐渐成为一个复杂的自组织网络系统，而对于能量受限的无线传感器网络的能量均衡问题也更为复杂。因此，研究复杂自组织的无线传感器网络的能量均衡问题对延长网络寿命、协议设计等有重要的应用价值。

Wolfram等者对元胞自动机的演化行为进行了明确的划分，在此基础上很多学者利用元胞自动机在生命科学、信息科学等方面做了大量的研究。文献[1]利用元胞自动机揭示了网络的行为和时空相关性。文献[2]利用元胞自动机模型研究了无线传感器的整体行为存在振荡、衰减、稳定等模式。文献[3]研究指出自组织网络的本质在于系统内节点间内在相互作用。针对于无线传感器网络的能量整体行为和局部行为研究较少。本文通过建立二维元胞自动机模型，研究大规模的无线传感器网络中节点间的内在作用对能量整体的影响，这将对协议的设计、网络的控制及延长无线传感器网络的寿命等有重要的应用价值。

1 元胞自动机

元胞自动机模型是处理非线性复杂动力系统非常有效的工具。用元胞自动机来模拟一个复杂的动力系统时，时间被分成一系列离散的瞬间、空间被分成一种规则的格子，每个格子用若干数据表示其状态。在每一个时间间隔，网格中的格子按照一定的规则同步地更新它的状态，这些规则由所仿真的实际系统的真实物理机制来确定。网络蠕虫病毒的传播是一个复杂的动力系统，可以应用元胞自动机模型对其演变行为进行仿真研究。

根据元胞自动机的定义，用数学符号表示，元胞自动机可以看作有一个元胞空间和定义于该空间的变换函数组成。元胞自动机用形式语言的方式来描述，可以定义为如下四元组：

A=(Ld,S,N,f)

其中，A代表一个元胞自动机系统；Ld 代表一个规则划分的d维网格空间，d通常是一维或二维空间，理论上可以是一个任意正整数,在此d=2；S代表各个元胞的状态的离散有限集合；N代表单个元胞的邻域内元胞状态的组合（包括中心的元胞）；假设元胞的邻居个数为j，则N=(S1 , S2 , S3 , …,S j) ; Si∈Z（整数集合），i∈1,2,…,j; f代表一个将Sj 映射到S上的一个局部转换函数，又称为局部规则或状态转换函数。也就是根据t时刻某个元胞的所有邻居的状态组合来确定t＋1时刻该元胞的状态值。演化规则可记为：

其中，Sit+1为第i个元胞在t+1时刻的状态，Sj1t, Sj2t , …,Sjnt为Sit所有邻元的集合。

2 无线传感器网络能量的元胞自动机建模

无线传感器网络的数据传输需要路由协议的支持，但多数协议虽然从能量角度进行了考虑，但并没有将能量作为路由的影响因素。

路由建立时，当前节点是否进行参与路由，需要根据元胞及其邻居元胞的状态进行决策。

无线传感器网络的主要瓶颈在于能量的不均衡导致网络的寿命较短[4]。传感器节点分为四种状态：空闲状态（I）、发送状态（T）、接收状态（R）和休眠状态（S），并将空闲状态和休眠状态称为消极状态，发送状态和接受状态称为积极状态，这四种状态所需要的能量也不同，各状态所占比例如图2所示。

由于IC技术的发展，传感器的感知模块和数据处理模块都采用了低功耗技术，能量消耗所占比例较小；大部分的能量消耗在无线通信模块上 。我们基于元胞自动机模型的无线传感器网络的研究的重点就在于如何利用传感器节点的邻居的已知信息来使无线传感器网络的通信模块的能量达到最优化。

将无线传感器网络的节点的能量表示为四种级别：充足能量(E)、中等能量(M)、警告能量(W)和欠能量(L)。充足能量(E)节点表示该节点可做积极操作的通信任务。中等能量(M)表示该节点的能量处于临近能量，以一定概率做积极操作和消极操作；警告能量(W)表示该节点处于危险期，尽量减少去做积极的操作；欠能量节点(L)表示该节点已经无法提供通信功能，网络中如果出现这样的节点，说明网络已出现了空洞现象。这四种级别的能量是针对于整个网络而言的一个相对指标，并周期性的统计网络的能量级别。

基于元胞自动机模型的网络路由协议是采取按需路由的方式，网络中的节点不是实时的更新路由信息，而取决于传感器节点是否传输信息；如果有数据发送且没有达到目的地路由时，会启动路由请求。

路由建立的过程包括建立反向路由和建立前向路由两部分。在达到需要建立路由的条件时，源节点首先在路由表中检查，如果路由表中没有目的节点，或者路由表信息已经过期，那么，源节点将向邻居节点广播一个路由请求分组。当中间节点收到广播的路由请求分组时，首先，检查路由表中是否有到达目的节点的路由，如果有，则根据该节点的能量级别及邻居的能量级别来确定回复路由响应的延迟；延迟越小，越有利于路由的选择。如果没有，则检查自己的地址是否与目的地址相同，如果不同，则根据源地址和广播ID判断是否收到过该请求信息，如果收到过，则丢弃该消息，如果没有收到过，则记录相应的信息，形成反向路由。并向邻居节点转发该路由请求分组；如果自己是目的节点，则回复路由响应分组，并沿着反向路由到达源节点，则就建立的前向路由。

该路由协议的重点在于确定本节点及邻居节点的能量级别与回复路由响应的延迟的关系。也就是说，在建立路由时，中间节点根据自己的能量级别和邻居节点能量级别，进行适当的延迟，能量级别越高，延迟越小，这样，建立好的路由也就偏向于链路的能量较高的路径。

如果t时刻，该元胞是充足能量(E)节点，当其邻居元胞中的充足能量(E)节点(M)>=2，可以进行积极状态的操作，如发送和接收数据，则t+1时刻该元胞延迟0s；

当其邻近元胞中的欠能量(L)节点>=1，则t+1时刻该元胞延迟∞秒，并将该节点剔除；

否则，在t+1时刻，该元胞延迟0.5d秒；

如果t时刻，该元胞是中等能量(M)节点，当其邻居元胞中的充足能量(E)节点(M)>=2，可以进行积极状态的操作，如发送和接收数据，则t+1时刻该元胞延迟0.1d秒；

当其邻居元胞中的中等能量(M)>= 3，则t+1时刻该元胞以一定概率进行延迟0.01d秒；

当其邻近元胞中的欠能量(L)节点>=1，则则t+1时刻该元胞0s延迟，并将该节点剔除；

当其邻近元胞中的警告能量(W)>=2，则t+1时刻该元胞延迟0s；

如果t时刻，该元胞是警告能量(W)节点，当其邻居元胞中的充足能量(E)节点(M)>=2，可以进行积极状态的操作，如发送和接收数据，则t+1时刻该元胞延迟10d秒；

当其邻居元胞中的中等能量(M)>= 5，则t+1时刻该元胞延迟2d秒；

当其邻近元胞中的警告能量(W)>=2，则t+1时刻该元胞以一定概率延迟0.01d秒；

当其邻近元胞中的欠能量(L)节点>=1，则t+1时刻该元胞0s延迟，并将该节点剔除；

如果t时刻，该元胞是欠能量(L)节点，则t+1时刻该元胞延迟∞秒，即该节点被不能路由选择，并将该节点剔除；

其中，d为中间节点根据自己的能量的情况作时延处理，节点延迟的时间按照[6]：

e为当前的能量值，E为初始能量值，D为最大延迟值。文献证明了d能达到较好的延迟效果，本文采用此式作为延迟尺度。

3 实验结果

利用NS-2.29仿真平台验证提出的基于元胞自动机的AODV均衡路由协议，网络的节点为100个，仿真区域为1200m×1200m的平面内，仿真时间为100s。节点初始能量为1000J,发送功率为0.6mW，接收功率为0.3mW，空闲功率为0.25mW，睡眠功率为0.06mW。汇聚节点在网络的中心，网络中的节点采取随机通信的方式，如图3所示，红色为汇聚节点，蓝色为感知和转发节点。

网络生存时间为从网络工作到出现第一个能量耗尽的节点为止的时间长度。通过控制网络能量的达到均衡的方式，可以延长网络的寿命。对搭建的以上环境进行了仿真，如图4所示。

从仿真结果看出，网络中的100个节点的能量基本均衡，只有汇聚集节点的能量较低，可通过某种方式充电获取能量，这并不会影响网络的寿命；有些节点的能量损耗较大，是由于在汇聚节点的附近，进行了大量的转发导致。

4 结论

传感器节点的能量问题是无线传感器网络的瓶颈。利用元胞自动机模型对网络节点进行了建立规则，对能量均衡进行控制。结果表明，利用该模型有利于能量均衡，延长网络的寿命，并对网络的性能进行了分析，分析结果显示并没有增加性能指标的额外开销。因此，也表明元胞自动机模型对无线传感器网络在能量均衡方面有一定意义。

参考文献：

[1] Yuan J,Ren Y,Shan X.2000 Phys. Rev. E. 61-67[Z].

[2] 张文铸,袁坚.基于元胞自动机的无线传感网络整体行为研究[J].物理学报,2008,57(11):6898-6900.

[3] Tubbs S L.A Systems Approach to Small Group Interaction[M].NewYork:McGraw 2Hill,2003.

[4] 孙利民,李建中,陈渝.无线传感器网络[M].北京:清华大学出版社,2005.

[5] 孙利民,李建中,陈渝,等.无线传感器网络[M].北京:清华大学出版社,2005.

[6] 蒋敏,施惠昌,尹斌等.基于能量感知的AODV路由协议[J].传感器与微系统,2008,27(3):18-23.