异类点Ad Hoc网络的一种局部拓扑感知方法

摘要

本发明公开了一种异类点Ad Hoc网络的局部拓扑感知方法，本发明通过发掘异类点Ad Hoc网络中少量高性能节点的优势，配合使用两个发射功率不同且工作频带互不交叠的信道，以高性能节点为簇首，组织成一种松散的簇结构，簇首节点周期性地将簇内拓扑信息广播到其覆盖范围内的所有节点，每个节点接收并学习簇首广播的信息形成自己的拓扑感知区域。本发明最终将每个节点的感知区域半径扩大到HELLO包方式的3倍大小，而将负载控制在与HELLO包方式相当的水平。

说明书

技术领域

本发明是异类点无线移动自组织网络(Ad Hoc网络)中节点对周围局部拓扑信息的一种感知方法，特别涉及异类点Ad Hoc网络的一种局部拓扑感知方法。

背景技术

在Ad Hoc网络中，节点对周围网络的拓扑信息感知是路由协议设计，特别是基于地理位置信息的路由协议设计的基本条件之一。准确而高效的感知周围尽可能大的区域内的网络拓扑信息对于提高路由协议在数据包传递率、传递延时以及控制负载方面的性能具有不可替代的重要意义。目前的拓扑感知技术主要有以下两种。

第一种是最为普遍和基本的“信标”方法，即通过周期性地广播HELLO信息来告知周围节点自己的存在。这种方法存在负载过大且感知拓扑区域小的缺点，而且HELLO信息的广播周期也很难选择，周期大时虽然负载会相对较小，但是对于周围拓扑信息的变化会很不敏感，不能及时获得最准确的拓扑信息。周期小时能够及时获得准确的拓扑信息但是会带来很大的额外开销，这对于带宽资源十分有限的无线网络来说是不能容忍的。近来，有研究人员提出了新的算法，通过自适应地调整HELLO包广播周期来取得负载和拓扑信息准确性之间的平衡，取得了一定的效果，但是仍然不能让人满意，并且这种方法对于扩大拓扑信息的感知区域没有起到任何的作用。

第二种是分簇方法中的拓扑感知技术。为了提高协议的可扩展性，不少学者提出了分簇的方法。若干个节点组成一个簇并选择其中一个节点作为簇首，簇内成员定期按照一定的簇首选择方法向簇首节点注册自己的信息，这样簇首节点可以感知到整个簇内的拓扑信息。此种技术可以提高节点的感知范围，但是负载控制方面却面临着较大的挑战，差的簇首选择算法不但会增加节点的计算量而且带来的通信量会占据大量的带宽，影响正常的数据传输。此外，这种技术还有一个巨大的缺陷就是，感知范围较大的节点仅仅是少量的簇首节点，大量的簇成员节点还必须通过广播HELLO包方式来感知周围拓扑。

发明内容

本发明的目的在于克服上述现有技术不足，提供一种异类点Ad Hoc网络的一种局部拓扑感知方法，在异类点的Ad Hoc网络中，充分利用高性能节点的优势，在保证负载可容忍的情况下，大幅提高每个节点的拓扑信息感知范围，从而为提高路由协议在延时、数据包传递率等方面的性能提供保障。

本发明的技术方案是这样实现的：

异类点Ad Hoc网络的一种局部拓扑感知方法，包括以下步骤：

Step1网络中存在两类节点，一类是通信速率、计算速度、发射功率性能较好的节点，称为B节点，数量较少；另外一类是普通节点，称为G节点，数量较多。

Step2每个节点装备两个发射接口，分别工作在两个互不交叠的信道1和2。信道1上发射接口的发射半径为RG，信道2上发射接口的发射半径为RB，RB＞RG。B节点之间通过信道2通信。G节点之间以及B-G节点之间通过信道1通信，G节点不在信道2上发送任何信息，但是可以接收B节点在信道2上的广播信息。

Step3每个B节点构造一个包含本节点位置信息的初始化CPI包，并通过信道2在RB范围内广播。

Step4G节点接收侦听到的所有初始化CPI包，并选择一个到本节点欧几里德距离最小的B节点作为簇首节点。然后G节点构造一个包含本节点位置信息的GPI包，并通过信道1以k跳洪泛方式(k的取值根据RB与RG的比值确定)发送到簇首B节点。

Step5B节点将收到的GPI包中的信息(源G节点的标识符和位置)保存到一张“簇成员信息表”中，该表包含簇成员标识符和相应位置信息两项内容。

Step6B节点周期性地构造新的CPI包并通过信道2广播，包中包含整个“簇成员信息表”的内容以及本节点的位置信息。

Step7G节点收到CPI包时，将其中的内容全部添加到本地的一个称为“可感知区域拓扑信息表”的表中，该表包含节点标识符和相应位置信息两项内容。

Step8每个G节点周期性地根据收到的CPI包重新选择一个与本G节点有最小欧几里德距离的B节点作为新的簇首，构造GPI包，将自己的位置信息通过信道1以贪婪方式发送到簇首节点。

Step9这样，每个G节点实时维护的“可感知区域拓扑信息表”中保存的节点及其位置信息便构成了本节点可感知区域内的网络拓扑。

本发明通过发掘异类点Ad Hoc网络中高性能节点的优势，利用一种松散的簇结构，局部拓扑感知方法可以大幅提高网络中每个节点的感知区域，感知区域半径达到HELLO包感知技术的3倍左右，但是负载却能控制在与HELLO包感知技术的相当水平。

附图说明

图1为本发明局部拓扑感知方法的工作框图；

图2为G节点感知区域示意图；

图3为簇成员节点和簇首平均距离L_min与B节点度数λ_B的关系图。

下面结合附图对本发明的内容作进一步详细说明。

具体实施方式

参照图1所示，感知方法主要分为初始化和主循环两个部分，详细的工作流程如下描述，其中步骤1到步骤4是初始化过程，步骤5到步骤8是主循环。

Step1网络中存在两类节点，一类是通信速率、计算速度、发射功率性能较好的节点，称为B节点，数量较少；另外一类是普通节点，称为G节点，数量较多。

Step2每个节点装备两个发射接口，分别工作在两个互不交叠的信道1和2。信道1上发射接口的发射半径为RG，信道2上发射接口的发射半径为RB，RB＞RG。B节点之间通过信道2通信。G节点之间以及B-G节点之间通过信道1通信，G节点不在信道2上发送任何信息，但是可以接收B节点在信道2上的广播信息。

Step3每个B节点构造一个包含本节点位置信息的初始化CPI包，并通过信道2在RB范围内广播。

Step4G节点接收侦听到的所有初始化CPI包，并选择一个到本节点欧几里德距离最小的B节点作为簇首节点。然后G节点构造一个包含本节点位置信息的GPI包，并通过信道1以洪泛方式发送到簇首B节点。

Step5B节点将收到的GPI包中的信息保存到一张簇成员信息表中，该表包含簇成员标识符和相应位置信息两项内容。

Step6B节点周期性地构造新的CPI包并通过信道2广播，包中包含整个簇成员信息表的内容以及本节点的位置信息。

Step7G节点收到CPI包时，将其中的内容全部添加到本地的一个称为“可感知区域拓扑信息表”的表中，该表包含节点标识符和相应位置信息两项内容。

Step8每个G节点周期性地根据收到的CPI包重新选择簇首B节点，构造GPI包，将自己的位置信息通过信道1以贪婪方式发送到簇首节点。

参照图2所示，通过执行该感知方法，网络中每个节点都可以形成一个如图中阴影部分所示的感知区域，图中每个B节点周围的圆形阴影为簇内成员G节点的分布范围，整个阴影部分为中心G节点的感知区域。

局部拓扑感知方法中的负载主要来自于G节点向簇首周期性发送的GPI包。而负载的大小则和每个G节点到簇首的平均欧几里德距离L_min有关。通过概率论知识所计算L_min的值为：

$\overline{L_{\min }}={\int }_0^{R_B}{\mathrm{rf}}_{L_{\min }}\left(r\right)\mathrm{dr}={\int }_0^{R_B}\frac{{2\lambda }_B{r}^2}{R_B^2}{e}^{-\frac{{\lambda }_B{r}^2}{R_B^2}}\mathrm{dr}$

其中λ_B为B节点的邻居B节点数量，λ_G为G节点的邻居G节点数量。

参照图3所示，横坐标为B节点的邻居B节点数量λ_B，纵坐标为L_min与信道2发射半径RB之间的比值，坐标平面中的小圆点表示该比值随λ_B的变化趋势。该趋势表明G节点和自己簇首的平均距离L_min非常短，也就是说G节点向簇首发送的GPI包只需经过很小的跳数。特别当$\frac{R_B}{R_G}<3,$λ_B＞7.18时(这种条件很容易满足)，在统计意义下，G节点到簇首平均路由长度只有一跳。因此G节点向簇首发送的GPI包仅仅相当于一跳，而B节点发送的CPI包也仅有一跳，所以该感知方法与邻居感知的HELLO包方式造成的负载几近相当。

此外，本发明通过使用OPNET10.0网络仿真软件在一个1000m×1000m的区域内测算一个G节点的感知区域大小。取RG＝100m，RB＝300m，B节点数量为30个，G节点数量为250个，所有节点随机分布。在网络中任取一个G节点作为研究对象，通过10次仿真得到的平均结果，该G节点可以感知到的最远平均距离为318.6m，而HELLO包方式感知区域的最远距离仅为100m。