一种无线传感器网络可靠拓扑的生成算法*

和 鹏，毕红军

(北京交通大学 通信与信息系统北京市重点实验室，北京100044)

0 引 言

无线传感器网络(WSNs)是由部署在监测区域内大量的、简单的传感器节点组成，通过无线通信方式形成的一个多跳的自组织的网络系统，其被广泛应用于医疗卫生、环境保护、军事侦察等领域。这些应用都需要节点将采集到的数据信息传送到汇聚节点，汇聚节点将数据融合后再进行合适的操作，然而，无线通信信道容易受到干扰和噪声的影响，为确保数据信息传送到汇聚节点，可靠性是一个很重要的问题。

现在已有许多关于拓扑生成算法的研究，这些研究在优化节点度和路径长度［1，2］，端到端延迟和数据包丢失［3］，能量消耗［4～6］等方面做了很多工作。例如:文献［7］提出，当θ≥π 时，一个2π/θ 边连通拓扑，被称作无线传感器网络的物理拓扑。在文献［8］中，基于最小生成树的k 边连通拓扑，被称为LTRT。然而，以上研究都没有在链路连接失败时提供替代路由。

无线传感器网络可以描述成一个在二维欧几里得空间中，由N 个节点组成的集合V。假定所有节点的传输距离为R，当且仅当两个节点的欧几里得距离小于等于R 时才能相互通信，这种相互通信的能力用相应节点之间的边来描述。由此，图G=(V，E)是网络的物理拓扑，其中，G 为一个UDG 图。由于网络中的节点处于不断变化的环境中，节点的状态也在相应地发生变化，加之无线通信信道的不稳定性，因此，G 也在不断地调整变化。拓扑生成问题就是定义给定物理拓扑的子图，随之数据包路由就会形成。因此，本文将这种物理拓扑的子图称为路由拓扑。

本文对路由拓扑的可靠性问题进行研究，采用构建可靠的网络拓扑，提供替代路由传递重要信息的方法来提高可靠性。首先给出一个可以用于任何支撑结构的k 边连通拓扑结构，并为此提出一个通用的算法。根据研究需要，考虑从最小生成树(MST)、最短路径树(SPT)、度受限的最短路径树(DCSPT)和Gabriel图(GG)等基本支撑拓扑构建k边连通拓扑。仿真实验对不同拓扑的可靠性进行了探究。

1 可靠拓扑的生成算法

对于图G=(V，E)，若G 的顶点数大于1 且对任意少于k 条边的集合F⊆E，G-F 均是连通的，则称G 是k 边连通的，在G 中的任何两个节点之间都有k 条不同的路连接。给定一个k 边连通的物理拓扑G，构建一个k 边连通路由拓扑的问题就是找出一个G 的连通子图Dk(G)，在Dk(G)中任意两个节点之间都会有k 条分离式替代路径。本文在构建k 边连通拓扑时，选取k=2，也就是在给定的物理拓扑中找出一个2 边连通路由拓扑。

可靠拓扑生成算法描述如下:首先构建一个1 边连通拓扑D1(G)，它是G 的一个子图，然后把所有属于D1(G)的边从G 中删除。这样做可能会使G 不连通并且由2 个或更多连通的分支组成。接下来，为每一个连通的分支构建一个对应的1 边连通拓扑。然后把新找到的边添加到D1(G)中形成2 边连通拓扑D1(G)。上述算法是一个通用算法，它可以为不同支撑结构构建一个k 边连通拓扑。

算法1 k 边连通拓扑Dk(G)

E1是G 的一个分支连通支撑子图的边

D1(G)←E

for i←1 to k-1 do

将D1(G)的边删除，得到连通分支Di1(G)，Di2(G)，…，Dil(G)

for j←1 to l do

生成分支连通支撑子图Dil(G)

end for

合并Di1(G)，Di2(G)，…，Dil(G)以得到Dk(G)

end for

Dk(G)的k 连通特性在定理1 中得到了证明。

定理1 令E1是图G=(V，E)的一个分支连通支撑子图所有的边。任意i≥2，令Ei是图)的一个分支连通支撑子图所有的边。对于正整数i，图Di(G)=(V，，则对于k≥1，如果G 是k 边连通的，Dk(G)也是k边连通的。

证明:用归纳法来证明，对于所有1≤l≤k，Dl(G)是l边连通的。注意到D1(G)是G 的一个连通支撑子图，也因此是1 边连通的。再考虑2≤l≤k，假定Dl-1(G)是(l-1)边连通的。对于和Dl(G)=(V，)就是Dl-1(G)简单地加上边El。

假定Dl(G)不是l 边连通的，令{e1，…，el-1}是Dl(G)的一个割边，割边将顶点集合A 从顶点集合B 中分离出来，此处V=A∪B。因为Dl-1(G)是(l-1)边连通的，所以，{e1，…，el-1}的每条边必须是Dl-1(G)的一条边。又由于G是l 边连通的，所以，在中至少有一条边连接A 和B。亦即A 和B 中各有一个顶点在中是连通的，而在(V，E1)中不连通，这与(V，E1)是的分支连通支撑子图相矛盾。因此，可以得出Dl(G)是l 边连通的，定理得证。

依据算法1，可以定义如下一系列的路由拓扑:首先利用MST 构建子图D1(G)，删除D1(G)的边，再次在子图中利用MST 便可得到MST2。SPT2，DCSPT2 和Gabriel2 都是以同样的方式来构建。此外，Gabriel 可以和其他拓扑相结合，DCSPT-Gabriel(DCGB)拓扑也是G 的子图，它首先根据DCSPT 构建子图，然后利用Gabriel 图在剩余分支上构建DCSPT-Gabriel。MST-Gabriel(MSGB)与DCGB 的构建方式相同。

为了评估不同路由拓扑的性能，本文利用TDMA 链路调度。在TDMA 调度中，无冲突协议通过在链路中设置时隙来共享可利用带宽并控制数据包传输。为达到这个目的，采用集中控制模式，在该模式下汇聚节点从节点处收集信息来计算和传播调度长度。假设时隙的长度足够包含一个从接收器发来的ACK。当一个传感器节点传输的信息没有得到确认，它就会检测到一个下行链路。因此，失效的链路会被本地检测到，并且包路由也由本地决定。因为拥有2 连通拓扑，表示至少有2 条不同的链路以保证数据包路由到汇聚节点。当下行链路存在时，就需要交替利用2 条链路:一条是最好的链路，另一条可能是次好的链路。传感器在每个安排的时隙里尝试连接最优的链路，如果尝试失败，传感器在接下来的阶段尝试连接第二条链路。这个过程会持续下去，直到数据包通过1 条链路成功传送或者达到重试次数的限制(在仿真中设定为7 次)。当达到重试次数限制时，数据包就会被丢弃。

2 仿真与性能分析

2.1 仿真环境

使用Matlab 仿真来评估路由拓扑的性能。重点讨论在存在链路失效的情况下，不同拓扑的路径质量和提供替代路径的能力。实验中，将N 个传感器节点均匀分布在100 m×100 m 的矩形区域。每个节点的传输范围是25 m，节点在彼此的传输范围内时便可以相互通信，并由此产生底层物理拓扑，仿真只利用2 连通的物理拓扑。下面的每个结果都是1 000 次实验的平均值，并给定95%的置信区间。

本文考虑在动态环境下进行仿真，允许每种拓扑自由选取他们最佳的汇聚节点，并观察其相应的行为。

2.2 性能分析

本文主要探究数据包传输率。由于本文所分析的拓扑是2 边连通的，并且网络中的任何一个传感器都能被选为汇聚节点。因此，在这个动态仿真环境中，选择拥有最小调度长度的传感器作为汇聚节点。为保证比较的一致性，每种拓扑的仿真运行时间和产生数据包的数量都相同。

首先，设定数据源节点产生数据包的概率为10%，20%，30%，40%，50%，链路失败的概率设定为10%。不同拓扑的平均数据包传输率如图1 所示。

图1 不同数据包生成概率下平均数据包传输率Fig 1 Average data packet delivery ratio with different data packet generation probability

DCSPT2 和SPT2 的数据包传输率低于其他路由拓扑，这是由于尽管它们有最短路径，但却有更高的平均路径长度。造成这种结果的原因是提供最佳调度的汇聚节点是相对于图的边来说的，这为并行传输提供了最大的机会，并且有最少的冲突。相比之下，Gabriel 和MST 汇聚节点的位置能够提供更短的路径长度。更长的路径更容易因为连接失败而失效，因此，数据包在仿真时传输率更低。基于Gabriel的拓扑有更多集中放置的汇聚节点和最短的路径长度，可以更可靠地传输数据包。

设定数据包生成概率为1%，而链路失效概率设定为5%，10%，15%，20%，25%。不同链路失效概率下平均数据包传输率如图2 所示。

图2 不同链路失效概率下平均数据包传输率Fig 2 Average data packet delivery ratio with different link failure probability

正如预期的那样，DCSPT2 和SPT2 的数据包传输率由于汇聚节点位置问题受到失效链路的影响最大，其他拓扑的性能都很稳定，基于Gabriel 的混合方式DCGB，MSGB 性能最好。

实验发现，数据包生成概率比链路失效概率对拓扑性能的影响更大，这是因为当最优路由连接失败时，这些拓扑可以提供到汇聚节点的替代路由。

3 结 论

本文提出了一种无线传感器网络可靠拓扑生成算法，该算法能够设计可靠的2 边连通路由拓扑，为无线传感器网提供替代路由。此外，分析了不同拓扑的可靠性和在连通失效时的链路质量。仿真结果显示:基于Gabriel 图的拓扑在可靠性和路径冗余之间给出了最好的折中方案。

［1］ Ghosh A，Incel Ö D，Kumar V S，et al.Multichannel scheduling and spanning trees:Throughput-delay trade-off for fast data collection in sensor networks［J］.IEEE/ACM Transactions on Networking(TON)，2011，19(6):1731-1744.

［2］ Gelal E，Jakllari G，Krishnamurthy S V，et al.Topology control to simultaneously achieve near-optimal node degree and low path stretch in Ad Hoc networks［C］∥2006 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks，SECON’06，IEEE，2006:431-439.

［3］ Zinonos Z，Vassiliou V，Ioannou C，et al.Dynamic topology control for WSNs in critical environments［C］∥2011 4th IFIP International Conference on New Technologies，Mobility and Security(NTMS)，IEEE，2011:1-5.

［4］ Staniec K，Debita G.Evaluation of topological planarity and reliability for interference reduction in radio sensor networks［J］.EURASIP Journal on Wireless Communications and Networking，2012(1):1-7.

［5］ Qureshi H K，Rizvi S，Saleem M，et al.Poly:A reliable and energy efficient topology control protocol for wireless sensor networks［J］.Computer Communications，2011，34(10):1235-1242.

［6］ Karim L，El Salti T，Nasser N，et al.The significant impact of a set of topologies on wireless sensor networks［J］.EURASIP Journal on Wireless Communications and Networking，2012(1):1-13.

［7］ Poduri S，Pattem S，Krishnamachari B，et al.Using local geometry for tunable topology control in sensor networks［C］∥IEEE Trans on Mobile Comput(TMC)，2009.

［8］ Miyao K，Nakayama H，Ansari N，et al.LTRT:An efficient and reliable topology control algorithm for Ad-Hoc networks［J］.IEEE Transactions on Wireless Communications，2009，8(12):6050-6058.