基于小世界图无线多跳网络的研究

王雪冰

摘 要：将小世界图的思想应用于无线多跳网络。通过选择一小部分节点并放大它们之间的通信距离来建立一个网络模型。理论计算和仿真实验证明，这种模型可以表现出小世界模型的平均路径长度和聚类系数这二大特性。基于这个模型，提出了一个非均匀概率的洪泛算法。仿真结果表明，在网络覆盖和跳数这二个方面，小世界无线多跳网络大大优于一般的无线多跳网络模式。

关键词：小世界图 无线多跳网络 概率泛洪

一、引言

1967年，Milgram做了一个著名实验，他通过要求参与者传递信件，探索路径长度在相识人群网络中的分布。著名的“六度分离”概念正是起源于这个实验，尽管这个概念并没有出现在Milgram的著作中。 现代研究表明，在关系图中，重新布线或加入一些随机关联，将会导致常规图表有着很低的平均路径长度和高聚类的特性。我们称这类图表为小世界图。

无线多跳网络，包括Ad-hoc和网络传感器，它属于依靠节点之间的距离来链接的空间图形类别。实际上，这种网络并不被认为是小世界图，因为它很难在节点间建立一个大范围的连接。但是，如果对无线收发器的通信范围做一些修改，我们就可以得到更小的平均路径长度，这样就可以使无线网络具有了小世界特征。本论文中，将介绍一种基于小世界的无线网络模型。

此外，泛洪是一种在广播应用和作为其他的路由协议中必要的消息传播技术，例如在DSR（Dynamic Source Route）和ODMRP（On Demand Multicast Route Protocol）路由建设过程中，泛洪是必不可少的辅助和路由维护技术。但由于大量的包重播，信道争用和撞包的影响，简单的洪泛算法是远远不够的。为了节约宝贵的带宽，研究人员已经提出了概率泛洪算法。本论文中，将不均匀概率泛洪算法与小世界无线网络模型相结合。仿真结果表明，这样的组合会显现出极高的效率。

我们将建立一个小世界的无线网络模型。我们将提出一种基于小世界模型的非均匀概率泛洪算法。我们还将对所建模型和算法做详细的分析，并将网格网络和随机网络与普通的无线多跳网络模型进行比较。

二、建立小世界无线网络

典型的多跳无线网络中，所有的收发信机都具有相同的通信范围。当节点之间的距离超过该范围时，节点会通过路由对数据包进行交换，从而建成一个多跳（multi-hop）网络。在该小世界模型，随机选择一些节点并配备可与其他节点进行双倍距离通信的发送机。可以通过降低比特率，建立逻辑链路，或者配备多个无线电设备节点来建立。仿真表明，只需要将一小部分的节点变为强节点就可以显现出小世界效应。

仿真结果是基于创建400（20*20）个网格网络节点来实现的，对每个节点而言最多有4个邻节点。随机选择其中的节点作为强节点，可能有8个邻节点。随着强节点数量的增多，平均路径长度和聚类系数便可以进行计算。没有强节点或有400个强节点是两个极端的网络拓扑结构。通过仿真结果可以发现，只需要有20%的强节点，平均路径长度和聚类系数这两项指标就可以很接近极限。在此基础上继续增加强节点数目，并不能明显提高的效果。

由于强节点是在仿真网络中随机选取的，因此位于网格边界上的节点对长度和聚类的影响很小。如果我们了解并能利用这种网络的拓扑结构，那么就有可能在某些应用场合下使用全球定位系统，通过有意识地选择一些特殊的强节点，便可以得到更高的平均路径长度和聚类系数增益。

三、非均匀概率的泛洪算法

对于无线多跳网络，我们可以将无线多跳网络中的节点与站点之间的关系看作类似为渗流理论中的渗流点一样。Bhaskar对无线Ad-hoc网络的相变现象做了详细的说明。在对概率广播技术中的移动Ad-hoc网络（MANET）做了更深入的研究。他们得出一个结论，超过一定束缚的广播传送，例如pc，就不能得到很明显的提高。在这部分，我們将提出一个基于小世界的无线网络模式的非均匀的概率洪泛算法，并利用概率泛洪技术将它的优势与传统的泛洪无线网络算法相比较。

在普通的无线多跳（multi-hop）网络模型中，使用的都是概率广播技术，所有节点都有相等的传输半径并有着相同的频带。每个节点都配有一个发送机和一个接收机，并有着相同的重播概率。

但是在我们所建的小世界无线网络模式中，每个节点配备一个发射器和两个接收器。在整体网络中有两个传输频带，一个用于强节点，另一个用于普通节点。所有节点都可以接收和处理的两个频带的信号。其中强节点的通信距离是一个普通节点的两倍。不仅如此，强节点比普通节点具有更大的重播概率，这就是所谓的非均匀概率洪泛算法。

通过一系列的仿真可以比较上述二种不同模型的效果，仿真结果是基于二种不同网络：格形网络和随机网络。

1、网格网络案例

通过网格仿真：在2000米*2000米的区域，将400个节点设置为20行和20列并分布在此区域上。节点的通信半径设置为100米，所以在小世界模型中的强节点将具有200米的覆盖距离。将节点坐标为（1000，1000）的位置作为广播源，其他节点作为目标节点。在模拟中，随着重新发送的概率增加将会使0变化为1，这样两个目标统计就可收集。第一是接收包的节点的数目，这将反映一定概率泛洪时所覆盖的区域。第二点就是统计跳数，这将能反映平均路径长度。与多数研究类似，我们使用802.11 DCF作为MAC协议。

很容易就能看出，相比较普通模型，小世界模型有更广阔的覆盖区域，即使小世界模型采用了比较小的重传概率。此外，小世界模型的跳数还远小于一般模型。伴随而来的是，相变现象也会出现在一般模型中。

2、随机网络案例

随机网络仿真设置与网格网络相类似，不同之处只是将400个节点随机分布到2000*2000米的表面上。选择一个在（1000，1000）附近的节点为广播源。

=NπR2S-1

（1）

無线多跳网络的连通性与平均节点度相关，如等式1所定义，其中N表示节点的数目，S表示区域面积，R为通信半径 。当平均节点度超过了6，ad-hoc网络的连接的概率将达到95%以上。如果上面提到的随机网络中节点使用的通信半径为100m，那么平均节点度只有2.14 ，所以的连接性非常脆弱的。为了减少未连接网络的影响，我们将一般的无线Ad-hoc网络的通信半径扩展到200米。相比之下，在小世界模型中，普通节点使用150米半径和强节点为300米。接下来我们将看到，尽管小世界模型比一般模型使用较短的覆盖距离，但是它的性能却优于后者。在网格网络中使用相同的统计方式。从仿真结果来看，可以总结出，小世界模型比普通模型更优越。

（1）覆盖效益

小世界模型的使用0.2的重传的概率就相当于大约390个节点所能达到的传播覆盖范围，而对于普通模型将需要采用0.6的重传概率。较大重传概率，将会导致更多冲撞和更多的电力成本。

（2）功耗效益

正如我们上面提到的小世界模型中，通信半径为150m的320个节点和半径为300m的80节点。但是在一般模型中的所有节点都将使用200米的通信距离。根据在自由空间的传输公式（见方程2），可以计算出，为获得相同的接收功率Pr，小世界模型与普通模型相比，总发送功率大约可以节省13.75%。

PrPt=GtGrλ4πd2

（2）

（3）多跳效益

小世界模型的跳数明显低于同类中一般模型。一方面，小的跳数意味着更小的传输延迟，这对实时应用是非常重要的，另一方面，小的跳数是相当于更短的路径长度，这也正是小世界曲线图的特性。

应当指出，尽管小世界模型的总消耗功率小于一般的模型，但强节点的功率消耗却是非常大的。为了解决这个问题，可以通过对每个节点装备双收发器，并周期性的随机选择强节点。

四、结论

非均匀概率的洪泛算法，如基本的泛洪技术，是非常简单并易于实现的。它不需要任何控制成本。在模拟仿真中，小世界无线网络模型和非均匀概率洪泛算法的结合，可显示出优异的性能。由于普通节点使用重传的概率非常小，所以它可以显著的减少转播和碰撞量。优异的网络覆盖范围，对纯洪泛算法而言，它是一个非常好的替代者。小跳数可以使小世界模型能够适应低延时的要求，如语音通信。虽然我们不得不消耗更多的收发器和无线信道，但是相对于上述它的价值来说，尤其是对于无线多跳网络中省电这个重要目标来说是非常有价值的。