An Improved Formation Method of Connected-Dominating Set in Ad Hoc Wireless Networks

为了与无线传感器网络(WSN)文献一致，网络图的顶点也称为节点，网络图中的边也称为链路。图G=(V, E)可以用来表示一个Ad hoc网络，其中，V代表无线移动节点集合，包含K个元素，E表示边集合(链路集)。如果E中存在边e={u, v}，表示u和v相互在对方通信范围内，此时图G就是无向图。若用图G=(V, E)表示连通的Ad hoc网络，则图G是连通图。用N_k表示节点k的邻居节点集(不包括节点k)，|N_k|表示节点的度，即节点k的邻居节点数。定义I为标准单位阵，l为所有元素为1的矢量(通过上下文确定维数)。ρ(X)表示矩阵X的谱半径，即绝对值最大的特征值。

邻接矩阵是图谱理论中的常用矩阵，用来表示无向图G。邻接矩阵A(K×K维)的元素为：

也可以对有向网络图定义加权邻接矩阵W=[w_kq]_K×K，其中w_kq表示从节点k到节点q的链路k, q的权值(w_kq≥0，∀k, q∈V)。在有向图中，加权邻接矩阵W一般是非对称的。假设网络中的分布式算法同步执行，即每迭代一次，各节点执行相应任务并和邻居节点分享结果。

在图论中，“中心性”往往指的是节点对于网络中其他节点的“影响”，如果一个节点有很多邻居节点则认为它影响大。节点k的度|N_k|只能测量节点的本地影响，而不能把整个网络的拓扑考虑进来。特征矢量中心性能解决此问题，如果一个节点连接越多的节点，同时与它连接节点所连接的节点越多(以此类推)则认为影响越大。网络的多个可能“中心节点”一般位于稠密连接簇的中心位置。若定义c_k为节点k的中心性，可知：

式中，α是归一化因子。这里每一个节点能够看到超出本地以外的范围，所以节点的中心性不仅仅依赖于它的邻居，而且也依赖于它邻居的邻居，依次类推。式(2)用邻接矩阵表示为：

式中，c是由所有c_k堆叠构成的K维矢量。这说明c必定是A的一个特征矢量，这也解释了“特征矢量中心性”名称。如果仅允许c中存在非负参数，那么根据Perron-Frobenius定理得到最大特征值α_K所对应的最大特征矢量是式(3)的唯一解。这也限定了c是一个非零尺度，而此尺度可用来对c进行归一化。把式(3)中的A用W替换，那么就可以由有向图生成c。

容易知道，无向图中矩阵A^N的k行q列的元素等于从节点k到节点q长度为N的路径数量。因此矢量A^Nl的第k个元素等于从节点k出发长度为N的总路径数。定义矢量：

式中，ϕ>α_K(否则求和式发散)。那么v(ϕ)的第k个元素等于从节点k出发的所有路径权数量。对于ρ(X) < 1，利用泰勒级数展开式${\left( {\mathit{\boldsymbol{I}}-\mathit{\boldsymbol{X}}} \right)^{-1}} = \sum\limits_{i = 0}^\infty {{\mathit{\boldsymbol{X}}^i}} $，可以将式(4)重新写为：

因此，

如果ϕ从上向下接近α_K(表示为$\phi \mathop \to \limits_ > {\alpha _K} $)，那么式(5)中$\left\| {\mathit{\boldsymbol{v}}\left( \phi \right)} \right\| \to \infty $，在此情况下，式(6)中的Al可以忽略。因此${\lim _{\phi \mathop \to \limits_ > {\alpha _K}}}\mathit{\boldsymbol{v}}\left( \phi \right) \propto \mathit{\boldsymbol{c}} $，$\propto $表示等效于一个非零尺度值，即特征矢量中心性相当于式(4)在有限情况下的值，其中路径越长惩罚因子越小。

邻接矩阵隐含了网络自身编码，网络允许与A的矩阵乘法以网内分布式形式实现。事实上，如果想要计算矩阵矢量乘积y=Ax，假设节点k存储着向量x的第k个元素(表示为x_k)，同时已经获得其邻居节点q的信息x_q，那么y的第k个元素可以在节点k计算得到：

所以，可以网内执行幂迭代(power iteration, PI)：

随机矢量x⁽⁰⁾作为初始值，根据矩阵理论，可知幂迭代收敛为矩阵A的最大特征矢量，即${\mathit{\boldsymbol{x}}^{\left( \infty \right)}} \propto \mathit{\boldsymbol{c}} $。然而，式(8)中x_(i)的范数按照ρ(A)>1或ρ(A) < 1会发散或为零。因此，应该补偿增长或收缩造成的影响。为此，采用一个补偿因子不断补偿增长/收缩率，即：

使得${r^{\left( i \right)}} \approx \frac{{\left\| {\mathit{\boldsymbol{A}}{\mathit{\boldsymbol{x}}^{\left( i \right)}}} \right\|}}{{\left\| {{\mathit{\boldsymbol{x}}^{\left( i \right)}}} \right\|}} = \frac{{\left\| {{{\mathit{\boldsymbol{\bar x}}}^{\left( {i + 1} \right)}}} \right\|}}{{\left\| {{\mathit{\boldsymbol{x}}^{\left( i \right)}}} \right\|}} $，有$\mathop {\lim }\limits_{i \to \infty } \frac{{{{\bar x}_k}^{\left( {i + 1} \right)}}}{{{x_k}^{\left( i \right)}}} = \rho \left( \mathit{\boldsymbol{A}} \right) = {\alpha _K} $。r⁽ⁱ⁾的估计可以采用与式(8)并行进行的另一个分布式计算方法。最终，可以发现基于式(6)的中心性矢量v(ϕ)能用相似的迭代过程计算，即：

这里同样需要利用与前面相似的技术，进行一个合适的增长/衰减比例的补偿。

支配集的生成过程只需要与邻居节点进行本地信息交换和固定数量迭代循环就可以通过分布式方式实现。由于要在此支配集上建立路由，将路径搜索功能在此支配集上实现，因此生成的支配集应该是连通的，并尽可能小，生成的支配集应包括任何最短路径的所有中间节点。

CDS算法包括标记过程、缩减规则一、缩减规则二，以及由于网络拓扑改变而采取的更新/重算方法。

给定连通图G=(V, E)每个顶点一个标记符号。对于顶点v∈V，m(v)代表它的标记符号，被标记为T(标记)或F(未被标记)，标记完成后，所有“标记”顶点构成一个连通支配集。假设所有顶点在初始状态都是未被标记的。N(v)={u|{v, u}∈E}表示顶点v的邻居开集。初始状态，顶点v的邻居集等于N(v)。

标记过程^[3]：

1) 对于每个顶点v∈V初始化标记为F。

2) 每个顶点v与其邻居节点交换邻居节点开集N(v)。

3) 如果每个顶点v存在两个未连通的邻居节点，则标记m(v)为T。

显然经过第2)步过程后，每个顶点都知道距离2步的邻居信息。假设V’是V中标记为T的顶点集，即V’={v|v∈V, m(v)=T}。缩减图G’是由V’构成的连通图G的子图，即G’=G[V’]。下面说明图G’是支配集且连通，定理证明过程参见文献[3]。

定理1 给定连通图G=(V, E)，且非完全连通。由标记过程形成的顶点子集V’构成图G的一个支配集。

定理2 缩减图G’=G[V’]是一个连通图。

定理3 任何两个节点间最短路径的中间节点，不存在非网关节点。

由于确定连通图的一个最小连通支配集是完全NP难(NP-complete)问题，标记过程获得的连通支配集通常不是最小的，因此要对连通支配集进行缩减。

首先，给图G’中每一个顶点v分配一个独立的id号，记为id(v)。N[v]=N(v)∪{v}表示顶点v对应于邻居开集N(v)的邻居闭集。下面两个规则用来缩减由标记过程形成的连通支配集。

规则1  假设两个顶点v和u属于图G’。如果在图G中N[v]⊆N[u]，且id(v) < id(u)，则将v的标记变为F，即G’变为G’-{v}。

上面规则表明，如果顶点v的邻居闭集被顶点u的邻居闭集覆盖，且id(v) < id(u)，则顶点v可以从G’中移除。当顶点v与顶点u具有相同的邻居闭集，则id号小的顶点可以从G’中移除。

规则2  假设顶点u和w是顶点v在图G’中的两个邻居节点。如果在图G中$N(v) \subseteq N(u) \cup N(w) $，且${\rm{id}}(v) = \min \{ {\rm{id}}(v), {\rm{id}}(u), {\rm{id}}(w)\} $，则将v的标记变为F，即G’-{v}。

这里id号的作用是避免由于将“同时违规”的所有顶点同时从G’移除，而破坏原来V’的支配集属性。

在Ad hoc网络中，每一个节点可以不受距离和速度限制而移动。同时，为了降低能耗，移动节点可以在任何时刻关机一段时间后再开机。因此Ad hoc网络的拓扑改变可归结为3种情况：移动节点开机，移动节点关机，移动节点运动。

移动节点v开机时，只有它的非网关邻居节点需要更新状态，因为当节点v加入时，任何网关邻居节点依然保持网关状态。当移动节点v关机时，只有它的网关邻居节点需要更新状态，因为当节点v删除时，任何非网关邻居节点依然保持原来状态。网络中仅个别节点移动引起网络拓扑改变时，一般对连通支配集采用本地更新方式进行网关更新。如果移动网络中有许多节点在移动，则对网络的连通支配集重新进行计算。更新措施和对于连通支配集上的路由方法详见文献[3]，在此不再赘述。

由于确定连通图的一个最小连通支配集是完全NP难问题，获得的连通支配集一般不是最小的，为了使连通支配集尽可能小，通过两个缩减进行改善，然而这样同样不能保证得到的支配集是最小的。本文在生成连通支配集时，借助“拓扑可知”理论，引入拓扑相关信息，进而为解决此完全NP难问题打开途径。通过引入拓扑相关信息后，对网络中不同位置的节点按照对网络“影响”大小进行排序并id编号，这样避免了CDS算法中节点id编号的随意性和无网络拓扑相关意义的缺点。由于CDS算法中id编号仅是为了避免将“同时违规”的所有顶点同时删除而设置，使问题呈现完全NP难，通过为id编号赋予网络拓扑相关特性后，问题便有了条件最优解。

与CDS算法相似，这里改进算法也包括标记过程、缩减规则1、缩减规则2和新建规则3，以及由于网络拓扑改变而采取的更新/重算方法。

标记过程与前面相同，最终得到连通图G的子图G’，即G’=G[V’]。

在改进缩减过程中，引入特征矢量中心性概念，通过节点v对图G’的不同“影响”对节点v赋予不同的特征矢量中心性值c_v，即按照式(9)进行网内计算得到${x^{(\infty )}} \propto {\bf{c}} $，节点v存储${x^{(\infty )}} $的第v个元素，可看成c_v的值。给图G’中的每一个顶点v分配一个独立的id号，记为id(v)，并使id(v)=c_v。按照前面的两个规则来缩减由标记过程形成的连通支配集G’，虽然这里采用的缩减规则与前面相同，但由于id号的定义不同，所体现的含义也不同。

规则1在改进过程的含义：如果顶点v的邻居闭集被顶点u的邻居闭集覆盖，且顶点v对图G’的“影响”小于顶点u对图G’的“影响”，则顶点v可以从G’中移除。当顶点v与顶点u具有相同的邻居闭集，则“影响”小的顶点可以从G’中移除。

规则2在改进过程的含义：规则2中id号避免将“同时违规”的所有顶点从G’中移除，而破坏原来V’的支配集属性。另外在移除时考虑了节点的拓扑相关特性，移除对图G’“影响”小的节点。

实际上规则1和规则2对于最大id编号的网关节点会产生漏判情况，即如果最大id编号的网关节点是冗余的，那么通过规则1、规则2是无法删减掉的。这里提出规则3来解决此问题。

规则3  假设图G’是规则1、规则2缩减后的连通支配集，顶点v属于图G’且id号最大。若图G’中顶点v的邻居开集$N'(v) = \{ {v_1}, {v_2}, \cdots, {v_m}\} $，邻居数$m \geqslant 1 $。若在图G中$N(v) \subseteq N({v_1}) \cup N({v_2}) \cup \cdots \cup $ $ N({v_m})$，则节点v的标记变为F，即G’变为G’-{v}。

下面说明通过改进算法得到的缩减支配集G’是最小的。

定理4 经标记过程后通过改进缩减过程(规则1、规则2和规则3)得到的缩减图是一个条件最优连通支配集，它是在规则1、规则2和规则3条件下生成的一个最小连通支配集。

证明：按照图谱理论中的特征矢量中心性定义，给标记过程形成的图G’中的每一个节点v对应分配一个独立的id号，且满足${\rm{id}}(v) = {c_v} $。由特征矢量中心性含义可知，如果节点v连接的节点越多，同时与它连接节点所连接的节点越多(以此类推)，则影响越大，节点v的特征矢量中心性值c_v也越大；另外可知具有相同特征矢量中心性值的节点在网络中具有相同的拓扑连接结构。

假设通过改进缩减过程(节点id编号按照对应特征矢量中心性值升序排列)生成改进缩减图G’₁；另外存在一个其他id编号(不按特征矢量中心性值大小顺序对应编号)情况下生成的缩减图G’₂，即图G经过标记过程后的图G’，经缩减过程分别得到的缩减图G’₁和G’₂，两图id编号不同，假设图G’₁中节点不少于图G’₂中的节点数，其中图G’₁是通过将“影响”较小的节点删减而得到的支配集。结合规则1、规则2、规则3可知G’₁在此规则下不存在冗余可缩减节点，因此可知图G’₂中各节点的“影响”至少要大于等于图G’₁中相应节点的“影响”，且没有冗余可缩减节点，故可知图G’₁和图G’₂均按照改进缩减过程生成，且图G’₁和图G’₂节点总数相同，因此假设条件“id编号规则不同”不成立。另外在id编号按照对应特征矢量中心性值升序排列的情况下，由规则1、规则2、规则3及特征矢量中心性定义可知，即使存在多个节点中心性值相等的情况，此时节点id编号不唯一，但这些节点在网络中的拓扑连接结构是相同的，这些节点在网络中的功能是等价的，另外根据规则1、规则2、规则3去除冗余可缩减节点，故而缩减过程得到的缩减连通支配集有可能节点不同，但功能相同且节点总数不变。因此该连通支配集是一个条件最优连通支配集。定理得证。

由定理4可知，改进的连通支配集生成算法得到的连通支配集节点数量不会多于CDS支配集生成方法得到的连通支配集的节点数量，此方法是条件最优的。

改进算法对于Ad hoc网络的拓扑改变同样可归结为3种情况：移动节点开机，移动节点关机，移动节点运动。这3种拓扑改变所进行的网关更新与前面所述过程相同，这里不再赘述。不过在各个过程中如果利用规则1、规则2和规则3进行删减网络中的网关节点时，需要按照特征矢量中心性进行id编号，即采用改进的缩减过程进行，进而保证得到的连通支配集是当前条件下节点数量最小的，即条件最优。另外，在重算连通支配集时，也需要重新计算标记过程形成的图G’中每一个节点的特征矢量中心性值。

对于最小连通支配集上的路由方法，与文献[3]方法相同，这里不再赘述。

在长、宽各为1的矩形区域中随机分布12个节点，假设各节点无差别，最大通信距离r为0.6，在通信距离r内节点间可相互通信，即在图G中由连接的边表示。易知网络对应的图G是无向图。如图 1、图 2所示，边用虚线表示。图 1中按照随机节点出现的先后次序编号，编号为1~12，按照CDS算法的标记过程可得图 1中12个节点均标记为支配集节点，用“*”表示；按照CDS算法规则1缩减后的支配集用“○”表示，即连通支配集{2, 8, 9, 10, 11, 12}；然后按照CDS算法规则2继续缩减后的支配集用“□”符表示，为{8, 9, 10, 11, 12}。

图 2与图 1网络拓扑相同，并按照式(9)算出的特征矢量中心性值进行标注，按数值由小到大对节点编号，编号为1~12，如图 2所示。图 2经改进算法标记过程得到的连通支配集也包含网络所有的12个节点，并用“*”表示；按照改进算法规则1缩减后的支配集用“○”表示，为{12}；按改进算法规则2和规则3继续缩减后的支配集用“□”表示，为{12}。可见，相同的网络拓扑，CDS算法得到由5个节点构成的连通支配集，而改进算法得到的连通支配集只有1个节点，故而验证了改进算法的优良特性。显然，此时如果在图 2所示的连通支配集上实现共识算法(consensus algorithms)^[11]，则由于图 2中节点12可以一步到达网络任何节点，故而一次计算就可以收敛，进而可将结果分享给其他邻居节点，避免其他节点产生的能耗和网络带宽占用，且收敛速度快。另外，若在连通支配集上进行路由，由图 1可知需5个支配集节点共同维护路由信息，路由搜索功能复杂；而图 2仅1个支配集节点，路由信息由1个节点维护，路由搜索更简单，性能明显优于前者。

相同仿真环境下对CDS算法和改进算法进行仿真实验，实验中节点数量分别设为20、30、40、50、60个，另外通信距离r分别设为0.4和0.6，蒙特卡洛仿真次数为200次，并统计不同节点数和通信距离下两种算法获得的连通支配集节点数，统计平均值如图 3和图 4所示。通过图 3可知改进算法得到节点数比CDS方法少25%左右。由图 4结果可知改进算法得到节点数比CDS方法少50%左右。故而改进算法在获得连通支配集方面明显优于CDS算法，其原因是通过网内分布式计算获得了网络拓扑相关信息，提升了算法性能。且随着节点密度和连接复杂度的增加优越程度越明显。

本文通过研究Ad hoc无线网络的路由机制，对可以用来建立路由的连通支配集生成算法进行改进。改进主要有两个方面：1)通过借助“拓扑可知”理论，通过网内节点的分布式计算获得含有拓扑相关相信的特征矢量中心性值，并利用特征矢量中心性值进行节点id编号，避免了节点缩减时的随机性，使节点缩减与实际网络拓扑紧密联系；2) CDS算法对最大id节点是否可缩减并没有进行判定，改进算法提出规则3来完成最大id节点的缩减判定。通过改进，本文通过“拓扑可知”相关的图谱理论，将CDS算法中完全NP难问题转变为具有条件最优解的问题，改进算法可得到条件最小支配集，无需中心节点，可以完全分布式实现。