一种应用于ad hoc网络的基于节点类型的群首选举方法

摘要

一种应用于ad hoc网络的基于节点类型的群首选举方法，考虑节点的类型，即节点所属的行政单位，并结合相对移动性快慢和距离远近这两个因素，提出了一个综合性的群首衡量指标：稳定性系数S，利用该系数进行群首的选择以及分群的形成。由本算法构成的分群网络，由于同一个群内的节点又尽可能的属于同一个行政单位，因而在各个单位各自离开从而导致网络分割的时候，会降低群首更迭的次数，提高网络的稳定性。能够在网络进行分割的时候有效的减少群首的更迭次数，达到稳定网络的目的。

说明书

技术领域

本发明涉及一种应用于ad hoc网络的基于节点类型的群首选举方法。本发明适用于无线ad hoc分级结构网络应用领域。

背景技术

Ad hoc网络，又叫无线自组网，是由一组带有无线通信收发装置的移动终端节点组成的一个多跳的临时性无中心网络，可以在任何时刻、任何地点快速搭建，并且不需要固定设施的支持。

Ad hoc网络一般有两种结构：平面结构和分级结构。平面结构的网络比较简单，网络中所有节点的功能和地位相同，不需任何结构维护过程，缺点是网络规模受限，可扩充性差，随着网络规模的扩大和节点移动性的增强，节点在维护路由信息方面的控制开销也越来越大，继而导致了网络时延的增大和网络的拥塞。分群是克服以上缺点的常用方式，通过将网络中的节点划分为若干个群，每个群中选出一个群首，构成高一层次的虚拟骨干网，以实现网络的层次化，从而提高网络性能。

群首选举算法方法作为分群算法的重要一部分负责在所有节点中挑选合适的节点做群首，构成高一层的虚拟骨干网，因而群首选举算法方法的优劣将直接影响网络结构的稳定性，进而影响网络的性能。

目前已有的Ad hoc分群算法主要有以下几类：

1.最小ID分群算法

通常情况下，给网络中每个节点分配唯一的ID号。最小ID分群算法是指节点与相邻节点交换所听到的节点ID号，并且选择ID号最小的节点作为它的群首，选择结果就是把网络节点分成群首、网关或普通节点。

2.最大连接度分群算法

最大连接度分群算法的目标就是尽量减少群的数目。节点之间通过交互控制消息知道其邻居节点的数目，该节点和其相邻节点中具有最大度的节点被选为群首，当度数相同时则选择ID最小的节点作为群首，群首的一跳邻居节点则成为该群首的普通成员节点，反复进行以上过程，直到所有节点都加入某个群。

3.节点加权分群算法

节点加权分群算法基于节点适合作为群首的程度来为每个节点分配相应的权值，相邻节点中具有最高权值的节点成为群首，当权值相同时选择ID号最小的节点作为群首。权值分配可以考虑邻居节点多个因素，例如：收到的主机信号强度；信号质量；流量负载；连接度，即邻居节点个数等等。以上因素可根据需要同时选取，从而构成节点的向量权。

分群算法是和它的应用环境紧密相关的，不同的环境下可采取不同的分群算法与之相适应，从而更好地提高网络性能。在Ad hoc应用环境中，灾难救助是一种典型的应用，即：在同一区域内有多个不同的行政单位实施不同的行为活动，例如，消防队员、救护人员、士兵等可能会前往同一区域内执行各自的救助任务，任务完成后又各自离去。这样的应用环境中如果采用传统的分群算法，群首的选择可能是随机的，当节点从某一区域离开时，通常是按照行政单位统一行动的，这种随机选择的群首就可能频繁更迭，甚至导致网络的分割，引起网络性能急剧下降，本发明方法就是在节点加权分群算法基础上考虑节点类型(即节点所属行政单位)来解决此类问题的。

发明内容

为了克服现有的分群算法在某些特定环境下群首频繁更迭的不足，本发明提供一种应用于ad hoc网络的基于节点类型的群首选举方法，把节点的类型(即节点所属的行政单位)这个因素考虑进来，结合相对移动性快慢和距离远近这两个因素，提出了一个综合性的衡量一个节点是否适合做群首的指标——稳定性系数S，利用该系数进行群首的选择以及分群的形成。从而可以尽可能的使稳定性最好的节点作为群首，解决群首频繁更迭的问题。

本发明解决其技术问题所采用的技术方案是：

本发明提出了一种应用于ad hoc网络的基于节点类型的群首选举方法，也是基于节点类型和相对移动性的ad hoc网络分群方法。

本发明的基于节点类型和相对移动性的ad hoc网络分群算法假定每个节点可以随时获得自己的位置信息(例如配置GPS或其它的定位装置)。本方法包括如下几个过程步骤：

步骤1、节点通过HELLO消息周期性的广播自己的位置信息，并利用收到的HELLO消息在邻居列表中维护邻居的位置信息；

步骤2、利用各个邻居的位置信息和节点的类型计算相对移动性M，平均距离和D_SUM，进而计算稳定性系数S；

步骤3、通过比较S的大小来确定群首，完成分群。

本发明的有益效果是，由本算法构成的分群网络，由于同一个的群内的节点又尽可能的属于同一个行政单位，因而在各个单位各自离开从而导致网络分割的时候，会降低群首更迭的次数，提高网络的稳定性。

附图说明

下面结合附图和实施例对本发明进一步说明。

图1、程序流程图。

具体实施方式

步骤1、广播位置信息，建立邻居列表；

每个节点周期性的向邻居节点广播HELLO消息，HELLO的包格式如下：

  ID  IP  Status  P  S

各字段含义如下：

ID：全网唯一的节点名称；

IP：全网唯一的IP地址，具备<子网号主机号>这样的形式，用于路由的寻址及节点类型的区分；

Status：节点的状态信息，其值为0表示：该节点未加入任何群；

                        为1表示：该节点是群内的普通节点；

                        为2表示：该节点是网关节点；

                        为3表示：该节点是群首节点；

P：节点的位置信息；

S：节点的稳定性系数。

每个节点通过从邻居节点收到的HELLO消息建立一个邻居列表，格式如下(假设节点A的邻居节点有B1，B2，...。)：

  邻居ID  邻居IP地址  邻居状态  与邻居的距离  B1  *** *** *** ***     .   .   .  0  D_A，B1¹  D_A，B1²...... D_A，B1^N  B2  *** *** *** ***     .   .   .  0  D_A，B2¹  D_A，B2²...... D_A，B2^N........................

该邻居列表根据收到的HELLO消息周期性的更新，以上各字段的含义为：

邻居ID：表示邻居的名称；

邻居IP地址：具有<子网号，主机号>这样的形式，子网号表示该节点在逻辑上或是行政上的归属，子网号相同则表示属于同一个逻辑单位，比如救援组，消防组等。

邻居状态：在ad hoc网络进行初始化的时候，邻居状态都为0值，分群完成之后，邻居状态根据真实情况可以为0，1，2或3；

邻居位置：节点按照链表的形式保存邻居随时间变化的位置信息，并根据FIFO的原则对链表进行更新，用于群首选举时稳定系数S的计算。

步骤2、由相对移动性M，平均距离和D_SUM，进而计算稳定性系数S；

首先计算相对移动性M，相对移动性M表示某节点的邻居节点相对与该节点的移动性快慢，M越小表示邻居节点的相对移动性越低，从而该节点更适合做群首。计算步骤如下：(以节点A为例)

①计算A节点与邻居节点(B1)之间距离的平均值μ，N可以人为设定统计次数：

$>>\mu >=>>(>>D>>A>,>B>1>>1>>+>>D>>A>,>B>1>>2>>+>\Lambda >+>>D>>A>,>B>1>>N>>)>>/>N>->->->>(>1>)>>>s>$

②计算A节点与邻居节点(B1)之间距离变化的波动大小，即方差VD_A，B1：

$>>>VD>>A>,>B>1>>>=>[>>D>>A>,>B>1>>1>>->\mu >>)>2>>+>>>(>>D>>A>,>B>1>>2>>->\mu >)>>2>>\Lambda >+>>>(>>D>>A>,>B>1>>N>>->\mu >)>>2>>]>/>N>->->->>(>2>)>>>s>$

③计算A节点与每一个邻居之间距离的方差，并在加权后进行均值运算得到相对移动性M_A：

M_A＝(ω₁VD_A，B1+ω₂VD_A，B2+Λ+ω_mVD_A，Bm)/m                (3)

其中加权系数ω的确定规则如下：

根据IP地址的子网号是否相同，节点A判断邻居节点是否与自己属于同一个逻辑子网，如果是则ω值为λ(0＜λ＜1，可根据需要进行调整)，如果不是则ω为1。

然后，计算平均距离和D_SUM，D_SUM表示节点与它的各个邻居节点的距离之和的平均值，D_SUM越小表示邻居节点离它越近，从而该节点更适合做群首。计算时利用存储在邻居列表里最新的位置信息：

$>>>D>>SUM>->A>>>=>>(>>\omega >1>>>D>>A>,>B>1>>N>>+>>\omega >2>>>D>>A>,>B>2>>N>>+>\Lambda >+>>\omega >m>>>D>>A>,>Bm>>N>>)>>/>m>->->->>(>4>)>>>s>$

其中加权系数ω的确定规则与上相同。

最后利用已经计算出的M和D_SUM来计算稳定性系数S_A，该系数是用来衡量一个节点是否适合做群首的标准：

S_A＝α₁M+α₂D_SUM-A(α₁+α₂＝1  0＜α₁，α₂＜1)     (5)

步骤3、通过比较S的大小来确定群首，完成分群；

每一个节点都将计算这样的稳定系数并通过HELLO消息向邻居节点进行广播，节点A通过将邻居的稳定系数和自己的稳定系数进行比较来选举群首，如果A发现自己的稳定系数比邻居的稳定系数都要低，则A声明自己为群首，当两个节点稳定系数相同且最低时，选择ID号最小的节点作为群首，群首的一跳邻居节点则成为该群首的普通成员节点，否则A等待一个来自群首的HELLO消息并加入以该节点为群首的群，反复进行以上过程，直到所有节点都加入某个群，分群完成。