无线传感器网络WSN(Wireless Sensor Network)是一种由大量具有数据采集、处理及通信功能的传感器节点，通过相互协作形成的分布式自组织网络，在军事侦查、工业控制和环境监测等领域有着广泛的应用^[1].由于单个传感器节点的电量、计算能力、存储能力和通信能力有限，WSN本质上是一类资源受限的网络.WSN中的传感器节点依靠有限电量的电池供电，更换电池或补充电量非常困难^[2].因此，如何有效利用能量成为WSN领域研究的重点.尽管众多学者在传感器硬件技术飞速发展的同时针对WSN做了大量研究，目前，能量约束依旧是制约大规模WSN应用的关键问题.因此，在WSN资源受限的条件下，如何有效地降低节点能量消耗、延长网络生命周期对大规模WSN的推广和应用具有重要的理论意义及实际应用价值.

1 相关工作

为了节省能量，进而最大化网络生命周期，近年来国内外学者及研究人员在节点功率控制和拓扑控制方面做了大量的工作，取得了一定的成绩.基于分簇拓扑的路由协议能有效降低节点能耗、延长网络生命周期并提高网络的可扩展性.LEACH^[3](Low-Energy Adaptive Clustering Hierarchy)协议是由MIT的Heinzelman等人最早提出的分簇路由协议，它将网络的运行按“轮”划分，每轮循环从网络中以等概率随机选择簇头节点，将整个网络的能量负载均匀分配到每个传感器节点，有效降低了节点能耗、延长了网络生命期.LEACH路由协议采用层次结构，簇头的选择算法保证等概率且容易实现，各节点只需存储少量的路由信息，且与传统的路由协议相比具有更高的能量利用效率.尽管如此，LEACH路由协议仍存在一些不足之处^[4-5]：簇头节点以等概率随机选取，没有考虑节点的自身状态及其所处的实时环境等因素，可能出现不合理的分簇，影响能量利用效率.

针对LEACH协议在簇头选择上存在的不足，国内外众多学者相继提出了一系列改进方案.文献[6]提出在选举簇头时考虑节点的能量以及位置状况，将能量、密度和距离参数引入LEACH算法以修正簇头当选的阈值，以此让网络中综合性能更优的传感器节点担任簇头，改进后算法在节点能耗及网络生命周期方面比LEACH更优；文献[7]提出了基于节点分布密度、剩余电量和信号强度等综合因素的LEACH-T算法，在簇头选举时，能根据上述综合因素均衡划分各个簇的规模，与LEACH相比能进一步降低节点能耗，延长网络寿命；文献[8]提出了I-LEACH算法，将节点的剩余能量和节点到基站的距离作为簇头选取的参数，通过GPS定位把网络划分为4个象限并分别为每个象限内的节点指定阈值计算公式，在节点能耗和网络寿命方面取得了较好的性能.针对簇头选举不合理而改进的文献还有很多，但大都是对LEACH算法阈值计算公式的改进，在适用性和扩展性上存在局限性.

本文以增强系统灵活性、均衡节点能耗以及延长网络生命期为目的，通过将约束引入角色协同模型，即E-CARGO^[9](Environment-Class, Agent, Role, Group and Object)模型，进而将带约束的E-CARGO模型用于分簇型无线传感器网络系统建模，提出了一种改进的LEACH协议模型，从机制上实现对LEACH协议的改进.理论分析了该模型的可行性，并以能量和位置约束为例，通过仿真实验验证该方法的有效性.

2 LEACH协议与E-CARGO模型 2.1 LEACH协议

LEACH是WSN中经典的分簇路由协议，它的执行过程以“轮”为单位，每轮循环包括簇的建立阶段和数据传输阶段.在簇的建立阶段，网络中所有的传感器节点生成一个介于0和1之间的随机数，如果该随机数小于由式(1)计算得出的阈值T(n)，则该节点在本轮循环担任簇头.

$ \begin{array}{l} T\left( n \right) = \\ \left\{ \begin{array}{l} \frac{P}{{1 - P*\left( {r{\rm{mod}}\frac{1}{P}{\rm{ }}} \right)}}{\rm{ }}, {\rm{}}\;\;\;{\rm{if}}\;n \in G;\\ 0, \;\;\;\;\;\;\;{\rm{otherwise}}. \end{array} \right. \end{array} $

(1)

式中，n是传感器节点的标识，P是网络中节点被选为簇头的概率，r是系统当前循环进行的轮数，G是最后1/p轮中依旧未曾担任过簇头的节点集.随后，本轮循环被选为簇头的节点向外发送广播消息，其余节点根据收到的信号强度决定要加入的簇并向该簇头发送加入请求消息，簇头接收到请求后将该节点加入自己的簇并为其设定一个TDMA时隙用于数据通信.簇形成以后便进入簇稳定阶段，此后，簇成员节点按约定的时隙将采集到的数据发送给簇头，簇头则将收集到的簇内成员节点数据进行融合处理后转发给基站.由于簇的建立阶段开销较大，为节省能量，数据传输阶段的持续时间相对较长.

与传统的路由协议相比，LEACH协议有更好的能量利用效率.然而，在选举簇头的过程中，没有考虑节点自身的情况及节点所处的环境，可能产生不合理的分簇，影响网络的能量利用效率.

2.2 E-CARGO模型

角色作为面向Agent软件开发方法中的重要抽象概念，角色与Agent技术是解决复杂协同系统的有效方法^[10-12].基于角色的协同RBC (Role-Based Collaboration)是一套研究角色及其之间复杂关系的方法、理论及技术.RBC将角色作为个体行为在群组环境中的抽象描述，能够更简单、自然地描述群组协同关系，由于角色之间的关系比较稳定且长期存在，使得基于角色的群组协同关系具有很好的适用性和有效性.

朱海滨探讨了角色协同技术，提出了E-CARGO模型，并将该协同模型应用在多Agent系统及软件开等领域^[13-15].

定义1   E-CARGO模型Σ为九元组，$ \mathit{\Sigma} :: = < C, {\rm{ }}O{\rm{ }}, {\rm{ }}M{\rm{ }}, {\rm{ }}R{\rm{ }}, {\rm{ }}E{\rm{ }}, {\rm{ }}G{\rm{ }}, {\rm{ }}A{\rm{ }}, {\rm{ }}{s_0}, {\rm{ }}H > $.其中，C (Class)是类集合；O (Object)是对象集合；M (Message)是消息集合；R (Role)是角色集合；E (Environment)是环境集合；G (Group)是群组集合；A (Agent)是代理集合；s₀是初始状态集合；H是用户集合.

在九元组中，A, R, G及其关系是E-CARGO模型中的重要组件.引入角色思想，使agent之间通过扮演角色来实现交互.角色自身内部(R - R)的关系(继承、约束和冲突等)和角色与代理间(R - A)的关系(指派、提升和转移等)能方便地描述复杂协同系统内部关系的特征.基于此，将E-CARGO模型用于分簇型无线传感器网络系统建模.

3 基于E-CARGO的LEACH协议建模 3.1 问题描述

本文研究的WSN存在如下假设^[16]：

(1) WSN由大量位置相对固定或变化缓慢的传感器节点组成，节点在区域内随机分布，只有1个固定的Sink节点(汇聚节点)，且Sink节点不受能量约束；

(2) 传感器节点使用电池供电，存在能量约束，采用LEACH协议中的能量消耗模型;

(3) 传感器节点功率可控，能自主实现休眠/唤醒操作，支持不同MAC协议;

(4) 传感器节点安装全相天线，能够同步、周期性地感知环境，能进行数据融合操作，可通过多跳通信发送数据给Sink节点.

传感器节点作为独立的、符合设计目标的自治行为的实体，既是信息的采集和发出者，也能充当信息的路由者，节点是具有特定语义的agent^[17].

定义2    agent(代理)，$A:: = < {\rm{id, }}{R_o}{\rm{ }}, {\rm{ }}{R_c}, {\rm{ }}{N_g} > $，其中id是代理的标识；R_o是曾经扮演过的角色集；R_c是当前扮演的角色集；N_g是当前代理所属的群组.

相对于分簇拓扑结构的WSN，代理可以是具体的传感器节点或汇聚节点. R_o表示曾经扮演过的角色集，如曾经扮演过簇成员、簇头等；R_c表示当前扮演的角色集，如传感器节点i目前的角色是簇头和网关.

WSN作为一种分布式自组织网络，通常采用随机方式部署，节点在部署前的地理位置及其邻居节点都是未知的，提前为节点初始化配置是不可行的.而且节点的运行状态及参数也随时间动态变化，这就要求网络中的传感器节点能根据特定的应用环境进行自动配置，以完成监测任务.WSN网络的自组织配置过程，从RBC的角度，可理解为网络中的节点分配相应的角色，扮演不同角色的节点根据其自身的状态信息执行指定的应用程序，各节点通过扮演角色协同完成指定的目标任务.基于角色的分簇型WSN框架，如图 1所示.

假定WSN由n个传感器组成，A = { a₁, a₂, …, a_n }是传感器节点agent的集合；R = { r₁, r₂, …, r_m }是节点的角色集合.由于WSN能量受限，其配置问题，即保证网络满足指定应用要求的前提下，通过合理的角色分配，使得传感器节点能耗最小化，网络生命周期最大化.

3.2 角色定义及其关系

在WSN初始化之前，需要对角色及角色之间的关系给出定义.

定义3    role(角色)，$ R:: = < {\rm{id, }}I, {A_c}{\rm{ }}, {\rm{ }}{A_p} > $，其中id是角色的标识；I是一组消息的集合，定义为$ I{\rm{ :: = < }}{M_{\rm{ in}}}, {\rm{ }}{M_{\rm{ out}}} > , {M_{in}}$表示输入给相关代理的一组消息，M_out表示输出给相关角色的一组消息，M_in, M_out $ \subset $ M；A_c是该角色当前拥有的代理集；A_p是可以指派该角色的代理集合.

相对于分簇拓扑结构的WSN，网络中的角色主要分为3类：簇头(Cluster Head)、网关(Gateway)和簇成员(Cluster Member)，角色的集合记为R = {r_ch, r_gw, r_cm}.簇成员角色采集感知信息并发送给簇头角色；簇头角色不但能采集感知信息，还负责接收簇成员发送的数据，且具备数据融合能力；网关角色负责转发簇头角色发送给基站的数据.

角色之间存在合作关系，具体体现为提升关系、报告关系和请求关系.

定义4    promotion relations(提升关系)，$ \Delta :: = < {\rm{ }}{r_i}, {\rm{ }}{r_j} > $，对$ \forall {r_i}, {\rm{ }}{r_j} \in R$，设r_i通过竞争提升为r_j，则r_i与r_j之间为提升关系.

相对于分簇拓扑结构的WSN，$ < {r_{{\rm{cm}}}}, {\rm{ }}{r_{{\rm{ch}}}} > $表示簇成员角色提升为簇头角色，它们之间是一种提升关系.

定义5   report-to relations(报告关系)，$\diamondsuit :: = < {\rm{ }}{r_i}, {\rm{ }}{r_j} > $.其中r_i表示管理者角色，r_j表示被管理者角色，即N_i < N_j，其中N_i表示i的等级.

相对于分簇拓扑结构的WSN，r_cm向r_ch报告采集的数据信息、位置信息、剩余电量等，它们之间是一种报告关系.

定义6    request relations(请求关系)，$\mathit{\boldsymbol{ \boldsymbol{\varPsi} }}:: = < {\rm{ }}{r_i}, {\rm{ }}{r_j} > $，对$\forall {r_i}, {\rm{ }}{r_j} \in R $，设角色r_i请求角色r_j提供服务且角色r_j为角色r_i提供服务，即 < r_i, r_j> ∈Ψ iff $ \forall {r_i};{r_j} \in R$ $ \left( {{r_i};{M_{\rm{out}}} \subseteq {r_j};{M_{{\rm{in}}}}} \right)$，则r_i与r_j之间为请求关系.

相对于分簇拓扑结构的WSN，r_ch采用多跳与基站通信时，r_ch请求r_gw转发数据信息，r_gw将收到的来自r_ch数据信息按要求转发，它们之间是一种请求关系.

定理1   设a_1, a₂为网络中能单跳通信的两个传感器节点agent且它们之间的距离小于网络设定的节点感知半径，则$ \forall {r_i}, {r_j} \in R$有：(1)如果r₁为r_cm，r₂为r_ch，且r₁、r₂属于同一个簇g₁，则$ < {r_1}, {r_2} > \in \Delta $且$ < {r_1}, {r_2} > \in \diamondsuit $；(2)如果r₁为r_ch，r₂为r_gw，则$ < {r_1}, {r_2} > \in \mathit{\boldsymbol{ \boldsymbol{\varPsi} }}$；(3) a₁, a₂之间存在竞争关系.

证明    (1)、(2)由定义4、5，易知；(3)由a₁, a₂在同一区域且能相互单跳通信，在成簇阶段，为均衡网络能量，传感器节点agent是否扮演簇头角色由其自身状态及邻居状态共同决定，在簇头角色指派时节点a₁与a₂之间相互制约，即它们之间存在竞争关系.

3.3 角色分配

角色分配，即根据节点agent的状态信息(如剩余电量、邻居个数)采用相应的角色分配算法对节点agent进行角色指派.

定义7   赋值指派μ : R→ A.令μ为从R到A上的一个赋值指派，形如μ : R → A，其为R与A的笛卡尔积$R \times A{\rm{ }} = {\rm{ }}\{ < {r_{i}}, {\rm{ }}{a_j} > {\rm{ }}|{\rm{ }}{r_i} \in R \wedge {a_j} \in A\} $的一个子集.

在分簇拓扑的WSN中，扮演簇头角色的电量开销相对较大，为避免能量较低的节点继续担任簇头角色导致其电量耗尽而失效，在簇头角色指派时，应当优先考虑剩余能量较多的节点agent.为使角色分配更合理，通过定义约束，对节点agent实行约束指派.

定义8    Constraint(约束)，简称C.令C为μ上的一个约束，其一阶语言的定义形如：$C:: = {r_i}|{r_j}{\rm{| < }}{r_i}, {a_j}{\rm{ > |}}\neg C|{\rm{ }}CC|C \circ C|\forall {r_i}.C|\exists {r_i}.C|\forall {a_j}.C|\exists {a_j}.C $.其中i, j ∈ N，r_i ∈ R，a_j∈ A，$ \circ $表示集合论与布尔运算符，如∧, ∨, $ \neg $等；·表示算术与比较运算符，如+, ×, ≤等.

定义9   约束集Cons.令Cons为μ上的约束集，Cons = { C₁, C₂, C₃, … }，其中C_i(i = 1, 2, …)为满足定义8的约束.

定义10   约束指派，定义为μ_Cons : R × A = { < r_i, a_j > | r_i ∈ R ∧a_j ∈ A∧ C₁, C₂, C₃ …}是可满足的.

根据定义8~10，复杂约束是由一组具有一阶逻辑性质的子句构成.

定义11    group(群组)，$ G:: = < {\rm{id, }}e, {R_g}, {\rm{ }}{A_{g}}, {\rm{ }}J > $，其中id是群组的标识；e是群组所在的环境；R_g是群组中的角色集合；A_g是被指派的代理集合；J是由代理和角色构成的二元组，即$J = \left\{ { < {a_i}, {\rm{ }}{r_j} > |{a_i} \in {A_g} \wedge {r_j} \in {R_g} \wedge {a_i}, {r_j} > \in {\mu _{{\rm{Cons}}}}} \right\} $.

定理2   指派原则.设r₁, r₂, r₃为R中的角色，如果r₁为簇成员、r₂为簇头、r₃为网关，且WSN系统是工作的，则：(1) $\exists {a_1} \in A, {a_1} $扮演r₁；(2) $\exists {a_2} \in A, {a_2} $扮演r₂；(3) $\exists {a_3} \in A, {a_3} $扮演r₃.

证明  在大规模分簇型WSN系统中，网络配置采用自组织方式，有r₂概率大于0小于1.当网络中节点数n无限大时，则存在节点a₁扮演r₁且存在节点a₂扮演r₂；因是大规模自组织网络，r₂不能与基站单跳通信，又因WSN系统是正常工作的，则至少存在一个节点a₃扮演网关角色.

3.4 角色评估

角色评估，即对分配结果进行评估，以确定是否满足问题要求.当评估结果不满足约束条件时，重新进行角色指派或角色转移.

定理3   重指派原则：$ \forall {r_1} \in R{\rm{ }}, {\rm{ }}{g_1} \in G, {a_i}, {\rm{ }}{a_j}, {\rm{ }}{a_k} \in A$，设r₁为群组g₁中的成员，如果r₁提升为簇头，满足：(1)转移前：$ < {r_1}, {\rm{ }}{a_i} > \in {g_1}.J{\rm{ }}, {\rm{ }} < {\rm{ }}{r_1}, {\rm{ }}{a_i} > \in {\mu _{{\rm{Cons}}}}, \forall j{\rm{ }}, {\rm{ }}i \ne j{\rm{ }}, {\rm{ }} < {\rm{ }}{r_1}, {\rm{ }}{a_j} > \in {\mu _{{\rm{Cons}}}}$；(2)转移后：$ < {r_1}, {\rm{ }}{a_j} > \in {g_1}.J{\rm{ }}, < {\rm{ }}{r_1}, {\rm{ }}{a_j} > \in {\mu _{{\rm{Cons}}}}, \forall k{\rm{ }}, {\rm{ }}k \ne j, < {\rm{ }}{r_1}, {\rm{ }}{a_k} > \in {\mu _{{\rm{Cons}}}}$.

证明  略.

在分簇型WSN系统中，每个簇内只有一个簇头角色，为保证簇正常运行，当簇中扮演簇头角色的节点agent不能继续胜任此角色时，需提升簇内一成员角色担任簇头角色.为保证簇内能耗均衡，应让满足约束最优的节点agent的角色由簇成员角色转为簇头角色.

3.5 基于E-CARGO的LEACH协议模型

引入约束集，用带约束的E-CARGO对LEACH协议建模，如图 2所示.

在基于E-CARGO的改进LEACH协议模型中，每个循环周期(共1/p轮)开始时，首先考虑约束条件，满足约束的节点agent形成候选集，随后使用LEACH算法为网络中的节点agent指派角色.扮演簇头角色的节点agent广播Cluster-Head消息；簇成员角色根据收到簇头广播消息的强弱，选择与距离自己最近的簇头角色协商形成簇结构.在稳定阶段，簇结构内部的数据通信为单跳方式，簇头角色负责数据融合，簇头角色与基站通信采用单跳与多跳相结合.改进LEACH协议的工作流程如图 3所示.

因角色之间的关系不依赖具体的群组环境，将角色思想引入无线传感器网络，简化了WSN系统的设计与编程实现.引入约束机制，使节点约束独立于LEACH算法，进一步增强了LEACH协议的灵活性和可扩展性.

4 仿真实验与分析 4.1 实验设置

本实验环境使用Win7系统，Intel Core I5 CPU，RAM 4G，采用Matlab R2012a仿真平台，同文献[17]的无线通信模型，传感器节点agent传送k bit数据消耗的能量按式(2)计算：

$ {E_{{\rm{Tx}}}}\left( {k, d} \right) = \left\{ \begin{array}{l} k{E_{{\rm{elec}}}} + k{\varepsilon _{{\rm{fs}}}}{d^2}, {\rm{ }}d < {d_1};\\ k{E_{{\rm{elec}}}} + k{\varepsilon _{{\rm{mp}}}}{d^4}, {\rm{ }}d \ge {d_1}. \end{array} \right. $

(2)

式中，E_elec表示发射电路损耗的能量；$ {d_1} = {\rm{ }}\sqrt {{\varepsilon _{{\rm{fs}}}}/{\varepsilon _{{\rm{mp}}}}} $；当传输距离小于d₁时，功率放大损耗为ε_fs；当传输距离大于等于d₁时，功率放大损耗为ε_mp.

传感器节点agent接收k bit数据消耗的能量

$ {E_{{\rm{Rx}}}}\left( k \right) = k{E_{{\rm{elec}}}}. $

(3)

实验场景设在200 m×200 m的平面区域内，随机部署200个传感器节点，基站坐标为x =100, y =150.仿真参数如表 1所示.

本文考虑的约束包括节点的能量和分布位置，其中，节点的分布位置指节点的分布密度和到基站的距离.

(1) 节点能量约束

$ {C_1}\left( i \right) = \frac{{{E_c}\left( i \right)}}{{{E_0}\left( i \right)}}{\rm{ }}. $

(4)

其中，E_c是节点i当前的剩余能量，E₀是节点i的初始能量.

(2) 节点分布密度约束

$ {C_2}\left( i \right) = {\rm{max}}\left\{ {{\rm{ }}\frac{{{N_b}\left( i \right)}}{{\left( {1/p} \right) - 1}}{\rm{ }}, 1} \right\}. $

(5)

其中，N_b(i)表示节点i指定感知范围内邻居节点的个数，(1/ p)-1是WSN中所有簇内的邻居节点平均数.

(3) 节点到基站的距离约束

$ {C_3}\left( i \right) = \frac{{{d_0} - d\left( i \right)}}{{{d_0}}}. $

(6)

其中，d₀为网络部署区域的最大直线距离，d(i)表示节点i到基站的距离，采用欧氏距离公式计算.

综合考虑上述约束，得约束集Cons (i)：

$ {\rm{Cons}}\left( i \right) = {C_1}\left( i \right) + {C_2}\left( i \right) \times {C_3}\left( i \right). $

(7)

本文用式(7)计算Cons (i)的值，用以表示节点a_i竞争簇头角色的能力，值越大表示竞争力越强.每轮循环结束时，由簇头角色统计本簇内所有节点的Cons(i)值，排序后，发送消息通知Cons(i)值较大的一半节点加入候选集.在此约定，只有候选集中的节点能在下一轮中竞争簇头角色.然后，采用LEACH算法为候选集中的传感器节点agent进行簇头角色分配.由于上述候选集中节点约占网络节点总数的一半，因此，在采用公式(1)计算阈值时应增大式中的概率p至原来的2倍.选定1/2 p为一个候选周期，当r mod (1/2 p)等于零时，网络中所有正在扮演簇头角色的节点agent计算收到的Cons(i)值，并向Cons(i)值较大的一半节点agent发送候选消息，形成候选集，随后进入下一轮循环.网络中簇头角色与基站通信使用多跳方式，网关角色负责转发，路由路径形成采用最小生成树算法^[18].

4.2 结果分析

图 4是LEACH协议和本文方法(改进LEACH协议)网络中存活节点个数随系统运行轮数变化的曲线图.当节点电量小于等于0时，认为其死亡.由图 4可知，LEACH协议在第472轮时出现首个死亡节点，而改进LEACH协议发生在第729轮，延后了54.4%；WSN中一半节点死亡时，LEACH协议运行了695轮，改进LEACH协议则运行了835轮，延后20.1%；LEACH协议与改进LEACH协议所有节点都死亡的时间分别为第866轮和第905轮.由于本文方法通过能量和位置约束，避免未满足上述约束的节点agent竞选簇头，使得竞争扮演簇头角色的节点为剩余能量相对较多、位置相对较优的节点，因而延长了网络的生命周期.

图 5是LEACH协议和改进LEACH协议的网络总剩余能量随系统运行轮次的曲线图.从图 5可知，网络总剩余能量为80%时，LEACH协议和改进LEACH协议的运行轮数分别为第98轮和第136轮；当WSN总剩余能量为50%时，LEACH协议运行到了第250轮，改进LEACH协议则运行到第330轮.开始时两种协议的能耗相差不大，但随着网络轮次的进行，剩余能量约束和位置约束开始发挥作用，避免了电量相对较低、位置相对较差的节点继续竞争扮演簇头角色而致使其电量迅速耗尽而死亡的情况，因而有效均衡了网络的能耗.

5 结语

为了解决LEACH协议中簇头选取不合理所导致的节点能耗不均衡问题，本文在分析LEACH协议的基础上提出了用一种基于角色协同的模型，即E-CARGO模型，为分簇型无线传感器网络建模.通过将节点的剩余能量、分布位置等定义为约束，使得约束独立于LEACH算法，实现了对LEACH协议成簇机制的改进.分析表明，本文方法提高了LEACH协议的可扩展性及灵活性.为验证该模型的可行性，本文在成簇阶段，综合考虑了节点剩余能量和位置约束，结合LEACH算法进行簇头角色指派，避免了剩余能量较低、分布位置较差的节点扮演簇头角色，优化了网络成簇结构；在稳定阶段，使用多跳通信，网关角色负责簇头角色与基站数据通信的转发，采用最小生成树算法形成簇头角色与基站的通信路径.仿真实验表明，改进后协议能有效均衡传感器节点负载，延长整个网络的生存周期.