物联网下自组织无线网络Ad Hoc算法的新技术设计

李瑞江

摘 要： 为了进一步改进自组织无线网络Ad Hoc的抗毁性，建立了信道分配的着色模型，对[α=0.585 7]进行了信道分配模型分析，在[a=18]时，所需的圆数量为64个，信道的数量为79个。进行算法求解分析，得出抽掉的节点数越多，网络的抗毁性越差，结果分析还发现5%相交面积的抗毁性小于18%相交情况的抗毁性，体现设计模型的抗毁性优势明显。

关键词： Ad Hoc网络； 信道分配； 抗毁性； 相交面积

中图分类号： TN958?34； TP391.4 文献标识码： A 文章编号： 1004?373X（2015）11?0024?03

A new technical design of Ad Hoc algorithm for self?organized

wireless networks under Internet of Things

LI Rui?jiang

（Xinjiang Institute of Light Industry Technology， Urumchi 830000， China）

Abstract： To further improve the Ad Hoc anti?destroying ability of self?organized wireless networks， the recolor model of channel allocation is established. When [α=]0.585 7， the model of channel allocation is analyzed. When [a=18，] the demand of circle number is 64 and the channel number is 79. The algorithm solution analysis is carried out in anti?destroying ability analysis. A conclusion is obtained that the more number of nodes are removed， the worse network anti?destroying ability is. The result analysis shows that the anti?destroying ability of 5% intersection area is less than 18% intersection area， the obvious advantages of anti?destroying ability is reflected by the designed model.

Keywords： Ad Hoc network； channel allocation； anti?destroying ability； intersection area

0 引 言

随着社会经济发展和技术进步，Ad Hoc网络已经成为网络技术发展的一个热点。对于大型公司野外任务和部队野外训练而言，有一个能够实时传递信息并实现信息初步处理的系统是十分重要的。Ad Hoc网络能够较为良好地完成这个任务，而且该网络有诸多优点，例如不需要基站建设，不需要特定的交换路由节点，并且实现了随机组建系统和接入形式的灵活和稳定。因此，这个系统在实际生活中有很多应用[1?5]。但是受发射信号的功率和信道的一定限制，导致节点通信因依靠无线信号传输而受到限制。因此要建立中间点作为中转点以实现信息的共享[6?9]。因此，在系统建立过程中就要面临一个重要的问题，即如何建立中介点，以多大的距离为标准建立中间点。在这个网络系统中，实行先到先服务，因此避免了信号冲突导致的通信不畅等问题[10]。基于这一背景，本文介绍基于Ad Hoc网络中的信道分配模型建立及其抗毁性研究，并具体分析其应用前景。

1 信道分配的着色模型

1.1 建立理论模型

在一个1 000[×]1 000（面积单位）的正方形区域内构建一个Ad Hoc网络，用最少个半径都是100的圆完全覆盖，要求相邻两个圆的公共面积不小于一个圆面积的[a0%（a0=5 or a0=18）]。要使圆域被完全覆盖就必会有大量重合部分，尽量减少重合部分的面积且不会引起通信盲区是解决该问题的关键点。如图1所示，设定变量角度[α，][β，]分别从横向和纵向来确定圆的个数。

约束条件：正方形面积和圆面积的重合部分面积最小化，但是要保证相交圆的面积占总面积的比重，如[a%，]再有就是不能出现通信故障和通信盲区。在这些条件基础上建立如下模型：

目标函数：

[Min Z=mrow×nrank+ceilnrank2×w]

[s.t. mrow=ceil1 0002rcosα（ 1 ）d=（2?r?sinβ）2-（r?cosα）2（ 2 ） nrank=ceil1 000d（ 3 ）90°-β090°π-sinβ0cosβ0=π×a0%（ 4 ） β1=90°-α2 （ 5 ）Max（β0，β1）≤β<π（ 6 ）0<α≤π2 （ 7 ）w= 1， x0为偶数 0， x0为奇数 （ 8 ）x0=ceil1 000rcosα （ 9 ）]

参数含义解释：[mrow]为第一行中一跳覆盖区的个数；[d]为每增加一行增加覆盖区域的高度；[nrank]为要覆盖整个正方形所需圆的行数；[β0]为当相交圆公共部分的面积恰好占总圆面积的[a0%]时的弦割角；[β1]为三圆共点弦割角的边界值；[α]为相交弦所对圆心角的一半；[w]为受在该区域内圆弦心距的数量控制；[ceil]为向上取整数；[a0%]为相交圆的公共部分占圆面积的比例。

模型解释：方程（1）限定了每一行有多少个圆。具体表示方法如下：方程（2）和（3）表示完全覆盖正方形需要多少个圆。方程（4）表示相交圆面积在整个圆中正好是[a%]时的弦割角大小。方程（5）表示当3个圆具有一个共同点的时候，弦割角的大小。方程（6）描述了弦割角的取值范围，只有在这个范围内方程才是有意义的。方程（7）是一个限定范围，表示相交弦所对的圆心角的[12]应该在的取值范围。方程（8）和（9）表示通信区内一跳覆盖区的数量。

1.2 着色模型

着色模型中，对公式的设计和计算的准确性要求很高。把[a=6，]10分别代入之前的模型，利用数学软件进行求解，可以得出，把[a=6]时，需要圆至少40个。

所谓信道分配，即对信息资源进行分配。根据着色模型基本理论，将[n]个圆划分成[K]个部分，将每两个圆的共有部分设计成为信息的通道，将会产生[K]个颜色。而且[K]是最小值，即无法再划分为[K-1]个子集。[K]也是需要颜色的最少数目。这个过程需要求出图的独立集合，并从中挑选出最小值，这就是求出颜色数量的基本方法。

图2所示的着色图，是通过上述算法计算出[α=0.585 7]时的信道安排。不同的颜色表示的是不同的信道，着色会有差异；而公共部分没有着色的区域是不同信道表示的最好方式，在实践中有很大的应用空间。

当[a=18]时，通过计算得出需要圆的数量为64个，信道的数量为79个。此时的着色信道如图3所示。

2 抗毁性分析

抗毁性是网络系统的一个重要技术，抗毁性的能力是衡量中断部分节点之间的通信需要破坏的链接数量。抗毁性的分析需要从黏聚度和连通度两个角度进行分析。本文只讨论在去除了一部分节点之后网络的连通度。一般而言，网络的连通度和抗毁性之间成正比。

2.1 抗毁性算法

对抗毁性的计算需要依照一定的约束条件进行，其具体算法见图4。

首先假设节点的表示方法，[P（A，B）]表示[A～B]的最大独立轨条数。独立轨表示的是[A～B]公共内的距离。假设[G]是一个非平凡的连通示意图，[{V1][V1]是[G]的点割集或[G?V1]是平凡图}为[G]的点连通度。即[K（G）]是使得[G]不连通或成为平凡图所必须删除的顶点的最小个数。这个假设在实践中被证明是有效的。接下来，将重点分析[A～B]的最大轨数的计算方法。连通的条件是在[G]图中的[v]顶点能够正常地发挥其设计作用，而非成为虚设点。

下面将分析图4表示的计算内容。假设[K（G）]的趋势是向正无穷大，然后在此基础上分析图中每一个顶点。如果[A]和[B]是不相邻的，中间具有很宽的范围，那么求[P（A，B）]可以采取求最大流的方法进行求解。而在对其进行一系列的分析之后，笔者发现，割顶集合的建立就会为顶连通度的实现提供前提。

2.2 设计的抗毁性分析

在前文所述的算法中，可以实现对节点的求解，并能够计算出在去除一些节点之后的网络连通度。在这个过程中，网络节点的连通具有一定的规律可循，因此从数学概率理论的角度，可以计算出网络节点的连通概率。

根据以上算法可求得从节点集合中随机地抽掉2%，5%，10%，15%等数量的节点后网络的连通度，就可以求得该网络节点的连通概率，表1给出了模型的抗毁性算法应用的结果。

由此得出结论，节点越多，抗毁性越强，否则反之。而纵向的比较能够得出结论，相交面积越小，抗毁性越强。这两个结论是整个系统的一个设计基础和实现系统功能最重要的部分。而相交面积的扩大没有带来面积内节点数量的增加，因此导致圆的个数也在不断增加。将这两个结论代入表格中的数据进行进一步的检验，可以证明其准确性。

表1 模型的抗毁性算法应用

[公共面积＼&抽调节点＼&总通信

节点数＼&2%＼&5%＼&10%＼&15%＼&5%＼&99.998 4%＼&99.94%＼&99.20%＼&96.75%＼&155＼&18%＼&99.75%＼&99.48%＼&97.41%＼&92.95%＼&225＼&]

3 总 结

Ad Hoc网络中的信道分配模型建立及其抗毁性的研究涉及的变量多，计算方法复杂多变，并需要很多的限制条件。而且按区域的分布划分信道，有一个潜在的问题，即每一个节点的发射信号面积之间有重合部分，因此导致了一定程度的资源浪费。因此该系统面临着一个新的挑战，即如何调整系统设计方式，并实现一定的技术进步以达到资源利用率的最大化和最优化。

参考文献

[1] 刘冰，刘全，禹华钢.Ad Hoc网络中的区域划分和资源分配问题[J].数学的实践与认识，2007，37（14）：16?24.

[2] 刘耀斌.基于平面拼装的Ad Hoc网络抗毁性研究及其信道分配[J].吉林大学学报：理学版，2008，46（6）：1159?1163.

[3] 胡兴雨，张学义，吴俊，等.移动Ad Hoc网络拓扑结构抗毁性测度模型[J].计算机工程与应用，2011（2）：78?80.

[4] 卢晓珊，贺永金，何伟，等.Ad Hoc网络中的区域划分和资源分配研究[J].数学的实践与认识，2009，39（8）：53?60.

[5] 徐武，雷剑，陶红亮.Ad Hoc网络中的覆盖和互联问题研究[J].景德镇高专学报，2009（2）：29?30.

[6] 任治国.Ad Hoc网络中的区域划分和资源分配问题[J].咸宁学院学报，2012，32（6）：44?46.

[7] 赵耀培，张福强，董茜.Ad Hoc网络技术研究进展[J].信息技术与信息化，2005（3）：9?12.

[8] 余旭涛，张在琛，毕光国.一种Ad Hoc网络可靠性度量：网络均衡度[J].应用科学学报，2005，23（6）：582?585.

[9] 田方，刘福杰，常义林.无线Ad Hoc网络关键技术研究[J].计算机与网络，2002（20）：50?52.

[10] 王华，薛涛，崔云平，等.Ad Hoc网络技术[J].硅谷，2012（17）：9?10.