无线传感器网络(WSN)是一种涉及多学科的新型无线网络。它综合了传感器技术、网络通信技术、无线传输技术、嵌入式计算技术、软件编程等技术，是通信和计算机科学的一个研究热点领域。WSN网络通常部署在自然环境复杂的区域，节点的供电非常有限。因此如何在保证数据传输可靠性没有明显降低的情况下，尽量减少节点能耗是目前研究的主要方向之一。

目前WSN节能的研究虽取得了一些成果，但仍存在以下问题：未能使用网络仿真软件对二维元胞自动机进行网络仿真；尚处于数学算法研究阶段；缺少将元胞自动机技术与网络协议相融合的实例。文献^[1]提出一种基于IEEE 802.15.4/Zigbee网络的整体休眠策略，核心思想是以划分时隙的方式实现整个网络同步工作或休眠，即包括路由节点在内的所有节点在工作时间传输并储存数据信息。当休眠时隙到来时所有节点休眠，工作时隙到来时所有节点工作，传输缓存的数据信息。文献^[2]针对将元胞自动机模型用于无线网络拓扑控制的问题，提出基于覆盖度和连通度的考量标准下的元胞自动机模型，建立该模型的拓扑控制方法，并仿真其有效性。文献^[3]基于IEEE802.15.4/Zigbee网络比较AODV协议与树形路由Zigbee协议在节能上的表现，提出了一种混合路由机制。文献^[4]提出基于元胞自动机的动态自组织算法，节点根据邻居节点的工作/休眠状态切换自身工作状态，平均节点能耗。但该机制缺少全局控制的针对性，对待检测区域缺乏可靠性，不适用于无线多跳网络。文献^{[5, 6]}指出自组织网络性质的决定性因素在于系统节点之间的内在交互作用，而不是外界干扰或边界条件的影响。

本文基于元胞自动机机制，在路由层设置元胞处理模块(CA-modular)，通过路由报文中捎带CA信息，网络节点自组织形成以sink节点为中心的多级元胞自动机区域。sink节点元胞处理模块根据CA信息和状态转换机制决策是否应使某些子节点进入休眠状态。休眠节点定时器超时时，节点恢复工作状态。该机制能降低无线传感网络整体能量消耗，提高能量利用率，延长整个网络生存时间。

二维元胞自动机(CA)是一类时间、空间、状态都离散的动力学系统，其基本特点是：散布于规则网格中的每一元胞均取有限的离散状态，各元胞遵循相同的演化规则进行更新^[7]。元胞自动机的核心元素包括：节点状态集合、节点状态总数、节点邻居集合和节点状态转换规则。即元胞自动机A可以用4元组表示为$A = (S,k,N,f)$，其中，S代表节点所有可以处于的状态，k代表节点的状态总数，N为节点邻居集合，F为状态转换规则^[8]。

无线传感网络由大量分布式的微小传感器节点构成，每个节点只能与周围临近的节点进行通信，并依靠局部信息做出行为决策。而元胞自动机能够以简单的规则揭示复杂的全局特性，并且结构简单、易于计算机实现。因此，本文首先构建面向无线传感网络的二维元胞自动机模型。该模型建立二维元胞自动机与实际无线传感网络的映射关系，包括元胞空间与节点空间、元胞邻居集与节点邻居集、元胞状态集与节点状态集、元胞状态转换规则与节点状态更新等要素间的对应关系。

考虑一个平面分布的无线传感器网络，N个静态独立的传感节点以随机的方式布撒在一个包含$L \times L$个格子单元的规则二维网格中，网格即代表一个二维元胞空间。为简化分析，假设一个网格单元至多包含一个传感节点，这个平面无线传感网即构成元胞空间，一个传感节点就是元胞空间中的一个元胞。任何节点在空间中的位置可以用该二维网格中的水平坐标i和垂直坐标j唯一标识。记$C(i,j)$表示处于$(i,j)$坐标的节点或元胞。元胞空间记为：

由于信号强度路径衰减，每个节点存在最大通信距离${R_{\rm{c}}}$，二维元胞模型中的邻居定义由该最大通信距离决定。定义节点邻域为Moore型结构，定义节点$C(i,j)$的通信邻居集合为：

本文考虑传感器节点采用S-MAC协议，即每个节点在每个round周期按照工作与休眠两个阶段的方式工作。节点根据唤醒规则选择自己处于工作状态或休眠状态。当处于工作状态时，节点则对周围环境进行检测并进行必要的处理；而处于休眠状态时，节点将进入休眠状态以节省能量。因而可以定义$k = 2$，$S = \{ 1,0\} $。“1”状态表示节点工作；“0”状态表示节点休眠。

设t时刻sensor传感器节点$C(i,j)$的状态为$S_{C(i,j)}^{(t)}$，其邻居状态之和定义为：

对于任意节点$C(i,j)$，按照状态转移规则有:

即$t + 1$时刻的节点状态是由t时刻该节点邻居状态按照一定规则$f( \cdot )$确定的。

无线传感器网络中随机散布的sensor传感器节点以自组织形式构成网络，通过多跳中继方式将监测数据传到sink节点。本文的无线传感网络拓扑形式为星形，由一个中心sink节点和若干sensor传感器节点组成。sensor传感器节点为同质性节点，具有数据采集和数据中继功能，所有sensor传感器节点将数据传输至中心sink节点。中心sink节点能量无限且一直处于工作状态。只有中心sink节点有决策休眠功能，即sensor节点的休眠或工作状态由中心sink节点控制。

图 1

图 1 基于多级分区元胞自动机的多跳WSN

sensor节点启动后，以sink节点为逻辑中心自组织形成多个元胞自动机CA区域，如图 1所示。CA区域共包括3种等级节点。中心sink节点为零级节点，sink节点单跳通信范围内的sensor传感器节点为第一级节点，第一级节点单跳通信范围内的sensor传感器节点为第二级节点。sensor节点的通信级别至多两级。节点启动时不具有等级信息，通过CA区域构建过程确定节点等级，且仅具有唯一一种等级。数据传输过程中，第二级节点传输数据经第一级节点至sink节点。

在CA区域的构建完成后，每间隔一段时间，sink节点根据邻居节点(第一级节点)的能量状态信息，选择部分能量较低的节点进入休眠状态，邻居节点收到休眠通告后转发给下属的第二级节点并进入休眠状态。节点休眠前设置休眠定时器，当休眠定时器超时时，恢复工作状态。

该系统需要修改节点协议栈，在路由层添加CA处理模块。CA模块采用事件驱动机制，记录并更新邻居状态集N，实现元胞自动机的状态转换规则f(×)。协议栈如图 2所示。在通信过程中，节点路由层报文将附加CA处理模块的CA信息，以捎带的形式随路由报文传输。CA信息包括信息类型、节点ID号和节点剩余能量，其中信息类型如下面所述的CA_start、CA_startsecond和CA_response等。收到路由报文的节点根据报文中的CA信息更新本地的CA信息表并根据状态转换规则切换工作与休眠状态。

图 2

图 2 协议栈

CA区域构建过程中的报文交互如图 3所示，构建步骤如下所述。

图 3

图 3 CA区域构建的报文交互过程

1) sink节点和sensor节点开机。sink节点查询本地CA表，CA表记录了邻居节点的节点ID、节点等级和剩余能量信息。若CA表为空则触发CA区域构建过程。

2) sink节点将CA构建信息(报文头部的信息类型字段为Type_CA_start类型)置于目的地址为广播的路由报文中发送(如AODV路由协议中的request类型和hello类型报文)，发起CA区域构建。定义该类报文为CA_start。

3) 收到CA_start报文的节点，将自身节点的类型定义为第一级节点。首先构建CA_response类型报文(报文头部的信息类型字段为Type_CA_response)，随目的地址为源节点的单播路由报文(如AODV路由协议中的response类型报文)发送给源节点，此处源节点即步骤2)中所述的sink节点；然后构建CA_startsecond类型报文(报文头部的信息类型字段为Type_CA_startsecond)，用于第一级节点发现并建立与第二级节点的联系。报文构建完成后置于目的地址为广播的路由报文中发送。

4) sink节点收到CA_response报文后，记录该节点IP、级别和能量等信息于自身CA表中。

5) 无级别的sensor节点收到CA_startsecond类型报文时，将自身节点的类型定义为第二级节点，构建报文CA_response，发送给源节点。一个已经有级别的sensor节点再收到CA_start或CA_startsecond类型报文时，若自身级别小于构建报文级别时(CA_start为第一级报文，CA_startsecond为第二级报文)，将放弃原级别，改为新级别，即某区域的第二级节点可以变为其他区域的第一级节点。

6) 若某节点处于sink节点两跳通信范围以外则有可能无法成为任何节点的子节点，这种类型的节点被称为无等级节点。无等级节点不能进入休眠状态。因此在网络部署时应尽量保证各CA区域范围之和能覆盖全部节点。至此，CA区域构建完成。

无线传感器网络对于待检测区域采取冗余配置的方式，使用多个传感节点对同一区域或目标进行检测，保证数据采集可靠性。对同一区域或目标的检测通常是重复性的，因此在保证可靠传输的基础上，使部分冗余节点进入休眠状态以节省能量是必要且有效的。

本文定义的转换规则如下：除sink节点外的其他节点取0/1两种状态，分别代表休眠和工作状态。sink节点根据当前状态和状态转换规则决策部分子节点进入休眠状态。子节点进入休眠状态前，通告其自身的所有子节点进入休眠状态。节点进入休眠时设置休眠定时器，定时器超时时节点恢复工作状态。

影响sink节点决策休眠的因素主要体现在无线传感器网络节点冗余配置情况和节点的剩余能量两个方面，可表示为：

式中，$N{\rm{\_sleep}}$表示可以休眠的节点数：R表示冗余率；N表示网络总节点数；k为冗余节点中进入休眠状态的节点比例。

无线传感器网络节点冗余配置情况将影响休眠决策，由式(5)可见，sink节点根据网络冗余率R计算邻居节点中冗余节点个数，判定冗余节点个数的k%进入休眠状态。此外，节点剩余能量将影响休眠决策。每个第二级sensor节点定时向第一级sensor节点汇报能量情况，第一级sensor将自身能量和所有第二级sensor 节点能量计算平均值后，发送给sink节点。sink节点记录第一级sensor节点通告的剩余能量情况。

sink节点记录第一级sensor节点通告的剩余能量情况，根据冗余率R和式(5)计算可以进入休眠状态的节点个数。sink选择剩余能量最少的N_sleep个第一级sensor节点，对这些节点发送休眠通告报文。休眠通告报文随目的IP地址为广播的路由报文发送，具有类型字段值为Type_sleep和节点ID字段。收到广播路由报文的节点根据类型字段值和节点ID字段值，识别自身节点是否为可休眠节点。若自身节点为可休眠节点，则对本节点的子节点发送休眠通告报文。可休眠节点设置休眠定时器后进入休眠状态，休眠定时器持续时间t秒后唤醒节点。休眠状态节点不具有发送接收功能。当休眠定时器超时时，节点恢复工作状态。

子节点收到休眠通告报文后同样完成上述过程。第二级节点不能发送休眠通告报文。无等级节点不能进入休眠状态，因此在网络部署时应尽量保证各CA区域范围之和能覆盖全部节点。

本文定义休眠/唤醒周期时长为2倍休眠定时器持续时间，用以避免节点频繁地在工作和休眠状态之间切换，从而保证网络的稳定性。sink节点在每个休眠/唤醒周期对子节点进行一次状态转换决策。

利用NS2仿真软件对基于元胞自动机模型的无线网络进行模拟。仿真中考虑了两种类型的无线传感网络：1) 网络的节点为未加入元胞自动机处理过程的普通节点；2) 网络的节点为加入了元胞自动机的CA节点。对这两类无线传感网络的总体能量消耗、能量利用率和传输率进行了比较，并且限制节点能量，仿真两种模式下剩余节点数随时间变化的情况。

仿真拓扑分别设置为5 x 5格状拓扑和7 x 7格状拓扑，如图 4所示。在5 x 5格状拓扑中，拓扑中心有1个sink节点接收传感数据和决策休眠；7 x 7格状拓扑，在拓扑中有3个sink节点接收传感数据、划分CA区域和决策休眠。拓扑方格中I代表在CA区域划分后成为第一级节点，II代表将成为第二级节点，none代表将成为无等级节点。每一个CA区域以sink节点为中心，其边缘节点可能是第二级节点也可能是第一级节点。每一个节点只存在于一个CA区域中，不会存在区域重叠节点。表 1为仿真参数设置。

表1

表 1 仿真参数设置

表 1 仿真参数设置 仿真参数 值 网络规模 24/48个Zigbee节点，1/3sink节点 最大传输距离/m 50 MAC协议 IEEE802.15.4 信道类型 双向信道 传输速率/kbs-1 250 报文长度/Byte 800 数据采集间隔/s×个-1 1 路由协议 AODV

图 4

图 4 仿真拓扑

图 5为5 x 5拓扑和7 x 7拓扑的整体能量消耗。在此过程中节点能量无限。能量消耗包括传感节点发送、接收和侦听过程中的能量消耗。节点从第50 s开始发送传感数据。采用CA机制后，节点首先完成CA区域构建，然后sink可以根据节点工作状态决策部分节点进入休眠状态，因此，降低了整体能量消耗。对5 x 5拓扑和7 x 7拓扑，总能量消耗大致分别减少了10% ~30%。

图 5

图 5 整体能量消耗图

图 6比较了两种网络的能量利用率。t时刻的能量利用率为t时刻以前传输数据报文所消耗的总能量与t时刻以前传输所有报文所消耗的总能量之比。由图 6可见，采用CA机制后能量利用率提高了10%～20%。并且节点数少时，能量利用率高于节点数多时的能量利用率。分析其原因在于，当节点数增多时，在路由等方面的开销更多，CA区域构建过程更复杂，时间更长，导致能量利用率下降。通过使用CA处理机制，使节点在合适的情况下休眠，可以降低网络冲突，减少空闲侦听和冲突重传带来的开销，从而提高能量利用率。

图 6

图 6 能量利用率

在图 7中，限制每个节点的能量上限为4 J，在正常工作模式下约可以工作500 s。由于不同节点的负载不同，负载重的节点能量消耗快，负载轻的节点能量消耗相对慢一些，所以不是所有节点在同一时刻能量耗尽，而是整个网络中的节点能量逐渐耗尽。由图 7可见，采用CA机制后节点生存时间明显变长，节点能量耗尽速度明显下降，整个网络的生存期得到提高。

图 7

图 7 节点生存时间

图 8展示了两种拓扑下采用CA机制和未采用CA机制的传输率对比。t时刻的传输率为t时刻以前PAN节点收到的数据报文个数与t时刻以前传感节点发送的数据报文个数之比。传输率能够从整体上准确反映网络传输可靠性。由图 8可见，网络运行初期，采用CA机制与未采用CA机制的传输率均在80%以上，能够保证传输可靠性，满足用户的可靠性需求。随着节点能量的消耗，未采用CA机制的网络的传输率明显下降，逐渐下降至80%以下。节点采用CA机制后，sink节点协调部分节点进入休眠状态，保证了网络的整体稳定性。开启CA机制后，曲线出现交叠现象的一个原因是节点在休眠和工作状态进行切换，影响了数据传输路径和可靠性。某时刻进入休眠状态的节点多，网络传输率下降; 某时刻进入休眠状态的节点少，网络传输率上升，从而使曲线在一定范围内浮动。而对于未开启CA机制的网络，随着路由的建立，整体网络趋于稳定，从而传输率基本稳定。

图 8

图 8 传输率

本文提出了一种基于多级分区元胞自动机的多跳无线传感器网络路由节能技术。通过设计元胞自动机状态转换规则，中心sink节点选择部分剩余能量低的sensor节点进入休眠状态，从而使得节点能够通过元胞自动机的状态转换规则，在休眠和工作状态间进行切换。剩余能量等信息随路由报文传输，无需增加额外的开销。本文的休眠决策机制通过合理使用元胞自动机处理机制，在网络层的路由协议中添加CA处理模块，在保证网络传输可靠性的基础上，减少了节点能量消耗。仿真验证了使用CA处理机制在网络传输率没有大幅下降的前提下，在减少能量消耗、延长网络生存期和提高能量利用率上的良好效果。在后续研究中，将进一步对基于元胞自动机的无线传感网络节能问题展开更深入研究。针对具有自组织特性的无线传感网络时空演化规律，研究如何在尽量减少系统能量消耗的前提下，保证无线传感网络拓扑的连通性和覆盖性。