图论在计算机和无线传感器网络中的运用分析

孙帅

摘 要：21世纪，计算机技术的出现，从根本上改变了人类社会生产和生活方式，计算机凭借着强大、高速的计算能力，深入到现代科研、生产等多个领域，在其中占据着至关重要的位置。从某种意义上来说，计算机发展正推动者整个社会进步。图论作为一种简单、系统建模方式，能够将问题转换为图论问题，然后运用图论基本算法解决问题，以此来提高问题解决有效性。文章将从图论相关内容入手，分析无线传感器网络中的聚类问题，并探讨图论在计算机与无线传感器网络中运用，最后基于上述研究内容对算法性能进行梳理。

关键词：图论；计算机；无线传感器网絡；运用

近年来，人类社会正式进入到信息时代，移动传感器网络凭借自身在数据采集、鲁棒性等方面具有的强大优势，在军用、民用等方面得到了广泛应用，并能够实现对环境高效监督和控制，且能够提高防御效果。相比较具有固定设施的通信网络，无线传感器自身具有的组织机制，能够赋予系统抗毁性、灵活性，但其自身实施对象能力存在一定局限性。故我们将图论引入到计算机与无线传感器网络当中，能够实现对通信效率、时机等要素进一步协调，以此来实现快速高效的网络自组织，提高网络运行有效性。

1 图论概述

图论是数学一部分，以图为研究对象的理论。图论当中的图是由多个既定的点构成的图形，这种图形能够描述某些事物之间特定关系，用点代表事物，运用连接点与点之间的线，能够体现出事物之间的关系。图论最早起源于非常经典的问题，即柯尼斯堡问题，欧拉是图论创始人[1]。19世纪英国数学家汉密尔顿发明了一个游戏：运用规则实心十二面体，各个顶点标记为城市，游戏者要沿着各边通过每个顶点形成闭回路。运用图论语言来解释，游戏的最终目的在于在十二面体图中形成生成圈，正因为运筹学、计算机科学及编码理论中的多数问题都可以运用汉密尔顿问题来解决，故引起了广泛关注。

随着无线通信技术快速发展，传感器技术也随之发展，传感器具有的低成本、低能耗等优势，在实践应用中能够有效感知周围环境、简单处理数据。通常来说，传感器由感知、处理、收发及功能单元构成。在不同领域中的应用，还会增加定位器、能量产生单元等附加组件[2]。感知单元是整个传感器的核心，由感知组件与模数转换器构成，前者能够感知地震波、声波等参数。而后者能够对不同格式的数据信息进行转换。

2 无线传感器网络中的聚类问题

无线传感器网络存在能量限制，减少需要传输数据量，能够有效节省节点能量。故在从不同节点收集数据过程中，可以在现有节点基础上，实现对数据予以融合处理，消除冗余信息，以此来实现降低能量消耗的目标。但值得注意的是，节点易失效，影响数据融合效果，因此无线传感器网络，同样要采用数据融合技术综合数据，以此来提高信息准确度[3]。一般来说，当传感器分布在范围较大的区域、数量较多时，传感器数据如何朝着融合中心传输成为亟待解决的关键问题。当前，现有技术发展水平下，可以构建三层分级网络结构，并借助聚类算法。

聚类是一项数据分析技术，是将物理、抽象对象的集合，分组成由类似对象构成多个类的过程。但当前多数算法都集中在单一环境，很多应用中的数据源存在于网络环境中，且聚类前，会数据采集到中心位置无法实现对数据信息的高效处理[4]。主要原因是，无线传感器网络中的有限通信宽带，建立在感知节点之上，电池能源有限，无法确保网络持续运行，但现有的聚类算法尚无法做到上述目标。图2是图论聚类算法框图。

聚类算法按照既定的流程进行计算，能够寻找到信息传输最佳路径。

3 图论在计算机与无线传感器网络中的运用

针对上文来看，将图论应用到计算机、无线传感器网络当中，能够尽最大限度收集覆盖范围所有点，且能够有效弥补失效点，实现覆盖范围内数据传输有效性。为了进一步了解图论对于无线传感器网络的积极作用，文章将进行详细分析，具体如下：

3.1 图广度优先搜索算法

在实践中，根据节点数量与需要分成的簇数需求，能够获得每个簇节点数，对整个图广度优先所搜记录下节点数量，达到N/M后记所有节点，重新清零处理，直至整个图完全遍历完成后，将相邻的节点划分为M个子图，子图对应独立簇。图的广度有限搜索算法具体流程如下：从图中某一顶点出发，将其设置为VI，从该点出发，依次访问所有没有被访问的邻接点，如果图中没有被访问的点，要从中选择某一个作为起点，重复上述过程，完成对所有點的访问。

3.2 簇内节点信息传递最优路径实现

针对簇内信息传递来看，其目标是运用最小的能量代价，将信息传给簇头。本文选择普里姆算法，实现对簇子图优化构造和设计。普里姆算法是图最小生成树一种构造算法。假如WN=（V，{E}）中含有多个顶点连通网，TV是其中最小生成树顶点集合。可见，完成算法执行时，开始时TE为空集，仅有一个顶点。故基于普里姆算法构造最小生成树，即将所有点都集中在生成树上，而另一顶点尚未落在生成树上，取一条权值最小的边，逐条加在生成树上，完成所有点的结合。找出子图最小生成树后，可以选择直接连接节点最多的节点作为簇头，其他节点信息能够通过不同渠道实现，最后由簇头传输到数据融合中心，对数据信息进行分析和研究。

3.3 覆盖与Voronoi图

所谓覆盖率，是指网络能够探测到目标范围内，在目标区域总面积的占比，是评价自组织覆盖算法好坏的具体标准。好的自组织算法，能够使网络尽可能最大限度上覆盖目标区域，且能够在部分传感器节点失效情况下，进行网络调整和优化，以此来实现对失效节点的有效弥补。Voronoi图（如图3）是提高某些算法运算速度的主要方式和方法。通常而言，二维图形能够在特定时间范围内获取，而三维图获得信息时间较长，Voronoi图性质决定了其与很多几何结构存在密切联系，通过该图，很多集合算法能够快速实现，提高运算效率。值得我们注意的是，如果某个二维、三维点集中在四点共圆当中，此时，这些点对应的多边形中会有一个顶点。这些点相互连接，最终形成了不同的形状。综上来看，在二维、三维传感器节点自组织中，只要节点探测半径范围内形成的圆，能够包围住多边形，实现全面覆盖。

3.4 连接与三角剖分

连接目的是将网络构成一个整体，如果网络分化为多个不相连的子网络，其中部分子网络感知到的信息，将会成为无效信息。故我们希望网络中彼此都能够相互连接，确保整个网络协调、有序运转。实践中，在图论理论基础之上，三角形网格图中，称一条内边e是局部优化，指共享e的两个三角形对应形成的四边形能够形成较好的部分。简而言之，如果e具有局部优化，那么形成的四边形不存在凹多边形。称三角形网格是全局优化的，如果它所在内边具有局部优化，可以证明在特定节点集合所有网格当中，全局优化三角形网络具有最优性。通过上述分析，运用这种方式，在三角形网格中，各个节点之间的信息能够相互传递。

无线传感器网络自组织度衡量所有节点，自组织贡献率存在差异性。一般情况下，自组织越大，节点自身自组织贡献率差异性，网络自组织演化，对少数节点、节点集依赖性相对较小，因而网络更具鲁棒性。正因如此，图论对于无线传感器具有的促进作用使得二者能够深入整合。

4 算法性能分析

文章在PC机上运用VC++6.0编程环境，实现上述算法，通过多线工作方式模拟无线传感器网络工作环境。在仿真中，将无线传感器网络在图论上的分布式聚类算法与所有数据传回，并进行统一计算和处理，通过对二者性能进行比对，最后确定出随着网络节点数量增加，算法执行时间变化情况。根据上述内容形成比较曲线，如图4，其中横坐标与纵坐标分别代表的是节点数目、时间，从仿真实验结果中发现，图论分布式聚类算法较传统集中算法性能更好。

为了验证网络鲁棒性，我们在节点自组织稳定后，从中随机拿掉两个节点，观察网络再组织能力获得仿真效果。根据仿真结果来看，随机减少的两个节点，传感器网络依旧能夠良好地进行再组织，不仅能够有效弥补失去节点的空白，且能够使得网络对划定区域保持较高的覆盖率，使得网络更具整体性。另外，通过观察自组织曲线来看，当网络处于稳定状态后，虚拟里自组织办法能够使传感器网络在自组织过程中，保持较高的自组织度，且能够实现进一步优化。虽然网络节点有所减少，自组织度会下降。但在虚拟里的作用下，网络能够在短时间恢复到最佳状态，不断对其进行优化，可见网络鲁棒性、灵活性较好。随着科学技术不断发展，计算机与无线传感器网络在未来社会发展中的应用范围将会越来越广，对此我们还要增加资金、人力等方面投入，加大研究力度，进一步深化无线传感器结构与性能，使其能够在应用中充分发挥积极作用。

5 结论

根据上文所述，无线传感器网络在实践应用中，强调的是无线传感器网络由无到有、从小至大的过程。该网络凭借自身较好的鲁棒性、高效性及灵活性等优势，在实践中得到了广泛应用。而图论理论的提出和应用，为进一步优化网络性能提供了極大的支持。文章从覆盖、连接等多个方面对图论在计算机与无线传感器网络中运用进行分析和研究，并对算法在实践应用中产生的性能进行验证发现，图论对于无线传感器网络良好运行具有积极作用，能够及时发现其中的问题，并采取相应的措施加以规范和优化，不断提高网络运行有效性，从而为相关领域持续发展奠定坚实的基础。

参考文献

[1]李琳.无线传感器网络路由算法仿真模型的研究[J].电脑开发与应用，2014，（4）：27-29，32.

[2]师超，仇洪冰，陈东华，等.一种简单的分布式无线传感器网络时间同步方案[J].西安电子科技大学学报，2013，（1）：93-99，147.

[3]何剑海.无线传感器网络定位技术在农田复杂环境中的应用[J].无线互联科技，2013，（2）：187-188.

[4]肖大威.无线传感器网络中数据存储与访问进展分析[J].电子制作，2013，（9）：149.

（作者单位：北京邮电大学）