连通图3-跳连通控制集的数值模拟

3-跳连通控制集的数值模拟网络算法与理论在对真实网络的结构优化，性能提升方面有着重要意义。而一个网络的连通控制集则囊括了网络的关键节点。而这些对于分析一个网络的性能而言至关重要。而对于无限传感网络而言，其2-跳、3-跳连通控制集就可以囊括支撑网络的大部分关键节点。故本文便尝试使用最小支撑树算法与贪婪算法，对一个连通图的3-跳连通控制集进行求解。在数值试验之后，我们将所得结果进行比较。发现贪心算法的结果较最小支撑树算法有更好的表现。 第一章引言网络算法，随着信息技术的发展，逐渐引起了人们的重视。一个适合的网络算法与理论对现实世界中网络的搭建，其工作时的能量消耗，传播效率等都有很大的帮助。而对于一个连通网络而言，其连通控制集能够很好地表示网络的关键节点，因此能够很好地提供对于网络优化的方案。因此，在许多网络的优化问题中，都需要求出该网络的连通控制集。而我们要讨论的无线传感器网络，其优化问题及网络分析便十分依赖于其多跳连通控制集。无限传感网络，是特指由无线传感器组成的网络。第一代传感器网络在20世纪70年代就已经出现了。此类传感器采用的是点对点传输。随着相关研究的不断深入，无线传感器网络还获得了对多类信息信号的信息综合、信息处理能力，为第二代传感器网络。而伴随无线传感器技术的普及与发展，人们对无线传感器网络的应用日益重视。其相关的网络理论及算法研究也日益深入。在网络中，每一个传感器都具有接收性息与传递信息的功能，且拥有有限的能量。而多个无线传感器之间相互感应，传递，处理信息，相互合作可以完成真个信息处理的功能，从而组成一个没有实际框架的信息传输网络。这类网络相比与传统的有线网络而言，有着搭建方便，网络结构变动灵活的特点。因此，在信息技术飞速发展，信息需求急速扩大的今天，无线传感器网络有着广大的应用前景。物联网，智能家居，智能汽车等等智能设备，其相互之间搭建的网络便是一个典型的无线传感器网络。考虑到智能设备之间通常不存在有线连接的条件，它们之间的通信通常是由无线通信完成的。因此它们之间会自组织地形成一个无线传感器网络。除此之外，无线传感器网络还能节约大量的人力资源。在预防森林火灾中，我们可以将大量的无线传感器部署在森林的各个角落，并且检测森林的温度。如此一来，如果发生了森林火灾，则传感器则可以在第一时间获取火灾所发生的地区，火势的大小等等。这能让消防人员第一时间获取火灾的相关信息，以着手准备应对方案。这对于防火救火都有很大的帮助。当然，在森林中部署大量的无线传感器是一笔不小的开支。而一个好的拓扑结构则可以在传感器网络效果没有特别大的变动的前提下，减少传感器部署的数量，从而减少相应的支出。无线传感器网络不仅在民间有着应用，在军事上更是有着不可或缺的地位。在现代化战场，并没有基站这类基础设施。因此，多数情况下只能搭建自组织网络进行无线通信。这种自组织网络是一个多跳网络，其终端兼有路由器与主机的两种功能，可以看作是一个传感器，因此，也可以通过对无线传感器网络的分析方法对其进行分析。这种网络在近代中东战场，诸如伊拉克与利比亚，都有广泛的应用。美国的橡树岭国家实验室（OAK）曾预言，“IT时代正在从计算机网络逐渐转变成传感器网络”。而无线传感器技术也被国家信息产业部列为我国“十一五”的重点突破邻域。然而，纵使无线传感器网络有如此重要的应用地位，其缺点也是存在的。考虑到传感器并没有实际的连接框架基础，其通信完全依赖于传感器节点。而传感器节点在运行过程中有可能会发生故障，或是其能量耗尽，从而导致通信中断。而如果无线传感器网络的组织不够完善，致使其鲁棒性不强，则很有可能会因为其中少量的几个传感器的故障而导致网络的整体崩溃。除此之外，在无线网络中，其通信方式也需要进行的考量。无线传感器网络中的一个基本通信方式便是广播，其直接实现方式是“泛洪”，即传感器节点在感应到广播数据后都对其进行转发。这种方式会造成大量不必要的转发，不仅会消耗传感器大量的能量，减少网络寿命，还会产生大量噪声，对传感器造成干扰，造成传播中的“信息风暴”，拥堵传输信道。因此，无线传感器网络的拓扑控制拥有不可比拟的重要意义。它不仅能够提高网络的鲁棒性与容错率，还可以找到适合用于传播数据的节点，减少网络的整体能量损耗，并避免信息风暴的产生，延长网络寿命。在一般思维下，传感器无线网络性能的提高依赖于传感器硬件性能，诸如传播距离，能耗，储存能量，运算速度等的提升，而现在我们可以看到，对于网络拓扑控制、网络协议、算法优化，对传感器网络性能的提高同样十分重要，而且这种方式更为巧妙。一般而言，无线传感器的网络质量的衡量标准是其虚拟骨架。它可以反映网络关键节点的大小，信息传播的大致速度等。在对无线传感器网络质量进行分析之前，我们需要求出其虚拟骨架。而网络的连通控制集已经广泛地在无线传感器网络的虚拟骨架构造中应用。因此，我们需要找到一个能够求得连通控制集的方法。但不幸的是，求图的连通控制集被证明为一个NPC问题。因此，对于该问题并没有一个完美的多项式解法。而本文中，我们尝试构造的是单位圆盘图中网络的3-跳连通控制集。分别尝试了最小支撑树方法与一种最近提出的贪心算法。对于贪心算法而言，我们也尝试了两种不同的参数。在数值试验后，这些算法都分别成功地得到了所需要的结果。之后，我们对其中的两次数值试验的结果进行比对。最后，我们一共进行了100次的重复数值试验，对生成的100张随机圆盘图构成的网络分别用三种方法构建3-跳连通控制集，得到其骨架网络的平均节点数。第二章预备知识定义2.1 相邻节点：若u, v为图G=(V, E)中任意两个节点，若E中存在边连接节点u, v，则称节点u与节点v互为相邻节点。定义2.2 导出子图：设G1=(V1, E1)为G=(V, E)的子图，如果V1中任意两点u, v在G1中相邻当且仅当他们在G中相邻，则称图G1为V1在G中的到处子图，记为G1=G(V1)。定义2.3 独立集(independent set)：子集UV称为图G的独立集，若U中任意两点都是不相邻的。若VU中任一点至少与U中一个点相邻，则称U为极大独立集(maximal independent set(MIS)。定义2.4 控制集(dominating set)：图G=(V, E)的一个子集SV称为控制集，若VS中任一点至少与S中一个点相邻。定义2.5 3-跳连通控制集(3-hop dominating set): 图G=(V, E)的一个子集SV称为控制集，若VS中任一点至少与S中一个点的距离小于3。定义2.6 连通控制集(connected dominating set)：若一个控制集S的导出子图是连通的，则称S为连通控制集(CDS)。定义2.7 圆盘图(Disk Graph): 在平面中放置若干不等大小圆盘，每个圆盘的圆心对应一个节点。从节点u到节点v有弧(arc)，当且仅当u对应圆盘包含v，所得的图被称为圆盘图，在一般情况下为有向图。第三章最小支撑树方法最小支撑树方法是求3-跳连通控制集的一个十分经典的方法。最小支撑树方法的思想是，首先求出图G的3-跳极大独立集3-hop MIS，亦即网络的3-跳控制集。然后不断地向3-跳独立集里加入新的节点，直到原来的3-跳极大独立集连通为止。即在图G中找到3-hop MIS的最小支撑树，从而使得极大独立集连通。此时所得到的集合一定是3-跳连通控制集。首先我们要求出一个连通图的3-跳极大独立集，其算法步骤如何：步骤1：将图G中的所有的节点标记为max，其中max为一个足够大的值。步骤2：任取一个节点u，将其标记为0，并加入传播队列Q。步骤3：对所有传播队列Q中的节点u进行传播，即对u的任意相邻节点v，若mark(v)（即v的的标记值）mark(u) +1，则将v的标记值设为mark(u)+1，若mark(u)+1=4，则再将v的标记值设为0。之后将v加入传播队列。最后将u移除队列Q。步骤4：若传播队列Q为空，算法结束。其中标记值为0的节点的集合即为我们所要求的3-跳极大独立集。否则返回步骤3。图3.1 某个图的极大独立集标记过程的最后结果。其中起点为左上角。在求得3-跳极大独立集后，便可向其加入节点使其成为连通集。但节点加入的方式并不是任意的，否则连通集的规模将无法控制，如此我们可能会得到一个很大的3-跳连通控制集。虽然这样的集合符合所求的要求，但并没有太大的实用价值。最小支撑树方法是通过寻找与为被加入的3-跳连通集的的一个节点，寻找其与已加入的节点的最短路，并将最短路所经过的节点加入进来。这样能够保证支撑树处于一个较小的规模。其算法的步骤如下：步骤1：令M为我们之前所求的3-跳极大独立集。 =，C=步骤2：找一条到的最短路，其中 ， 。令， 。步骤3：若，算法停止，输出，否则返回步骤2。这样我们所得到的结果就是所要求的3-跳连通控制集。其中的M保证了所求集合是3-跳控制的，而C则保证了所求集合是连通的。第四章贪心算法这里采用的贪心算法是Xianyue Li et al 在A New Greedy Algorithm for d-hop Connected Dominating Set中提出的贪心算法。这种算法可以普遍运用于d-跳连通控制集的构建。特别的，本文考虑d=3的情况，即用该算法构建3-跳连通控制集。该贪心算法的第一步与最小支撑树法一致，我们需要求出图的3-跳极大独立集M。随后我们将所求集合的元素放到中，并且不断向里面加入新的节点，直到将所有M中的节点加入至即可。的初始值是M中的任意一个元素，在加入新的节点时，遵循以下规则： 首先选取一个中间节点，中间节点属于的阶邻域，且其阶邻域所包含的中的节点数最多。在选取了中间节点后，求出其与M中距离小于等于的节点的最短路，对于这些最短路所经过的节点，将属于M的那部分加入至中，其余加入至C中。利用这种贪心规则，我们可以较好的减少所求的3-跳连通控制集的规模。图4.1中间节点的选取。其中u为中间节点。此时的=3其算法步骤大致如下：步骤1：，令，。其中为之前求得的3-跳极大独立集。步骤2：在的阶邻域中找到一个点v，使得v的阶邻域与的交最大。再令， 。其中为节点v的阶邻域与的交，为节点v与最短路径上的一般节点的集合交上v与的最短路径上一般节点的集合。其中，一般节点指的是既不属于中间节点，也不属于M的节点。步骤3：若，算法停止，输出，否则返回步骤2。通过选取中间节点，我们可能可以得到较最小支撑树方法节省的路径，从而减小作连通作用的集合C的规模。而算法中的参数则限定了选取中间节点的范围，它的变动对于算法的效果也有很大影响。特别的，对于3-跳连通控制集而言，需大于等于2。第五章数值试验及分析在求网络的3-跳连通控制集之前，需要先构建出一个网络。我们首先构建一个随机的圆盘图。首先我们需要如下假设：假设1：每一个传感器节点都能够向它周围的所有节点发送信息，其传播范围为一个半径为r的圆盘。假设2：所有传感器节点都有相同的传输半径r。假设3：所有传感器节点都在同一平面。在这三个假设下，我们在长x，宽y的矩形区域据平均分布随机选取n个节点，每个节点的传播半径为r。获取连通圆盘图的算法步骤如下：步骤1. 依据平均分布随机选取n个点。步骤2. 对任意两个点u, v，若u, v间的距离小于r，则u, v相邻。最后可以得到圆盘图G。步骤3. 若G连通，算法结束。否则返回步骤1。最后可以得到连通的圆盘图G。在以下的数值试验中，我们所生成圆盘图的参数如下：每个圆盘图共有200个节点，图的总体长宽均为70，每个传感器的传播半径为10。在得到G后，分别使用了最小支撑树算法，=3的贪心算法以及=2的贪心算法构建G的3-跳连通控制集。我们取了两次数值试验的结果，如下图：图5.1图5.2图5.3图中蓝色的米字符代表圆盘图的节点，连线表示其连通性。而带五角星标示的点则标示其属于3-跳连通控制集。其中，图5.1为使用最小支撑树算法所得到的结果，其3-跳连通控制集的大小为32；而图5.2为使用的贪心算法算法所得到的结果，其3-跳连通控制集的大小为26，图5.3为使用的贪心算法算法所得到的结果，其3-跳连通控制集的大小为25。可以看到，单从此次的数值试验来看，对于同样一张连通图而言，的贪心算法算法效果优于的贪心算法算法。而最小支撑树算法的试验结果最差。当然，一次试验的结果不足以证明其普遍性，我们随后进行了第二次数值试验，其结果如下：图5.4图5.5图5.6图中的标示同第一次数值试验结果。其中，图5.4为使用最小支撑树算法所得到的结果，其3-跳连通控制集的大小为39；而图5.5为使用的贪心算法算法所得到的结果，其3-跳连通控制集的大小为33，图5.6为使用的贪心算法算法所得到的结果，其3-跳连通控制集的大小为30。与第一次试验相同。随后，我们重复进行了100次数值试验，分别对这三种算法所得到的3-跳连通控制集的结果进行了统计。最终得到了它们所算的的3-跳连通控制集大小的期望。其中，最小支撑树方法为32.26，的贪心算法为29.6， 的贪心算法为27.17。可以看到，在统计上的贪心算法也要优于的贪心算法，而它们二者也要优于最小支撑树算法。这与上述两个实验的结果相同。第六章结论本文分析了无线传感器网络的相关研究背景与应用现状。深入阐述了网络拓扑控制及网络协议对无线网络优化的重要意义，其重要性不亚于硬件提升对网络效能的优化。由于虚拟骨架对分析网络质量有着标杆性的作用