一种基于广度优先生成树的无线传感器网络自保护算法

张文哲 李 蓥广东工业大学

一种基于广度优先生成树的无线传感器网络自保护算法

张文哲 李 蓥
广东工业大学

从无线传感器网络中选取部分节点作为保护节点，为网络提供保护称为无线传感器网络的自保护。前人已经证明自保护问题是 NP- 完全问题。提出一种基于广度优先生成树的自保护算法，可以高效地分布式地选择保护节点。我们首先为自保护问题建模，其次提出了分布式的标记过程，不同于前人工作的是，在保持较小保护节点集合的基础上，我们还保持了保护节点的连通性，使得紧急消息到网关的平均汇报跳数最少，这一特点使得本文算法更加合理可行，从而提高了区域监控应用中传感器网络性能。仿真实验证明，本文算法可行性和有效性。

无线传感器 自保护算法

1 无线传感器网络的自保护

1.1 传感器网络的辐射与暴露

在区域监控应用中，无线传感器网络通常被用来监测入侵区域的任何目标 Target，这些目标通常都是智能的，例如战场上的敌人、商店的小偷以及公共安全场所的恐怖分子等。目标不仅会发现布置的传感器节点绕道入侵，而且会敌意破坏这些节点使之服务失效 Denial of Service。由此可见，我们有必要隐藏无线传感器网络的节点，使其能够在敌对的环境下继续工作，增强传感器网络的鲁棒性。

传感器节点被目标发现，通常由于两种情形：一是节点体积形态庞大而被人看见；二是由于节点通信时形成的电磁场暴露。随着电子技术的高速发展和元器件微型化，有更多的微型传感器节点面世，如美国加州大学Berkeley 分校的 Smart-Dust 项目，正是致力于能够悬浮在空气中的传感器节点制造。此外，形态伪装同样可以减少被目标通过视觉发现的可能性。因此，节点的微型化并不是难点，电磁场暴露才是传感器节点被发现的主要原因。

针对电磁场暴露，我们重新考虑传感器节点的组成与结构，传感器节点上能够产生较大电磁场暴露的元器件，通常有两个重要的组成部分：感知单元和通信单元。传感器节点的感知方式有很多种，由于感知原理的不同，各种感知单元形成的电磁场强度各不相同。通常由于辐射强度与节点能耗成正比，节点在通信过程中的能耗是感知过程的十几倍，因此通信时的电磁场暴露是传感器节点暴露的关键因素。

一种简单而有效的减少节点暴露的方法是减少传感器网络的通信量，本文中称之为隐藏技术。这就为面向区域监控的传感器网络设计提出了新的辐射要求：在维持传感器网络正常功能的前提下，减少节点发送的消息数量，使更多的节点保持休眠，避免暴露。此外，休眠节点依然面临着危险，具有较强的脆弱性，容易遭受攻击。在区域监控应用中，隐藏技术不仅能够减少电磁暴露，使节点不被发现而免受破坏，增强了网络的可靠性；而且能使智能目标误闯被监控区域，大大增加了传感器网络监测目标的机率。

此外还需要保护传感器节点，实时监控节点的状态。一旦有节点被破坏，其保护节点即刻发送紧急消息 “SOS” 至网关汇报情况。这一技术称之为自保护（Self-protection），也即由传感器节点自己保护自己。自保护的实现是选择部分节点承担保护任务，实时监督其他节点的状态。一旦有节点被毁或者失效，网关能够收到紧急消息并采取进一步措施。由于电池供电，传感器节点常常由于电能耗尽而失效，可见自保护技术是传感器网络健康状态自我监视的好方法，在区域监控应用中同样具有重要的研究意义。

1.2 问题的提出

减少通信量可以降低传感器节点的电磁场暴露。根据传感器网络的辐射要求，把传感器节点分为两类：隐藏节点和保护节点。仅感知少通信的节点称为隐藏节点，而既感知又通信的节点成为保护节点，承担保护任务，监视隐藏节点的状态。

那么传感器网络中，选择哪些节点为隐藏节点，哪些节点又为保护节点呢？ 这是需要重点解决的问题。此外，在区域监控应用中，我们还发现隐藏节点的选择过程具有以下特点：

1） 布置在监控区域边缘的节点最容易暴露、被破坏，因此最需要被保护；

2） 隐藏节点的数量越多越好，但是所有隐藏节点都需要被保护。通常地，假设节点一跳可保护，即保护节点可以定期询问隐藏节点是否安好；

3） 保护节点必须连通至网关，而且向网关汇报的紧急消息平均跳数最少。

基于上述分析，我们提出的问题是，从所有节点集合V中，找出最小连通子集V*，使得任意节点要么属于V*，要么在V*节点的一跳范围内。如此所得的V*节点是保护节点集合，承担保护任务，实时监督其他节点的状态，不可以休眠；V -V*是被保护节点，可以休眠以减少电磁场暴露。

由此可见，传感器网络的隐藏问题可以归纳为这样的数学问题：求任意连通图的最小连通支配集（Minimum Connect-ed Dominating Set，MCDS）。关于最小连通支配集问题，有人已经证明是 NP完全问题，前人已有出色的研究工作如下。

1.3 研究现状

无线传感器网络的自保护问题已经有很多文献阐述了细致的工作。D。Wang在文献中首次提出了无线传感器网络的自保护（Self-protection）问题，并给出了正式的定义：一个无线传感器网络被p-自保护，当且仅当任何时刻任何传感器节点至少被p个活跃的节点监视到。文章证明了自保护问题是 NP完全问题，并给出了两种求解方法：集中式的pIA（Pre-Scheduled Independent Activation）和 分 布 式 的 NC（Neighbour-hoodCooperative self-protection）。在pIA 算法中，每个传感器节点需要预先设定一个计时器和概率 δ。当计时器过期时，节点以概率δ激活自己并重置计时器。计时器需要时间同步，概率δ则必须在布置传感器节点之前，根据传感器节点的密度而设定。由于绝大多数情况下传感器节点都是随机布置的，所以算法中这些设置和要求是不现实的。在 NC 算法中，节点无需密度信息即可协同地提供保护。但仅关注于自保护问题，不易于扩展到解决p-自保护问题的情形（p≥2），且没有深入研究节点静默和紧急消息的汇报要求。

修订了无线传感器网络的p-自保护（k-selfpro-tection）问题的定义，针对p-自保护问题，给出了一种局部最优的集中式算法，并对稠密网络可以生成多个保护集以轮流工作。集中式算法的基本思想是生成p个最大独立集 MIS，这些 MIS 提供网络的保护，每个 MIS 能够单独地保护网络节点，这p个 MIS即可提供p保护。文章将p-自保护问题归纳为最小连通支配集MCDS 问题，然后给出了一种分布式近似算法。分布式算法是集中式算法的扩展，传感器节点根据自己和邻居的信息决定自己的状态。同样，没有研究节点隐藏时的静默要求。针对提出的自保护问题求解方法给出了一个反例，证明的方法并不能适应于任何网络拓扑，在此基础上给出了一种分布式的自保护问题求解方法，并证明能够获得常数近似比。传感器网络中p-自保护问题，给出了一种局部最优的自保护集合生成算法，并能适应p＞=2 的情形，但该方法所得的集合仅仅是局部最优，未必是全局最优解。

2 自保护模型与网络建模

2.1 k-跳可保护与p-自保护

在无线传感器网络中，自保护指的是由传感器节点之间相互保护，怎样选择保护节点集合承担保护任务成为问题的关键。

保护措施可以通过多跳通信的方式来实现，所以可以通过通信的跳数（hops）来衡量保护的种类。如果认为传感器节点可以通过 k 跳通信的方式保护其他节点，则称之为 k-跳可保护。通常假设，传感器节点是 1-跳可保护的，即传感器节点可以通过 1 跳通信方式监视邻居的状态是否完好。

此外，自保护问题还可以通过保护节点的数量来衡量。p-自保护被定义为，在任何时刻，传感器节点至少被p个其他传感器节点所监视。如果p取值为1，则认为任何时刻传感器节点至少被1个其它节点所保护，也即1-自保护。在本文中，为了简化问题，更好地致力于求解传感器网络的隐藏方法，我们假设节点之间均是1-跳可保护的，而且算法目的只要求1-自保护。

此外，我们认为任何传感器节点都需要被保护，包括保护节点自身。但由于问题的特点是所有保护节点均连通至网关，则任何保护节点均可与其它保护节点 1-跳通信，也即任何保护节点均可以被保护。基于以上分析可见，传感器网络隐藏问题就可以简化为求解隐藏节点被 1-跳可保护与 1-自保护的问题。

2.2 网络建模

由于传感器网络离散分布的特性，节点的几何布置状况有多种布置方法，有如确定性布置和随机布置。确定性节点布置是传感器网络的简易布置方法，研究内容较少。本文中我们重点考虑随机布置的情况。假设节点的初始位置均一并相互独立地分布在监控区域内，且构成一个连通的无向图。为了更好地描述本文算法，首先给出如下有关基本概念。

定义1。设图G=（V，E），称G为简单连通无向图，当且仅当图G满足以下两个条件：①G为无自圈的、连通的无向图；②G中任意两个节点之间最多有一条边。定义2。若p、q 为图G=（V，E）中的任意两个节点，即p、q∈V，若存在G中的一条边连接节点p、q，则称节点p和节点 q 相邻 Neighbor。

定义3。图G的节点集SV为支配集，当且仅当节点集S 满足以下条件：/p∈V 则p∈S 或p为S中的某个节点的邻节点。S 中的节点称为支配点（Dominator），图G中不属于S 的节点称为被支配点（Dominatee）。

定义4。给定一个图G=（V，E），图G的节点集SV为满足如下条件的节点集合：由S导出的子图是连通图，且S是图G的一个支配集；则称S为连通支配集。若S为满足上述条件的最小节点集合，则称为最小连通支配集，记为 MCDS（G）。

定义5。若p为图G=（V，E）中的任意节点，即p∈V，称p在图G中的相邻节点的个数为p的度数，记为 D（p）。

定义6。若图G=（V，E）的生成子图T是一棵树，则称该树T为G的生成树（Spanning Tree）。

定义7。在图G的所有生成树中，从树根开始的广度优先遍历得到的生成树，称为G的广度优先生成树（Breadth-FirstSpanning Tree，BFS）。

定义 8。在图G=（V，E）的生成子图T是一棵广度优先生成树，一个节点子树的根节点称为孩子节点，含有相同孩子节点的节点称为父节点，具有相同父节点的节点称为兄弟节点。

3 基于BFS 的自保护算法

3.1 前提假设

随机布置的传感器网络构成一个简单无向图，为了研究问题的方便，我们如下假设：

1）网络拓扑是连通的。因为对于不连通的传感器网络来说，节点的感知信息不能够传回至网关，必然是失效的节点，更多的隐藏与保护措施也无意义；

2）每个节点标识了各自唯一的 ID，并通过 1 跳通信获知其邻居信息。每个节点维护自己的邻居节点信息表，包括节点ID 号、层次和状态信息；

3）网络中节点可以分层，用层数表示：0，1，2…，网关层数为 0，以此类推。

基于以上假设，我们就可以构建隐藏算法。

3.2 节点状态与分类

根据节点的工作模式，传感器节点分为两种类型：隐藏节点和保护节点。本文将节点状态相应地定义为被支配状态和支配状态。

保护节点处于支配状态，为其他节点提供保护；处于被支配状态的节点是隐藏节点，被支配节点保护。考虑到网络的初始状态，没有生成任何保护节点和隐藏节点，所有节点都处于初始状态，因此，传感器节点有三种状态，分别是初始状态、被支配状态和支配状态，处于以上状态的节点分别定义为初始节点primal、被支配节点 dominatee 和支配节点dominator。

3.3 消息设计

为了实现分布式隐藏节点选择算法，各节点需要沟通各自的状态并协商。为此，我们设计了专门的消息，用于通告各自的状态。这一消息在 1-跳范围内获知，即消息接受者只接收，不转发。如此设计，大大降低了消息广播的数量，而且有效防止了消息洪泛的现象。

我们设计了两种消息：1。分层消息 Layer Message用于通告自己的节点层次，消息结构定义为 Layer（n，i）：表示节点n 处于第 i 层；2。状态消息 State Message用于通告自己的节点状态，有三种：Dominating（n）：表示节点 n 处于支配状态，为支配节点；Dominated（n）：表示节点 n 处于已被支配状态，为已被支配节点；Undominated（n）：表示节点 n 处于未被支配状态，为未被支配节点。

3.4 节点状态转换策略

节点的状态有三种，处于不同状态节点也有三种，分别是初始节点、被支配节点、和支配节点。每当收到不同的消息，节点状态都要做出相应的变化。初始状态的节点收到任何消息都将转换为被支配状态，被支配状态的节点收到被支配请求后，转换为支配状态；当支配状态的节点得知被支配节点包围时，转换为被支配节点。

节点在状态转换的过程中，还需要把这一状态变化通告周围邻居。因此需要发送自己状态消息。对于处于不同状态的节点，每当收到不同的消息，都将自己标记为其他的状态，同时发送新的消息表明自己的状态。

3.5 基于 BFS 的 MCDS 问题求解

3.5.1 BFS 树构造阶段

由 Gateway 发起，通过 Flooding 或受限的 Flooding 算法构造一个以 Gateway 为根的生成树。经过该过程后，生成了一棵以 Gateway 为根的广度优先生成树 BFS，其中每个节点都将知道自己的父节点和孩子节点，并将节点 ID 信息记入自己的父子关系表。

3.5.2 层次生成阶段

从 Gateway 开始进行分层过程，其层次记为 0，并发送LM消息（Layer Message，其中包含节点 ID 和其层次）。收到LM的节点如果发现是由其父节点发出的，则该节点的层次记为父节点的层次加 1，然后发送自己的 LM 消息。同时，每个节点也记录其邻接点的层次信息，记入邻居信息表。直至所有节点完成分层。

3.5.3 节点标记阶段

初始化网络中所有节点（Gateway 除外）为初始状态。由Gateway 发起标记过程：首先标记自身为支配状态，其次发送DM 消息，也即 “发送支配 DM” ，（包含 ID 和其支配状态）。根据上文提出的节点-消息-动作策略，所有节点都将按照如下规则进行标记：

（a）如果处于初始状态的节点收到支配 DM，则标记自身为被支配状态，并广播已被支配 DM；

（b）如果处于初始状态的节点收到已被支配 DM，则标记自身为被支配状态，并广播未被支配 DM；

（c）如果处于初始状态的节点收到未被支配 DM，则标记自身为被支配状态，并广播未被支配 DM；

（d）如果处于被支配状态的节点收到所有孩子节点发送的未被支配 DM，则标记自身为支配状态，并广播支配 DM；（e）如果处于支配状态的节点收到其非孩子的所有邻居节点的支配DM，则标记自身为被支配状态，并广播已被支配DM。

4 实验结果与分析

为了切实评价本文提出的自保护算法，验证 BFS-basedMCDS算法的可行性，本文采用 NS2（Network Simulator）进行了仿真实验。

首先，保护节点承担保护其他节点的任务，不允许休眠，加快了对电能的消耗，容易导致电能耗尽而失效。因此保护节点越少 MCDS 算法越好，保护节点集的大小是评价隐藏算法的重要指标。为此我们在监控区域为 500×500 unit2 的二维矩形平面上，布置 N 个传感器节点，设置节点通信半径为110 unit，通过仿真实验考察保护节点数目所占的比例。图中 X 轴表示布置的节点数目，Y 轴表示通过 BFS-based MCDS 算法求得的保护节点比例 N R（Node R atio），其中 N R =支配节点数/网络节点总数。从图中可以看出，在不同节点密度下的BFS-based MCDS 算法的性能。

当节点总数少、节点密度小时，保护节点比例 N R 较大；随着布置节点数的增多，保护节点比例 N R 越来越低。也即BFS-based MCDS 算法在稠密的网络中能够选择相对较少的支配节点集，更具有优越性。这一现象可以这样解释：由于节点稀疏时，在通信半径不变的情况下网络连通度较小，很少有节点能够被其他节点保护而隐藏；当节点密度增大时网络中有更多地节点可以被保护而隐藏，导致保护节点比例 N R 下降。可以预测：在通信半径不变的情况下，随着节点密度增加，选择的支配节点数目将趋于饱和。

其次，在区域监控应用中，传感器网络监控的对象是智能目标。尽管采用了隐藏技术使得部分传感器节点保持静默状态，但静默节点依然有被发现并敌意破坏的可能性。一旦隐藏节点被破坏，其保护节点应当及时生成紧急消息并汇报网关，这是区域监控应用中重要的设计要求。本文提出的基于广度优先生成树算法就是在充分考虑这一点的基础上而设计的。

为了进一步衡量本文算法关于紧急消息 SOS 汇报的及时性，我们提出用平均汇报跳数作为指标，并做了如下仿真实验。在监控区域为500×500 unit2 的二维矩形平面上，布置 N个传感器节点，设置节点通信半径为110 unit，通过仿真实验考察紧急消息的平均汇报跳数，每个值都是重复独立试验节点随机布置50次后求得的平均值。在不同节点密度下的 BFS-based MCDS 算法的 ASH 性能。当节点总数少、节点密度比较小时，平均汇报跳数很小；随着布置节点数的增多，平均汇报跳数逐渐增大。但是增加的趋势越来越缓和，可以预见，当节点数目趋于饱和时，平均增加跳数 ASH也将趋于某一极大值。

5 小结

本文研究了传感器网络的自保护算法，即在保证网络正常监测功能的前提下，选择部分节点作为保护节点的方法。首先我们提出了问题— — —如何选择静默节点集合，使得所有静默节点都能被其他节点保护；其次，将问题归纳为基于广度优先生成树的最小连通支配集；针对这一数学问题，我们设计并实现了一种三阶段的节点标记方法，求得最小连通支配集。进一步推导了最小连通支配集就是我们所要选择保护节点集合，其余节点均是隐藏节点。仿真实验证实了本文方法的可行性和有效性。

由于电池供电的特点，传感器节点长时间执行保护容易导致电能耗尽而失效。一种延长传感器网络生命期的常见做法是休眠。那么在传感器网络自保护技术中，可以考虑生成多组MCDS 结果，实行节点轮换休眠，即是较好的选择。这些都是未来努力的方向。