自组织网络区域覆盖协作控制算法

刘大鹍，陈桂芬，王义君

(1.长春理工大学 电子信息工程学院，吉林 长春 130022；2.中国北方车辆研究所 网络与信息中心，北京 100072)

0 引言

自组织网络的发展核心是在异构协作基础上为应用提供最优化服务，即面向不同应用实现差异化的服务功能共享。功能需求个性化决定了应用场景的多变性，应用场景的多变性决定了网络协议、硬件技术、软件技术的不同，因此自组织网络的研究内容是面向应用场景、面向功能需求的。从目前的研究情况可知，自组织网络的关键技术包括射频识别(RFID)技术、无线传感器网络(WSNs)技术、智能嵌入(EI)技术、纳米技术、信息处理技术、自组织管理技术以及安全技术等[1-2]。但是对于绝大多数应用场景，如果能够通信的网络节点不能有效覆盖信息区域，则上述关键技术的相关研究内容都将变得没有意义。因此，自组织网络区域覆盖的有效性研究是未来军事及民用领域能够实现广泛应用的基础内容，但是对于该方面内容的具体研究并不多见。

对于区域覆盖技术的研究，文献[3]提出一种针对移动自组织网络的能量有效区域覆盖机制。通过一个网络区域覆盖的临时备份节点，利用三角测量技术减少通信消耗来增强能源的使用效率。因此，能够在均衡电池能源使用最小化的同时，实现最大程度地节点覆盖连通，进而保证网络的鲁棒性并延长网络的生命周期。文献[4]提出一种基于网格划分的无线传感器网络多重覆盖算法，包括冗余节点判断和节点调度两部分。该算法将节点覆盖区域划分为多个网格，通过判断各个网格是否满足覆盖要求，进而判断节点是否冗余；在调度过程中能够克服边界效应的影响，同时通过冗余节点能量比较，避免休眠冲突和覆盖盲区的产生。文献[5]依据区分与划分相结合的可拒绝模式识别思路，提出高维空间海量训练样本情况下基于结构风险最小化决策的自组织多区域覆盖可拒绝近邻分类算法。该算法利用数据分类实现覆盖应用，具有一定的实践价值。文献[6]面向物联网应用分析了覆盖网络节点布置问题，主要利用局部搜索算法解决时间复杂度，这种算法很难均衡地反映覆盖控制的综合指标。文献[7]提出了无线传感器网络目标跟踪应用场景下的边界节点选择算法，该方法主要针对目标跟踪，具有一定的局限性。

本文在已有研究基础上提出基于三角剖分的自组织网络元胞遗传区域覆盖控制(CRCCTS)算法。该算法首先在三角剖分基础上完成网络节点的区域划分；其次根据区域划分后信号频谱的不同确定集群范围；最后基于元胞遗传算法解决自组织网络节点的功率控制。仿真结果表明，该算法在覆盖效率、能量消耗以及平均端到端传输可靠性三方面取得了一定的改进。

1 模型假设

对于自组织网络而言，必须综合考虑网络环境的特点，按照某种原则合理部署网络节点，保证网络连通覆盖前提下完成与终端用户的通信，而通信传输的网络节点应尽可能少，从而保证网络能耗尽可能低。自组织网络特点如下：

1)覆盖区域。自组织网络的目的是协作通信，从网络覆盖范围考虑，最终目标是实现整个作战区域的全方位覆盖。具体到某个网络，其覆盖区域至少应该是城域网或广域网。

2)网络带宽。自组织网络包含千变万化的异构网络，异构网络带宽存在较大差异，因此在不考虑信号频谱情况下，对网络进行覆盖算法研究将变得没有意义。

3)功率控制。自组织网络节点分属于不同异构网络，对于发射功率的要求也不尽相同。节点选择合适的发射功率可以影响其无线通信信号的覆盖范围，进而可以选择性地调整整个网络拓扑结构。相对于单一网络节点，自组织网络节点对于能量消耗的要求有所降低，因此自组织网络功率控制的主要目的是保证网络连通度和覆盖度前提下增加网络的容量，降低通信干扰[8]。

通过以上分析可知，自组织网络覆盖控制的特点主要体现在连通和通信两方面。因此本文对自组织网络区域覆盖算法所应用的数学模型作如下定义。

1.1 连通模型

由于覆盖模型需要表现出节点发送信号在网络中的传播能力，需要用连通度来反映覆盖能力。连通数学模型是基于某种特定的网络拓扑结构及节点分布状态，可以用(1)式表示覆盖连通模型，

(1)

式中：S为网络节点连通度；N为节点数；Si为第i个节点连通度。

1.2 通信模型

自组织网络中异构网络结构不同，对于传输对象的信号带宽也不尽相同，每个节点必须能够感知信号的频带宽度，用以完成对网络的选择和信号的传输。在实际应用中，当被监测区域中的监测对象不在节点通信范围内时，节点不能感知到监测对象。因此此时还需要考虑发射功率对于接收节点的影响。

根据电磁波传播理论，当其在自由空间中传播时，如果发射端与接收端在视距范围内，则可用自由空间传播模型预测接收信号的强度。设Ps为发射端的信源发射功率，r为收发端距离，则收发节点之间的信号功率关系为

(2)

式中：Pr为信宿接收功率；λ为载波波长；σ为信道衰落系数；As、Ar分别为信源天线和信宿天线的增益。

1.3 网络模型

本网络模型基于元胞思想[9]。

1.3.1 元胞空间及状态集定义

定义1C={c1，c2，…，cN}为网络节点集合，C中任意源节点与目的节点间的所有通信路径构成链路元胞空间L，L={Lk=(c1，…，cz，…，cj，…，cN)|cz，cj∈C，cz≠cj，z、j=1，2，…，N}。其中：Lk为两节点第k条链路的元胞空间，k∈Z，Z表示整数集。

定义2S={So，Sw，Si}为元胞节点状态集，So表示工作状态，Sw表示等待状态，Si表示空闲状态。元胞节点共有中心元胞节点(CC)、邻居元胞节点(NC)2种类型，反映3种元胞状态。其中：CC为正在传输信息的工作节点，该节点始终处于工作状态，此时CC需要决定下一跳节点的选择；NC为CC在通信距离一跳范围内的邻居节点，NC的状态分为工作状态和空闲状态两种，CC可以根据通信链路关系选择邻居节点，实现下一跳信息传输。设Sl为元胞空间Lk在t时刻的链路状态集合，该集合由Lk、S和t决定，即集合U(Lk，S，t)∈Sl.

1.3.2 元胞节点间邻居关系确定

采用Von Neumann邻域确定元胞节点间的邻居关系，该关系定义在二维方格上，由中央单元及其4个相邻邻居及扩展邻居组成，如图1所示。图1中，Z为处于中央单元的中心元胞，M为4个相邻邻居元胞，E为扩展邻居元胞，x、y表示元胞坐标。该邻域关系由无重复的U(Lk，S，t)集合决定。同时，在此邻域关系基础上，元胞空间Lk的通信链路判定由下面公式决定：

X={Lk|d(Lk1-Lk2)≤v，Lk1，Lk2∈Lk}，

式中：X为链路判定集合；d(Lk1-Lk2)为相邻节点间不同通信路径的差别，Lk1、Lk2表示两节点间第k1和第k2条链路；v表示相差度，由链路能量、误包率和时间延迟决定。

图1 Von Neumann邻域关系Fig.1 Von Neumann neighborhood

1.3.3 网络模型进化及更新准则

步骤1网络初始化：C={c1，c2，…，cN}，S={So，Sw，Si}。

步骤2元胞节点状态S转换。

状态1：假设CC周围存在处于空闲状态的相邻NC，则CC通过一个空闲状态相邻NC转发数据分组到下一跳元胞；选择依据为节点能量，即选择邻居节点中剩余能量最多的作为转发节点；

状态2：如果CC周围没有相邻NC但存在扩展NC，则CC通过一个扩展NC转发数据分组到下一跳节点，选择依据为节点能量及链路状态；

状态3：如果CC有效范围内不存在有效元胞，此时该CC的所有邻居元胞均处在工作状态，则CC将数据分组存储到缓存中；当该CC接收到某一元胞发送的释放消息后，选择该元胞完成数据分组的下一跳节点。

步骤3链路元胞空间状态S转换。构建网络传输路径，通过下式比较链路的节点通信路径差别，选择相对最优的数据链路完成链路路径选择。

X={Lk|d(Lk1-Lk2)≤v，Lk1，Lk2∈Lk}.

步骤4更新链路，存储多径信息，完成U(Lk，S，t)∈Sl的链路更新。

2 覆盖协作控制算法

2.1 基于三角剖分的区域划分

为了提高网络节点的覆盖效率，必须对节点进行合理部署，即对自组织网络覆盖范围进行科学的区域划分，为基于信号频谱的集群确定选择出合适的扫频节点。因此协作控制算法的第一步是将覆盖区域进行物理划分，从而不仅可以降低拓扑控制的成本，还能通过最少的链路节点获取最大的路由效率，是下一步算法实现的基础。在确定覆盖区域所需扫频节点时，由于覆盖区域可能较为复杂，可以将其分为若干子块。每一块由扫频节点覆盖。为了完成每一块的分解，需要将区域内若干顶点通过对角线连接起来，即一段开线段。这种开线段必须完全落在分块区域内。通过一组极大的互不相交的对角线，即可将覆盖区域分解为多个三角形的集合，实现覆盖区域的三角剖分。本文以节点覆盖区域外部多边形顶点结构为基准，通过三角剖分形式将网络覆盖区域划分为若干子域。网络覆盖区域的外部多边形结构即区域W如图2所示。

图2 节点覆盖区域外部多边形结构Fig.2 Outside polygon structure of nodes coverage

2.1.1 构建单调多边形

将区域W划分为w个单调多边形，通过引入对角线来消除多边形不规则情况下引起的拐点，如图3所示。图3中，点p为1个拐点，与其连接的2条多边形的边分别位于点p的左右两侧，此时需构造1条以p为起点、向上连接到点b的对角线，对角线pb将原多边形分为两部分，此时p不再属于拐点，而属于划分后2个多边形的1个公共顶点。基于此，即可完成区域C的单调划分。由文献[10]可知，在空间复杂度O(w)的存储条件下，可在O(wlgw)的时间复杂度内将包含多个顶点的任何简单多边形分解为多个单调的子块多边形。

图3 通过引入对角线消除拐点Fig.3 Introducing diagonals to eliminate inflection point

2.1.2 单调多边形的三角剖分

完成对自组织网络外部多边形结构的单调划分后，按随机次序依次引入网络中的各节点，程序的执行需要维护并更新1个与当前点集对应的三角剖分。单调多边形三角剖分构造算法流程图如图4所示。

图4 三角剖分流程图Fig.4 Triangulation flow chart

综上所述，通过对覆盖区域的外部多边形结构进行单调划分和三角剖分，即可得到自组织网络节点外部多边形为10个顶点时在平面区域内划分的三角剖分拓扑结构图(见图5)。

图5 经过三角分解后的网络拓扑结构Fig.5 Network topology after triangular decomposition

2.2 基于信号频谱的集群确定

2.2.1 基于染色方案的扫频节点确定

网络拓扑形成后，需要为覆盖协作控制奠定基础。当三角剖分后的拓扑结构形成后，将三角形顶点处的节点组成1个子集。为了最大限度地在该子集中找到尽可能少的节点、完成区域覆盖任务，使用红、黄、绿3种颜色给子集中的所有节点进行染色。染色方案需要满足由任何边连接的2个节点所染的颜色不能相同。基于此，三角剖分后的多边形经过染色后，其中每个三角形都有且仅有1个红色、黄色和蓝色顶点。通过上述方法，当网络完成三角划分后，如果覆盖区域外部多边形结构存在h个顶点，则可以选择h个网络中三角形顶点处的节点完成整个网络区域的监测，如图6中圆形顶点所示。在拓扑结构确定的基础上，通过染色可以获取协作控制的中心节点，保证集群确定的实现。

图6 骨干传输节点选择示意图Fig.6 Schematic diagram of backbone node selection

2.2.2 基于信号频谱的集群确定

首先定义兴趣驱动的概念。所谓兴趣驱动，是将网络中同时具有如下特征的节点称为同类兴趣驱动节点：1)描述共同的需求网络行为；2)具有共同的性能指标参数；3)表达共同的附加功能请求。关于同类兴趣驱动节点，就需求网络行为而言，可以指能量消耗需求或时间同步精度需求；就性能指标参数而言，广义讲可以指传输信号的类型，如视频、图像或语音等，或者是允许多种类型信号同时传输对指标参数的要求；就附加功能请求而言，可以指是否需要与互联网或移动通信网络相连等。

当确定扫频节点后，扫频节点通过发射某种频率的信号发现具有共同兴趣驱动的自组织网络节点，将具有共同兴趣驱动的节点划分到统一的通信范围中，本文将满足该通信范围所代表的区域称为1个集群。基于频谱的共同兴趣驱动节点发现过程如图7所示。当扫频节点确定后，所有节点仍处于独立的分布状态，并没有形成以兴趣驱动为目标的集群，此时不同类型扫频节点开始以不同频率发射广播信号，寻找共同兴趣驱动的同类型节点，如图7(a)所示，广播信号的帧结构包括集群ID、时间戳、安全认证码和兴趣驱动优先级，其中时间戳位于集群ID之后。当扫频节点周围的普通节点接收到与其同频段的广播信号时确定兴趣类型，并向该扫频节点发送应答信号，等待扫频节点确认后加入属于该频段且同兴趣的集群中，如图7(b)所示。当共同兴趣驱动节点完成集群组合后，如图7(b)所示，在规定时间内自组织网络节点3并没有发现合适的集群，此时该节点主动成为扫频节点并开始以频率f广播信号，寻找共同兴趣集群。当有同类型节点收到此信号时，与节点3建立联系并告知该集群中的扫频节点，使节点3加入该集群中，如图7(c)所示。如果节点3在有效时间阈值中不能找到共同兴趣集群，则其以扫频节点身份存在于网络中。

图7 基于频谱的共同兴趣驱动节点发现过程Fig.7 Discovery process of common interests drive nodes based on spectrum

2.3 基于元胞遗传的功率控制

对于自组织网络，覆盖协作控制算法的关键一步是功率控制，以降低网络节点的相互干扰、提高自组织网络的覆盖效率。功率控制的基础是区域划分和集群确定，这三方面相互协作，可以实现区域的完全覆盖。覆盖控制方法需要遵循功率控制与睡眠调度相统一原则[11]。节点在没有事件驱动时设置通信模块为睡眠状态，在有事件驱动时结束睡眠并唤醒邻居节点，进而形成数据转发的拓扑结构。该原则使无线通信模块大部分时间处于休眠状态，传感器模块则处于工作状态。由于无线通信模块的能耗远大于传感器模块，节省了能量开销。该原则重点在于解决节点在睡眠状态和激活状态之间的切换，而且不能独立成为一种拓扑结构控制机制，需要与其他拓扑控制算法结合使用才更有效。因此，要建立能量高效的覆盖控制结构，必须在考虑通信能耗和空闲能耗的基础上建立功率控制机制。本文基于元胞遗传思想解决功率控制问题，算法运行流程图如图8所示。图8中，Ep为1条无线通信链路中端到端的总能量消耗，Eth为端到端通信所需要的最低能量消耗阈值，PERl为1条无线通信链路中端到端的总误包率，PERth为端到端通信所要求的最低误包率阈值，Tp为1条无线通信链路中端到端的传输总延时，Tth为端到端通信所要求的最短时间阈值，β为时间延迟的目标概率，P表示概率。

图8 功率控制算法流程图Fig.8 Flow chart of power control algorithm

控制方法具体步骤如下：

步骤1进行三角剖分，整个自组织网络完成区域划分及节点覆盖布置，形成初始节点分布集群。

步骤2建立基于元胞的节点集群网络模型。

步骤3节点集群网络模型通过能量测试完成性能指标适应度评估。设Nb为节点传输数据包的比特数，

Nb=Nh+Nc+Nd，

(3)

式中：Nh为报头的比特数；Nc为经过编码后的编码比特数；Nd为数据比特数。设1条无线通信链路上第n个节点传输Nb信息的能量消耗为E(n)，则

(4)

(5)

如果Ep≤Eth，则表示无线通信链路稳定，可以按照既定路由完成数据转发；如果Ep≥Eth，则转步骤4，开始集群的进化。

步骤4节点集群进化的一方面是误包率判断，(6)式给出了误包率进化的判断方法，

PERl=1-(1-PERe)(1-PERi)≤PERth，

(6)

式中：PERe为物理层经过编码差错控制的链路误包率；PERi为网络误包率。如果(6)式成立，则满足误包率进化要求。节点种群进化的另一方面是时间延迟判断，(7)式给出了时间延迟判断方法，

(7)

式中：Tq为链路中某节点信息申请及等待发送时间；Tc为信息转发执行时间；Ti为网络传输时间。如果Tp≤Tth的概率P(Tp≤Tth)≥β，则满足时间延迟进化要求；如果上述两条原则均满足，则替换节点数据转发种群，否则转步骤5.

步骤5设we、wp、wt分别为链路能量、误包率和时间延迟的权重，则有

we+wp+wt=1.

(8)

当步骤1～步骤3不能满足时，功率控制采用(9)式完成。节点能量、误包率和时延在与相应阈值作归一化比较后，与对应的权值完成加权运算，将三类参数求加权和，通过均衡3组参数权值最小值，选择相应的节点增大功率，而其他节点则处于睡眠状态，不加入拓扑结构中。

(9)

4 仿真实验

仿真实验中将自组织网络节点按发送信号频谱的不同分为3类，每类节点各取300个，通过在800 m×800 m区域内布置900个自组织网络节点来测试覆盖控制算法，其中具体仿真设置参数如表1所示。为了验证本文所提CRCCTS算法的有效性，将其与均衡速率区域覆盖算法(BRACA)[12]、最小节点强屏障的分区构造(PMNSB)算法[13]、覆盖配置协议(CCP)算法[14]和多跳Ad Hoc无线网络的节能技术(SPAN)算法[15]进行比较。其中，BRACA主要以实现网络生命周期的最大化为目的开展网络能量均匀及均衡覆盖方面的研究；PMNSB算法构建了强栅栏覆盖模型，提出分区强K-栅栏覆盖构建方法，旨在用最少的节点形成强栅栏；CCP算法将无关节点安排睡眠间隔，其余节点保持活动状态以提供连续服务；SPAN算法则侧重在保证网络连通度情况下，最大限度地降低网络节点的能量损耗。将5种算法同时在表1所示的仿真环境下进行实验，并从覆盖效率、能量消耗和平均端到端可靠性3个方面进行数据处理和分析。

4.1 覆盖效率

覆盖效率是综合衡量网络覆盖控制算法的评价指标，它既可以反映覆盖程度，也可以反映节点的冗余程度，同时还可以体现网络能量消耗状况。覆盖效率可定义为覆盖区域中所有节点的覆盖范围并集与所有节点覆盖范围和集的比值，即

表1 仿真参数Tab.1 Simulation parameters

(10)

式中：Ci为第i个节点的覆盖范围。

图9 覆盖效率比较Fig.9 Comparison of coverage efficiencies

根据(10)式，得到CRCCTS算法、BRACA、PMNSB算法、SPAN算法和CCP算法在覆盖效率方面的性能指标如图9所示。由于CRCCTS算法通过三角剖分划分覆盖区域并确定集群中心节点的位置，可实现最少节点覆盖最大区域，同时采用信号频谱确定集群集合，进而调整集群节点的功率控制范围。从图9中可见，随着节点数量的不断增加，CRCCTS算法覆盖效率比BRACA平均提高约3%，比PMNSB算法平均提高约5%，比SPAN算法平均提高约12%，比CCP算法平均提高约22%.

4.2 能量消耗

对于能量消耗，本文主要考虑自组织网络底层异构网络中能量受限的无线网络节点，如无线个域网中的传感器节点或移动无线网络终端等。因此，将(4)式进一步细化，可得每个节点完成一次信息传输所消耗的能量，如(11)式所示：

E=q(Ei+Es+ξrψ)+E0，

(11)

式中：q为节点收发数据次数；Ei为1次收发过程节点电路本身能量消耗；Es为网络协议能量消耗；ξ为电磁场扩散能量损失系数；ψ为扩散损失因子；E0为节点在空闲状态下的能量消耗。因为CRCCTS算法一方面采用最少的节点数量保证网络覆盖效率，另一方面基于元胞遗传完成节点功率控制，所以1次端到端信息传输参与通信节点数量较少，而且每个节点完成此次通信任务的平均信息交换次数较少，其能量消耗相对于其他4种算法具有一定的优势。5种算法的能量消耗性能指标比较如图10所示。从图10中可见，网络中节点数量较少时，CRCCTS算法能量消耗最低，CCP算法能量消耗最高，但5种算法相差不大；随着节点数量增多，5种算法表现出来的能量消耗差距明显，当网络中有900个节点时，CRCCTS算法约消耗能量18 J，BRACA约消耗能量20 J、PMNSB算法约消耗能量26 J，SPAN算法约消耗能量46 J，而CCP算法约消耗能量70 J.

图10 能量消耗比较Fig.10 Comparison of energy consumptions

4.3 平均端到端可靠性

网络可靠性与网络质量和性能具有密切关系，本文针对覆盖控制算法，将平均可靠性指标定义如下：假设网络中有n个节点，平均端到端链路为La，则平均端到端可靠性指标可定义为

(12)

式中：pi为2节点间第i条链路成功通信概率；δi为2节点间第i条链路容量权重系数，本文所采用的链路容量指标为数据传输速率和信道数量。同时，将5种算法与文献[16]中提出的路由算法相结合，对端到端可靠性进行仿真，仿真结果如图11所示。由于CRCCTS算法利用信号频率建立集群，不同集群可作为信息传输的载体，同时利用元胞遗传控制集群节点功率，实现端到端可靠覆盖传输。由图11可知，网络中节点数量不同的情况下，CRCCTS算法的平均端到端可靠度在87%～97%之间，BRACA和PMNSB算法的平均端到端可靠度约为70%～95%，SPAN算法和CCP算法的平均端到端可靠度约为60%～85%. 由此可见，CRCCTS算法能够保证信息的端到端可靠传输。

图11 平均端到端可靠性比较Fig.11 Comparison of average end-to-end reliabilities

5 结论

为了解决自组织网络区域覆盖有效性的问题，本文提出基于三角剖分的自组织网络元胞遗传区域覆盖控制思想。通过区域划分、集群确定以及功率控制实现自组织网络应用环境下的区域覆盖控制。该算法可以较好地满足自组织网络的特点以及覆盖效率、能量消耗和传输可靠性等方面的约束。仿真实验结果证明了CRCCTS区域覆盖控制算法的有效性。由于本文在超密集节点和节点具有移动特性的情况下，相关性能指标优势并不明显。后续研究将进一步解决上述关键问题，同时将拓扑控制技术和路由技术融入到本文提出的区域覆盖控制算法中，综合考虑提高自组织网络异构数据传输速率及可靠性等问题的有效方法。