2008年7月系统工程理论与实践第7期 文章编号:100026788(2008) 0720119206
车用自组织网络分层优化策略研究
刘鸿飞1,2, 黄席樾, 李丽君, 张仔兵132
(11重庆大学自动化学院, 重庆400044;21重庆通信学院, 重庆400035;
31重庆工学院数理学院, 重庆400050)
摘要: 车用自组网中, 有效的分层协议可以增强网络逻辑拓扑结构的稳定性, 减小通信中继花费. 提出
利用相邻车辆节点之间的稳定和非稳定邻居关系, 构建网络分层结构, 同时利用优化策略选择网络中的
最优簇头集合, 在保证网络具有良好负载均衡度的基础上, 提高网络层次结构的稳定性. 仿真数据表明,
算法在分层结构的稳定性以及负载均衡度等方面均优于其他算法.
关键词: 车用自组网; 分层协议; 集合理论; 负载均衡
中图分类号: TP393101 文献标志码: A
Study on hierarchy and optimization orks
LI U H ong 2fei 1,2, X , , Z i 2bing 12
(11Chongqing University , , 21Chongqing C ommunication C ollege , Chongqing 400035,
) China ;31of T , and Sciences , Chongqing 400050, China
Abstract : vehicular ad hoc netw orks , stable clustering methods could reduce the netw orks of communication relay
and provide for a m ore efficient hierarchical netw ork topology. This paper proposes weight 2based stability clustering
alg orithm , in which stability neighbor sets are considered as a vehicular node weighted factor and an index of clustering
re 2affiliation. Meanwhile , to ensure netw orks load 2balancing performance , by applying optimized alg orithm , an
optimized clusterhead (CH ) sets is obtained. S imulation experiments are conducted to evaluate the performance of our
alg orithm in terms of the number of CH , re 2affiliation frequency and dominant set updates. The results show that our
alg orithm performs better than the existing alg orithms.
K ey w ords : vehicular ad hoc netw orks ; hierarchy ; sets theory ; load 2balancing
1 引言
车用自组网作为移动自组网络模型在智能交通信息系统中的重要应用, 可以满足驾乘人员获取实时道路交通信息和其它应用信息的需求. 在预防交通事故、减轻交通拥堵、实施紧急援救以及为驾乘人员提供多种服务信息方面具有其它无线或有线网络不可替代的优势. 虽然两种网络都具有自组性、多跳性、无基础设施要求等特点, 但是, 由于车用自组网络拓扑结构与道路布局、建筑物遮挡、车辆节点运动规律、天气状况等因素密切相关, 因此迫切需要研究适应于车用自组网络的各种协议.
移动自组网中, 由于物理拓扑结构中节点数量巨大, 运动的随机性强, 基于物理拓扑结构的各种数据
[1]分发协议普遍存在适应性差、性能低下等问题. 因此移动自组织网络中的各种协议一般都基于分层思想
进行研究分析. 基于簇的层次结构能够优化网络资源、提高信道利用率、减少路由维护代价以及提高应用的可扩展性、鲁棒性, 非常适合于规模日益庞大的车用自组网络. 但是, 许多现有的分层思想都是基于移动自组网络, 针对车用自组网络的分层研究还没有进一步展开.
网络分层研究实质是解决如何将网络中的节点分成各自相对独立的节点簇. 本文根据车用自组网络收稿日期:2007202225
资助项目:国家自然科学基金(60402035,60573001) ; 重庆大学研究生科技创新基金(200701Y 1A0030189)
作者简介:刘鸿飞(1974-) , 男, 四川泸州人, 博士生, 主要从事计算机网络体系结构方面的研究; 黄席樾(1943-) , 男, 重庆人, 教授, 博士, 博士生导师, 主要从事智能控制, 智能交通等方面的研究; 李丽君(1973-) , 女, 重庆人, 硕士, 讲师, 主要从事信息技术与网络方面的研究.
[2～8]
的基本特征以及移动自组网络中多种网络分层策略的优缺点, 提出基于权重的分布式稳定分簇算法, 并在此基础上, 利用优化性能突出的模拟退火机制对分层策略进行优化, 保证网络在具有良好负载均衡度基础上, 增强层次结构稳定性. 同时, 考虑到道路上车辆节点运动规律的特殊性和车辆节点之间运动的关联性, 提出自适应性强的簇重构策略, 以增强分层网络拓扑的稳定性.
2 相关工作
移动自组网络中, 分簇问题可以归结为寻找一个最大独立集问题, 而找一个最大独立集是著名的NP 2hard 问题[3], 因此, 大多数移动自组网络簇生成算法都采用了启发式算法进行簇划分. 根据簇首选择原则
[2]的不同, 可分为最小标识优先
性[7]、最大连接度优先以及最大权值优先算法等. 在最小标识优先算法[3][4]中,I D 较小的节点成为簇首的可能性远高于其他节点, 因此算法在性能有限的移动自组网络中缺乏公平. 而最大连接度优先算法仅以连接度作为启发选择簇首节点, 因此负载均衡度较差, 没有综合考虑网络在稳定性、扩展性等方面的需求. 基于权重的分簇算法综合考虑了系统的节点度, 移动性等多种增强簇结构稳定性因素, 可以保证网络具有更可靠的性能, 是较理想的分簇策略.
基于节点权重的分簇策略以文献[4～8]为代表, , 指示它适合充当簇头的程度, 例如:W =w 1a +w 2b +w 3c +w 4d +ke , a , c 表示节点的传输功率, d e , 参数w 1、w 2、w 3、w 4为权重因子. 文献[6], 网络的稳定性和负载均衡度都得到了较大提高.
但是, “节点运动是随机、互不相关”的假设设计的, 在真实场景中, 特别是车用自组网络中, 车辆节点运动一般都具有较强的组移动特征. 与节点的随机移动相比, 组移动具有几个鲜明的特点:①组内节点运动方式高度相似, 而不同组的运动方式可能差别很大; ②节点的运动速度与方向随机性小; ③在同一个组内, 通常节点密度较大, 相对移动性较小; ④在双向车道上, 相向运动的邻居节点之间相互联系是临时的, 对簇的稳定性影响较大;
针对车用自组网络中节点组内运动状态的关联性, 提出了考虑负载均衡性的W UF
(Weighted utility function ) 算法, 与传统的分簇算法相比, 该算法在网络的负载均衡性和稳定性等方面有较大改善. 但是由于没有考虑稳定邻居以及相向运动节点组之间关联的瞬时性, 因此, 该算法的稳定性有待Peng Fan [9]改进.
针对车用自组网络中节点以及节点组运动规律的主要特征, 充分利用基于权重的簇划分策略的优点, 在文献[7～9]的基础上, 提出了基于权重的稳定性分簇算法, 并且采用模拟退火算法进行优化, 以保证网络在良好负载均衡度条件下, 减少簇重构率, 提高网络分层结构的稳定性.
3 网络分层策略
311 模拟退火优化思想
模拟退火算法(Simulated Annealing ,S A ) [10]是基于M onteCarlo 迭代求解策略的一种随机寻优算法. 通过模拟物理退火过程,S A 由某一较高初温开始, 利用具有概率突跳特性的Metropolis 抽样策略在解空间中进行随机搜索, 伴随温度的不断下降重复抽样过程, 最终得到问题的全局最优解.
[11]模拟退火算法具有4个特点,1) 每个状态都可能到达;2) 在任意给定温度下, 分布相当稳定;3) 当温
度渐近到零度时, 模拟退火收敛到全局最优解;4) 算法的收敛不依赖于初始条件. 与禁忌搜索算法相比, 模拟退火最大的优点在于从理论上保证能够收敛到全局最优解. 因此, 为了避免陷入局部优化, 从而提高分层结构的稳定性和负载均衡性, 我们将模拟退火引入车用自组网络分层研究中.
312 问题描述
假设车用自组网络中所有节点采用全向天线, 节点的传输能力相同, 且所有链路均为双向链路, 则网络用图G (V , E ) 表示, 其中V 表示网络节点集合. {i , j }∈E 表示节点i 、j 间存在的通信链路. 算法中使用
的符号与定义如下:
W i :节点i 的权重值;
N (i ) :节点i 的邻居节点I D 集合;
‖N (i ) ‖:节点i 的邻居节点数;
M :单个簇首节点能服务的最大成员数;
M (i ) :簇成员节点集合, 初始值为空. 仅当i 为簇首节点时, 才更新该集合;
P :一定规则选举出的簇头节点构成集合, 初始值为空集;
H :网络中被选中作为簇头以及这些簇的成员集合, 初始值为空集;
Q :网络中剩余节点的集合, 记为Q =N -H .
定义1 对于给定的网络拓扑图G (V , E ) , 由状态产生函数获得网络中簇头的集合X 为解空间的一状态, 所有可能的簇头集合构成解空间V (X ) , 有X ∈V (X ) . 任意簇头集合的状态产生函数表述如下:
1) 判断集合Q 是否为空集, 为空则算法结束;
2) 从Q 中随机选取一个节点i , 如果满足‖N (i ) ‖≤M , 则有:P =P +{i }; Q =Q -M (i ) -{i }; 如果‖N (i ) ‖>M , 则返回1) ;
定义2 称F (X ) =-ΣW i (X ) 为解X 的能量函数, .
有最小能量值簇头集合. 33, F (X ) ≤F (X ) , 使得网络在保持较好负载均衡度的
基础上, .
313 节点权重分析
在移动自组网络中, 基于权重的分簇算法的基本思想是根据网络中节点的运动变化状态, 节点的邻居节点数以及节点的剩余能量等因数设计节点的权重值. 在许多文献[4～7]中, 均采用平均速度来描述节点的运动, 这是符合M ANET 网络中节点运动的独立性原则, 但是在车用自组网络中, 高速运动节点之间的位置相互关联, 特别是相邻车辆之间的运动更是紧密相关. 因此, 采用平均速度不能有效地描述车辆节点运动速度的变化情况, 并且, 大多数文献中对于平均速度的计算需要依靠其他节点的位置信息, 因此算法的可扩展性不强, 根据分布式原则,SWC A 根据单一节点的速度连续变化信息获得节点的运动改变情况, 从而为更加准确地描述节点运动提供保证.
定义3 在任意的时间段[t 1, t 2]内(T =t 2-t 1) , 有均匀的k 个采样点, 采样时间间隔为Δt =T Πk , 每
Δt 时刻记录自身的运动速度大小和方向(其中n ∈[0, k ]) , 邻居节点数以及邻居节点标识个节点在t =n
Δt 的速度大小为v (i , t ) , 则在T 时间段内速度大小的平均值和方差为分别(I D ) . 设网络中节点i 在t =n
为v (i , T ) , δ(i , T ) .
根据道路上车辆节点组的运动特征, 双向车道上相邻节点之间的邻居关系主要有两种. 相向行驶的车辆节点之间可能是邻居关系, 可以构建在同一个簇内, 但是这种临时邻居关系会削弱簇的稳定性, 相反, 同向行驶的相邻节点之间是稳定的邻居关系, 对簇的稳定性起关键作用. 因此提出节点稳定邻居集合(Stability Neighbor Sets ,S NS ) 作为网络拓扑结构中最重要的稳定性指标, 并定义如下.
定义4 在t 1和t 2时刻, 节点i 的邻居节点I D 的集合分别记为N (i , t 1) , N (i , t 2) , 则邻居数分别记为‖N (i , t 1) ‖, ‖N (i , t 2) ‖, 稳定邻居集合记为N (i , T ) =N (i , t 1) ∩N (i , t 2) , 稳定邻居数记为‖N (i , T ) ‖.
则节点i 的权重归一化模型可以设为:
-N (i , t ) Π2() 2) +w 3W i =w 1+w 2(1-e 1+δ(i , T ) ‖N (i , t 1) ‖
3
且
314 基于模拟退火的分簇初始化i =1∑w 1=1.
在车用自组网络中, 由于节点组在道路上的分割性, 节点的邻居数量差别较大, 因此在进行网络分层时, 必须考虑各个簇头的负载均衡性, 以保证节点的负载、信道的分配能处于均衡状态, 以提高网络的整体性能. 同时, 为了保证网络的稳定性, 在选取簇头集合时应该考虑节点权重值对整体性能的影响, 因此, 设计了多次迭代的簇头选举算法.
模拟退火算法中使用的符号与定义如下:
t 0:算法开始时的初始温度值;
T 0:算法结束时的终止温度值;
R :算法在同一温度下的迭代次数;
λ:温度改变系数, 且0
H :目标函数值在某一区间内保持连续稳定的次数;
ε:状态函数改变的某一极小量;
基于上述模拟退火的基本思想, 对网络分层优化问题进行处理, 算法步骤如下:
①设置控制参数. 初始温度t 0, 温度改变系数λ, 迭代次数r , 成功迭代次数h ;
②随机产生初始状态X =X 0, 并令k =0, r =0, h =0;
③构造X 的邻域解X j , 有X j ∈V (X ) , 且r =r +④如果ΔF =F (X j ) -F (X ) 0, j ⑤. 否则转步骤⑥;
⑤如果|ΔF |+1⑦, , ⑧;
⑥,exp [-(F (X j ) -F (X ) ) Πt k ]}≥random[0,1], X =X j , 转步骤⑧; 否则X =X , ;
⑦如果h ≥H , 转步骤⑨, 否则转步骤⑧;
⑧如果r ≥R , 转步骤⑨, 否则转步骤③;
⑨温度降低. k =k +1, t k +1=λt k , 且r =0, h =0, 并转步骤⑩;
⑩算法终止规则. 如果温度t k ≥T 0, 输出状态解X , 并且算法终止; 否则返回步骤③.
315 簇维护
簇的维护主要包括节点的加入或者离开, 以及簇的分离和合并, 为保持簇首生存时间尽可能长, 故给出如下的规则:
规则1 当一个簇i 的非簇首节点移入另一个簇j 时, 两个簇首均不改变;
规则2 当一个非簇首节点移出当前簇, 没有进入任何已存在的簇时, 它成为一个新的簇首, 形成一个新簇;
规则3 当簇首CH (i ) 从i 移到簇j , 判断两个簇首运动的方向是否一致, 如果为同方向, 则CH (i ) 与CH (j ) 竞争当前簇首, 根据权值大簇首原则, 当前的CH (i ) 或CH (j ) 将放弃它的簇首;
规则4 当簇首CH (i ) 从簇i 移到簇j , 判断两个簇首运动的方向如果不一致, 则两个簇头开始记录
) , T r Π两个簇头作为邻居的连续时间, 当其中任一个簇头记录的T H 满足条件T H ≥max{T r Πv (i , T ′v (j ,
) }时, 两个簇按规则3合并, 否则不合并. 其中T r 为节点信号的传输距离. v (i , T ′) 和v (j , T ′) 分别表示T ′
簇头前一段时间内的平均速率.
由于双向车道上相向而行的簇头之间是一种典型的不稳定邻居关系, 如果按照普通簇合并规则, 将会出现两个簇刚合并后即迅速分离, 直接影响网络层次结构的稳定性. 通过规则4, 可以减轻由于双向簇头临时偶遇给网络稳定性带来的影响.
4 性能分析
本节利用S UM O 提供的车用自组网络拓扑产生器, 同时扩展网络仿真软件NS2相应底层代码实现对算法的支持. 主要研究SWC A 的平均簇数、单位时间内簇头更新次数以及网络的负载均衡因子(LAB )
[9][5]等指标性能, 并且与W UF 的相应指标进行全面比较. 其中网络负载均衡度定义如下:
[12][11]
LB F =∑(x
i i -u ) 2, u
=. n c
n c 为簇头节点的数量, x i 为簇头节点i 的成员数, u 为簇头的平均邻居节点数量, N 为网络中节点总数.
为了简单起见, 还采用了文献[12]提出的城市道路模型, 如图1所示.
每段道路的长度均为200m , 车辆节点在每个道路交叉口的运动方向选择有
两种(直行、左转、右转) 和(直行、转向) , 概率分别为(015、0125、0125) 和
(015、015) . 节点的平均速度在5m Πs 到30m Πs 之间, 节点数为120个. 理想的
簇成员数M =10, 加权系数w 1、w 2、w 3分别为013,013,014. 其他物理层参
数以及模拟退火优化策略中的相关参数设置均与文献[7]一致. 图1 城市道路拓扑图
在节点的平均速度为15m Πs 的情况下, 图2和3表示簇头的平均数和
簇更新率随着节点信号传输范围改变而变化的趋势. 在平均簇头数方面, 虽然SWC A 算法的簇头数量要略高于W UF , 但是在簇的重构性能上, 由于SWC A 考虑了稳定邻居集作为节点权重的重要参数, 同时也考虑了双向车道上簇的重构条件, 因此提高了簇的稳定性
.
图2 平均簇头数vs 传输范围
图3 簇头改变的平均数vs 传输范围
图4描述当节点信号传输范围在250m 时, 簇重构率随着节点速度变化的情况. 显然双向车道上相向运动簇头节点之间的临时邻居关系造成簇的频繁合并和分离, 并没有对SWC A 算法造成较大的影响, 因此在W UF 稳定性能急剧恶化时,SWC A 保持了较高的稳定性
.
图4 单位时间内簇头的平均改变值vs 节点速率
图5 负载均衡度比较
图5表示网络负载均衡度随着仿真时间增加时的性能图. 虽然SWC A 算法中设置了单个节点的最大服务成员数为10, 但是网络中节点的密度不大, 因此对算法的负载均衡度影响不大. 而W UF 在簇的重构上没有考虑不同方向运动节点之间的邻居稳定关系, 因此在双向车道上相向运动的邻居节点之间以及在道路交叉口上运动的邻居节点之间的复杂和临时邻居关系, 对W UF 簇重构后的负载均衡性产生较大的影响, 导致W UF 中各个簇中的成员数之间差异性比较明显. 而SWC A 由于只对满足一定条件的同向运动的簇进行重构, 簇之间的差异性较小, 因此W UF 负载均衡度在总体性能上低于SWC A , 加重了某些簇头的负担, 不利于其他协议的构建.
124系统工程理论与实践2008年7月5 结论
车用自组网作为特殊的移动自组网络, 节点组运动规律性, 道路的双向性以及道路交叉口对网络拓扑结构分层起着关键作用. 根据相邻节点运动规律的相似性, 提出了稳定邻居集概念, 对节点的权重进行重定义, 并基于模拟退火机制对车用自组网络分层机制进行优化, 构造出满足网络需求的初始簇头集合. 并且针对不同邻居关系对簇重构的影响, 提出了新的簇重构策略. 仿真性能分析表明,SWC A 在网络的稳定性和负载的均衡性上均明显优于传统的基于权重的分簇算法. 虽然在簇的优化过程中该算法需要获得网络的整个状态, 算法的扩展性不强. 但是, 通过借鉴该策略, 可以为全面研究车用自组网络分层结构的分布式分簇策略提供有效的解决途径.
下一阶段的工作主要是根据当前的研究结论设计出更加有效、具有较强可扩展性的分布式分簇策略, 并且采用与实际道路拓扑结构更接近的仿真实验环境进行分析验证, 进一步优化分簇算法在复杂道路拓扑结构下的性能.
参考文献:
[1] Y ousefi S , M ousavi M S , Fathy M. Vehicular ad hoc netw orks () :and ΠΠProceedings of the
6th International C on ference on ITS T elecommunication Proceedings , , , :[2] E phremides A , Wieselthier J E , Baker D J. A design hopping signaling
[C]ΠΠProceedings of IEEE , 1987-[3] Mario G, Jack , 2ork[J].AC M 2Balter Journal of Wireless Netw orks , 1995,
(3) :255-[4] Basagni S. clustering for ad hoc netw orks [C]ΠΠProceedings of the Parallel Architectures , Alg orithms and Netw orks.
Perth , June , 1999:310-315.
[5] Chatterjee M , Das S K, Turgut D. An on 2demand weighted clustering alg orithm (WC A ) for ad hoc netw orks[C]ΠΠProceedings of
the IEEE G lobecom 2000, San Francisco , 2000, (11) :1697-1701.
[6] Er I I , Seah W K G. Clustering overhead and convergence time analysis of the m obility 2based multi 2hop clustering alg orithm for
m obile ad hoc netw orks[C]ΠΠProceedings of the Parallel and Distributed Systems , 2005, S ingapore , 2005, (02) :130-134.
[7] Turgut D , Turgut B , E lmasri R , et al. Optimizing clustering alg orithm in m obile ad hoc netw orks using simulated annealing[C]ΠΠ
Proceedings of the Wireless C ommunications and Netw orking , Orlando , F L , US A , 2003:1492-1497.
[8] Chatterjee M , Das S K, Turgut D. WC A :A weighted clustering alg orithm for m obile ad hoc netw orks[J].Journal of Clustering
C omputing (S pecial Issue on M obile Ad hoc Netw orks ) , 2002, (5) :193-204.
[9] Peng F , Haran J , Dillenburg J , et al. T raffic m odel for clustering alg orithms in vehicular ad 2hoc netw orks[C]ΠΠProceedings of the
IEEE C onsumer C ommunications and Netw orking C on ference , 2006:168-172.
[10] 王凌. 智能优化算法及其应用[M].北京:清华大学出版社,2001.
Wang L. Intelligent Optimization Alg orithms with Applications[M].Beijing :TsinghuaUniversity Press , 2001.
[11] 崔勇, 吴建平, 徐恪. 基于模拟退火的服务质量路由算法[J].软件学报,2003,14(5) :877-884.
Cui Y, Wu J P , Xu K. A Q oS routing alg orithm by applying simulated annealing[J].Journal of S oftware , 2003, 14(5) :877-884.
[12] K arnadi F K, M o Z H , Lan K C. Rapid generation of realistic simulation for VANET[C]ΠΠProcessing of the IEEE 2007Wireless
C ommunications and Netw orking C on ference , 2007:2506-2511.
[13] The ns 22Netw ork S imulator. http :ΠΠw w w. isi. edu Πnsnam Πns Π.
[14] Jaap S , Bechler M , W olf L. Evaluation of routing protocols for vehicular ad hoc netw orks in city traffic scenarios http Π:Πw w w. ibr.
cs. tu 2bs. de Πusers Πbechler ΠmyPublications Πmarc JaBW05. pd f.
[15] Helbing D , Hennecke A , Shvets ov V , T reiber M. Micro 2and Macro 2simulation of Freeway T raffic[M].Mathematical and C omputer
M odeling , 2002, (35) :517-547.
2008年7月系统工程理论与实践第7期 文章编号:100026788(2008) 0720119206
车用自组织网络分层优化策略研究
刘鸿飞1,2, 黄席樾, 李丽君, 张仔兵132
(11重庆大学自动化学院, 重庆400044;21重庆通信学院, 重庆400035;
31重庆工学院数理学院, 重庆400050)
摘要: 车用自组网中, 有效的分层协议可以增强网络逻辑拓扑结构的稳定性, 减小通信中继花费. 提出
利用相邻车辆节点之间的稳定和非稳定邻居关系, 构建网络分层结构, 同时利用优化策略选择网络中的
最优簇头集合, 在保证网络具有良好负载均衡度的基础上, 提高网络层次结构的稳定性. 仿真数据表明,
算法在分层结构的稳定性以及负载均衡度等方面均优于其他算法.
关键词: 车用自组网; 分层协议; 集合理论; 负载均衡
中图分类号: TP393101 文献标志码: A
Study on hierarchy and optimization orks
LI U H ong 2fei 1,2, X , , Z i 2bing 12
(11Chongqing University , , 21Chongqing C ommunication C ollege , Chongqing 400035,
) China ;31of T , and Sciences , Chongqing 400050, China
Abstract : vehicular ad hoc netw orks , stable clustering methods could reduce the netw orks of communication relay
and provide for a m ore efficient hierarchical netw ork topology. This paper proposes weight 2based stability clustering
alg orithm , in which stability neighbor sets are considered as a vehicular node weighted factor and an index of clustering
re 2affiliation. Meanwhile , to ensure netw orks load 2balancing performance , by applying optimized alg orithm , an
optimized clusterhead (CH ) sets is obtained. S imulation experiments are conducted to evaluate the performance of our
alg orithm in terms of the number of CH , re 2affiliation frequency and dominant set updates. The results show that our
alg orithm performs better than the existing alg orithms.
K ey w ords : vehicular ad hoc netw orks ; hierarchy ; sets theory ; load 2balancing
1 引言
车用自组网作为移动自组网络模型在智能交通信息系统中的重要应用, 可以满足驾乘人员获取实时道路交通信息和其它应用信息的需求. 在预防交通事故、减轻交通拥堵、实施紧急援救以及为驾乘人员提供多种服务信息方面具有其它无线或有线网络不可替代的优势. 虽然两种网络都具有自组性、多跳性、无基础设施要求等特点, 但是, 由于车用自组网络拓扑结构与道路布局、建筑物遮挡、车辆节点运动规律、天气状况等因素密切相关, 因此迫切需要研究适应于车用自组网络的各种协议.
移动自组网中, 由于物理拓扑结构中节点数量巨大, 运动的随机性强, 基于物理拓扑结构的各种数据
[1]分发协议普遍存在适应性差、性能低下等问题. 因此移动自组织网络中的各种协议一般都基于分层思想
进行研究分析. 基于簇的层次结构能够优化网络资源、提高信道利用率、减少路由维护代价以及提高应用的可扩展性、鲁棒性, 非常适合于规模日益庞大的车用自组网络. 但是, 许多现有的分层思想都是基于移动自组网络, 针对车用自组网络的分层研究还没有进一步展开.
网络分层研究实质是解决如何将网络中的节点分成各自相对独立的节点簇. 本文根据车用自组网络收稿日期:2007202225
资助项目:国家自然科学基金(60402035,60573001) ; 重庆大学研究生科技创新基金(200701Y 1A0030189)
作者简介:刘鸿飞(1974-) , 男, 四川泸州人, 博士生, 主要从事计算机网络体系结构方面的研究; 黄席樾(1943-) , 男, 重庆人, 教授, 博士, 博士生导师, 主要从事智能控制, 智能交通等方面的研究; 李丽君(1973-) , 女, 重庆人, 硕士, 讲师, 主要从事信息技术与网络方面的研究.
[2～8]
的基本特征以及移动自组网络中多种网络分层策略的优缺点, 提出基于权重的分布式稳定分簇算法, 并在此基础上, 利用优化性能突出的模拟退火机制对分层策略进行优化, 保证网络在具有良好负载均衡度基础上, 增强层次结构稳定性. 同时, 考虑到道路上车辆节点运动规律的特殊性和车辆节点之间运动的关联性, 提出自适应性强的簇重构策略, 以增强分层网络拓扑的稳定性.
2 相关工作
移动自组网络中, 分簇问题可以归结为寻找一个最大独立集问题, 而找一个最大独立集是著名的NP 2hard 问题[3], 因此, 大多数移动自组网络簇生成算法都采用了启发式算法进行簇划分. 根据簇首选择原则
[2]的不同, 可分为最小标识优先
性[7]、最大连接度优先以及最大权值优先算法等. 在最小标识优先算法[3][4]中,I D 较小的节点成为簇首的可能性远高于其他节点, 因此算法在性能有限的移动自组网络中缺乏公平. 而最大连接度优先算法仅以连接度作为启发选择簇首节点, 因此负载均衡度较差, 没有综合考虑网络在稳定性、扩展性等方面的需求. 基于权重的分簇算法综合考虑了系统的节点度, 移动性等多种增强簇结构稳定性因素, 可以保证网络具有更可靠的性能, 是较理想的分簇策略.
基于节点权重的分簇策略以文献[4～8]为代表, , 指示它适合充当簇头的程度, 例如:W =w 1a +w 2b +w 3c +w 4d +ke , a , c 表示节点的传输功率, d e , 参数w 1、w 2、w 3、w 4为权重因子. 文献[6], 网络的稳定性和负载均衡度都得到了较大提高.
但是, “节点运动是随机、互不相关”的假设设计的, 在真实场景中, 特别是车用自组网络中, 车辆节点运动一般都具有较强的组移动特征. 与节点的随机移动相比, 组移动具有几个鲜明的特点:①组内节点运动方式高度相似, 而不同组的运动方式可能差别很大; ②节点的运动速度与方向随机性小; ③在同一个组内, 通常节点密度较大, 相对移动性较小; ④在双向车道上, 相向运动的邻居节点之间相互联系是临时的, 对簇的稳定性影响较大;
针对车用自组网络中节点组内运动状态的关联性, 提出了考虑负载均衡性的W UF
(Weighted utility function ) 算法, 与传统的分簇算法相比, 该算法在网络的负载均衡性和稳定性等方面有较大改善. 但是由于没有考虑稳定邻居以及相向运动节点组之间关联的瞬时性, 因此, 该算法的稳定性有待Peng Fan [9]改进.
针对车用自组网络中节点以及节点组运动规律的主要特征, 充分利用基于权重的簇划分策略的优点, 在文献[7～9]的基础上, 提出了基于权重的稳定性分簇算法, 并且采用模拟退火算法进行优化, 以保证网络在良好负载均衡度条件下, 减少簇重构率, 提高网络分层结构的稳定性.
3 网络分层策略
311 模拟退火优化思想
模拟退火算法(Simulated Annealing ,S A ) [10]是基于M onteCarlo 迭代求解策略的一种随机寻优算法. 通过模拟物理退火过程,S A 由某一较高初温开始, 利用具有概率突跳特性的Metropolis 抽样策略在解空间中进行随机搜索, 伴随温度的不断下降重复抽样过程, 最终得到问题的全局最优解.
[11]模拟退火算法具有4个特点,1) 每个状态都可能到达;2) 在任意给定温度下, 分布相当稳定;3) 当温
度渐近到零度时, 模拟退火收敛到全局最优解;4) 算法的收敛不依赖于初始条件. 与禁忌搜索算法相比, 模拟退火最大的优点在于从理论上保证能够收敛到全局最优解. 因此, 为了避免陷入局部优化, 从而提高分层结构的稳定性和负载均衡性, 我们将模拟退火引入车用自组网络分层研究中.
312 问题描述
假设车用自组网络中所有节点采用全向天线, 节点的传输能力相同, 且所有链路均为双向链路, 则网络用图G (V , E ) 表示, 其中V 表示网络节点集合. {i , j }∈E 表示节点i 、j 间存在的通信链路. 算法中使用
的符号与定义如下:
W i :节点i 的权重值;
N (i ) :节点i 的邻居节点I D 集合;
‖N (i ) ‖:节点i 的邻居节点数;
M :单个簇首节点能服务的最大成员数;
M (i ) :簇成员节点集合, 初始值为空. 仅当i 为簇首节点时, 才更新该集合;
P :一定规则选举出的簇头节点构成集合, 初始值为空集;
H :网络中被选中作为簇头以及这些簇的成员集合, 初始值为空集;
Q :网络中剩余节点的集合, 记为Q =N -H .
定义1 对于给定的网络拓扑图G (V , E ) , 由状态产生函数获得网络中簇头的集合X 为解空间的一状态, 所有可能的簇头集合构成解空间V (X ) , 有X ∈V (X ) . 任意簇头集合的状态产生函数表述如下:
1) 判断集合Q 是否为空集, 为空则算法结束;
2) 从Q 中随机选取一个节点i , 如果满足‖N (i ) ‖≤M , 则有:P =P +{i }; Q =Q -M (i ) -{i }; 如果‖N (i ) ‖>M , 则返回1) ;
定义2 称F (X ) =-ΣW i (X ) 为解X 的能量函数, .
有最小能量值簇头集合. 33, F (X ) ≤F (X ) , 使得网络在保持较好负载均衡度的
基础上, .
313 节点权重分析
在移动自组网络中, 基于权重的分簇算法的基本思想是根据网络中节点的运动变化状态, 节点的邻居节点数以及节点的剩余能量等因数设计节点的权重值. 在许多文献[4～7]中, 均采用平均速度来描述节点的运动, 这是符合M ANET 网络中节点运动的独立性原则, 但是在车用自组网络中, 高速运动节点之间的位置相互关联, 特别是相邻车辆之间的运动更是紧密相关. 因此, 采用平均速度不能有效地描述车辆节点运动速度的变化情况, 并且, 大多数文献中对于平均速度的计算需要依靠其他节点的位置信息, 因此算法的可扩展性不强, 根据分布式原则,SWC A 根据单一节点的速度连续变化信息获得节点的运动改变情况, 从而为更加准确地描述节点运动提供保证.
定义3 在任意的时间段[t 1, t 2]内(T =t 2-t 1) , 有均匀的k 个采样点, 采样时间间隔为Δt =T Πk , 每
Δt 时刻记录自身的运动速度大小和方向(其中n ∈[0, k ]) , 邻居节点数以及邻居节点标识个节点在t =n
Δt 的速度大小为v (i , t ) , 则在T 时间段内速度大小的平均值和方差为分别(I D ) . 设网络中节点i 在t =n
为v (i , T ) , δ(i , T ) .
根据道路上车辆节点组的运动特征, 双向车道上相邻节点之间的邻居关系主要有两种. 相向行驶的车辆节点之间可能是邻居关系, 可以构建在同一个簇内, 但是这种临时邻居关系会削弱簇的稳定性, 相反, 同向行驶的相邻节点之间是稳定的邻居关系, 对簇的稳定性起关键作用. 因此提出节点稳定邻居集合(Stability Neighbor Sets ,S NS ) 作为网络拓扑结构中最重要的稳定性指标, 并定义如下.
定义4 在t 1和t 2时刻, 节点i 的邻居节点I D 的集合分别记为N (i , t 1) , N (i , t 2) , 则邻居数分别记为‖N (i , t 1) ‖, ‖N (i , t 2) ‖, 稳定邻居集合记为N (i , T ) =N (i , t 1) ∩N (i , t 2) , 稳定邻居数记为‖N (i , T ) ‖.
则节点i 的权重归一化模型可以设为:
-N (i , t ) Π2() 2) +w 3W i =w 1+w 2(1-e 1+δ(i , T ) ‖N (i , t 1) ‖
3
且
314 基于模拟退火的分簇初始化i =1∑w 1=1.
在车用自组网络中, 由于节点组在道路上的分割性, 节点的邻居数量差别较大, 因此在进行网络分层时, 必须考虑各个簇头的负载均衡性, 以保证节点的负载、信道的分配能处于均衡状态, 以提高网络的整体性能. 同时, 为了保证网络的稳定性, 在选取簇头集合时应该考虑节点权重值对整体性能的影响, 因此, 设计了多次迭代的簇头选举算法.
模拟退火算法中使用的符号与定义如下:
t 0:算法开始时的初始温度值;
T 0:算法结束时的终止温度值;
R :算法在同一温度下的迭代次数;
λ:温度改变系数, 且0
H :目标函数值在某一区间内保持连续稳定的次数;
ε:状态函数改变的某一极小量;
基于上述模拟退火的基本思想, 对网络分层优化问题进行处理, 算法步骤如下:
①设置控制参数. 初始温度t 0, 温度改变系数λ, 迭代次数r , 成功迭代次数h ;
②随机产生初始状态X =X 0, 并令k =0, r =0, h =0;
③构造X 的邻域解X j , 有X j ∈V (X ) , 且r =r +④如果ΔF =F (X j ) -F (X ) 0, j ⑤. 否则转步骤⑥;
⑤如果|ΔF |+1⑦, , ⑧;
⑥,exp [-(F (X j ) -F (X ) ) Πt k ]}≥random[0,1], X =X j , 转步骤⑧; 否则X =X , ;
⑦如果h ≥H , 转步骤⑨, 否则转步骤⑧;
⑧如果r ≥R , 转步骤⑨, 否则转步骤③;
⑨温度降低. k =k +1, t k +1=λt k , 且r =0, h =0, 并转步骤⑩;
⑩算法终止规则. 如果温度t k ≥T 0, 输出状态解X , 并且算法终止; 否则返回步骤③.
315 簇维护
簇的维护主要包括节点的加入或者离开, 以及簇的分离和合并, 为保持簇首生存时间尽可能长, 故给出如下的规则:
规则1 当一个簇i 的非簇首节点移入另一个簇j 时, 两个簇首均不改变;
规则2 当一个非簇首节点移出当前簇, 没有进入任何已存在的簇时, 它成为一个新的簇首, 形成一个新簇;
规则3 当簇首CH (i ) 从i 移到簇j , 判断两个簇首运动的方向是否一致, 如果为同方向, 则CH (i ) 与CH (j ) 竞争当前簇首, 根据权值大簇首原则, 当前的CH (i ) 或CH (j ) 将放弃它的簇首;
规则4 当簇首CH (i ) 从簇i 移到簇j , 判断两个簇首运动的方向如果不一致, 则两个簇头开始记录
) , T r Π两个簇头作为邻居的连续时间, 当其中任一个簇头记录的T H 满足条件T H ≥max{T r Πv (i , T ′v (j ,
) }时, 两个簇按规则3合并, 否则不合并. 其中T r 为节点信号的传输距离. v (i , T ′) 和v (j , T ′) 分别表示T ′
簇头前一段时间内的平均速率.
由于双向车道上相向而行的簇头之间是一种典型的不稳定邻居关系, 如果按照普通簇合并规则, 将会出现两个簇刚合并后即迅速分离, 直接影响网络层次结构的稳定性. 通过规则4, 可以减轻由于双向簇头临时偶遇给网络稳定性带来的影响.
4 性能分析
本节利用S UM O 提供的车用自组网络拓扑产生器, 同时扩展网络仿真软件NS2相应底层代码实现对算法的支持. 主要研究SWC A 的平均簇数、单位时间内簇头更新次数以及网络的负载均衡因子(LAB )
[9][5]等指标性能, 并且与W UF 的相应指标进行全面比较. 其中网络负载均衡度定义如下:
[12][11]
LB F =∑(x
i i -u ) 2, u
=. n c
n c 为簇头节点的数量, x i 为簇头节点i 的成员数, u 为簇头的平均邻居节点数量, N 为网络中节点总数.
为了简单起见, 还采用了文献[12]提出的城市道路模型, 如图1所示.
每段道路的长度均为200m , 车辆节点在每个道路交叉口的运动方向选择有
两种(直行、左转、右转) 和(直行、转向) , 概率分别为(015、0125、0125) 和
(015、015) . 节点的平均速度在5m Πs 到30m Πs 之间, 节点数为120个. 理想的
簇成员数M =10, 加权系数w 1、w 2、w 3分别为013,013,014. 其他物理层参
数以及模拟退火优化策略中的相关参数设置均与文献[7]一致. 图1 城市道路拓扑图
在节点的平均速度为15m Πs 的情况下, 图2和3表示簇头的平均数和
簇更新率随着节点信号传输范围改变而变化的趋势. 在平均簇头数方面, 虽然SWC A 算法的簇头数量要略高于W UF , 但是在簇的重构性能上, 由于SWC A 考虑了稳定邻居集作为节点权重的重要参数, 同时也考虑了双向车道上簇的重构条件, 因此提高了簇的稳定性
.
图2 平均簇头数vs 传输范围
图3 簇头改变的平均数vs 传输范围
图4描述当节点信号传输范围在250m 时, 簇重构率随着节点速度变化的情况. 显然双向车道上相向运动簇头节点之间的临时邻居关系造成簇的频繁合并和分离, 并没有对SWC A 算法造成较大的影响, 因此在W UF 稳定性能急剧恶化时,SWC A 保持了较高的稳定性
.
图4 单位时间内簇头的平均改变值vs 节点速率
图5 负载均衡度比较
图5表示网络负载均衡度随着仿真时间增加时的性能图. 虽然SWC A 算法中设置了单个节点的最大服务成员数为10, 但是网络中节点的密度不大, 因此对算法的负载均衡度影响不大. 而W UF 在簇的重构上没有考虑不同方向运动节点之间的邻居稳定关系, 因此在双向车道上相向运动的邻居节点之间以及在道路交叉口上运动的邻居节点之间的复杂和临时邻居关系, 对W UF 簇重构后的负载均衡性产生较大的影响, 导致W UF 中各个簇中的成员数之间差异性比较明显. 而SWC A 由于只对满足一定条件的同向运动的簇进行重构, 簇之间的差异性较小, 因此W UF 负载均衡度在总体性能上低于SWC A , 加重了某些簇头的负担, 不利于其他协议的构建.
124系统工程理论与实践2008年7月5 结论
车用自组网作为特殊的移动自组网络, 节点组运动规律性, 道路的双向性以及道路交叉口对网络拓扑结构分层起着关键作用. 根据相邻节点运动规律的相似性, 提出了稳定邻居集概念, 对节点的权重进行重定义, 并基于模拟退火机制对车用自组网络分层机制进行优化, 构造出满足网络需求的初始簇头集合. 并且针对不同邻居关系对簇重构的影响, 提出了新的簇重构策略. 仿真性能分析表明,SWC A 在网络的稳定性和负载的均衡性上均明显优于传统的基于权重的分簇算法. 虽然在簇的优化过程中该算法需要获得网络的整个状态, 算法的扩展性不强. 但是, 通过借鉴该策略, 可以为全面研究车用自组网络分层结构的分布式分簇策略提供有效的解决途径.
下一阶段的工作主要是根据当前的研究结论设计出更加有效、具有较强可扩展性的分布式分簇策略, 并且采用与实际道路拓扑结构更接近的仿真实验环境进行分析验证, 进一步优化分簇算法在复杂道路拓扑结构下的性能.
参考文献:
[1] Y ousefi S , M ousavi M S , Fathy M. Vehicular ad hoc netw orks () :and ΠΠProceedings of the
6th International C on ference on ITS T elecommunication Proceedings , , , :[2] E phremides A , Wieselthier J E , Baker D J. A design hopping signaling
[C]ΠΠProceedings of IEEE , 1987-[3] Mario G, Jack , 2ork[J].AC M 2Balter Journal of Wireless Netw orks , 1995,
(3) :255-[4] Basagni S. clustering for ad hoc netw orks [C]ΠΠProceedings of the Parallel Architectures , Alg orithms and Netw orks.
Perth , June , 1999:310-315.
[5] Chatterjee M , Das S K, Turgut D. An on 2demand weighted clustering alg orithm (WC A ) for ad hoc netw orks[C]ΠΠProceedings of
the IEEE G lobecom 2000, San Francisco , 2000, (11) :1697-1701.
[6] Er I I , Seah W K G. Clustering overhead and convergence time analysis of the m obility 2based multi 2hop clustering alg orithm for
m obile ad hoc netw orks[C]ΠΠProceedings of the Parallel and Distributed Systems , 2005, S ingapore , 2005, (02) :130-134.
[7] Turgut D , Turgut B , E lmasri R , et al. Optimizing clustering alg orithm in m obile ad hoc netw orks using simulated annealing[C]ΠΠ
Proceedings of the Wireless C ommunications and Netw orking , Orlando , F L , US A , 2003:1492-1497.
[8] Chatterjee M , Das S K, Turgut D. WC A :A weighted clustering alg orithm for m obile ad hoc netw orks[J].Journal of Clustering
C omputing (S pecial Issue on M obile Ad hoc Netw orks ) , 2002, (5) :193-204.
[9] Peng F , Haran J , Dillenburg J , et al. T raffic m odel for clustering alg orithms in vehicular ad 2hoc netw orks[C]ΠΠProceedings of the
IEEE C onsumer C ommunications and Netw orking C on ference , 2006:168-172.
[10] 王凌. 智能优化算法及其应用[M].北京:清华大学出版社,2001.
Wang L. Intelligent Optimization Alg orithms with Applications[M].Beijing :TsinghuaUniversity Press , 2001.
[11] 崔勇, 吴建平, 徐恪. 基于模拟退火的服务质量路由算法[J].软件学报,2003,14(5) :877-884.
Cui Y, Wu J P , Xu K. A Q oS routing alg orithm by applying simulated annealing[J].Journal of S oftware , 2003, 14(5) :877-884.
[12] K arnadi F K, M o Z H , Lan K C. Rapid generation of realistic simulation for VANET[C]ΠΠProcessing of the IEEE 2007Wireless
C ommunications and Netw orking C on ference , 2007:2506-2511.
[13] The ns 22Netw ork S imulator. http :ΠΠw w w. isi. edu Πnsnam Πns Π.
[14] Jaap S , Bechler M , W olf L. Evaluation of routing protocols for vehicular ad hoc netw orks in city traffic scenarios http Π:Πw w w. ibr.
cs. tu 2bs. de Πusers Πbechler ΠmyPublications Πmarc JaBW05. pd f.
[15] Helbing D , Hennecke A , Shvets ov V , T reiber M. Micro 2and Macro 2simulation of Freeway T raffic[M].Mathematical and C omputer
M odeling , 2002, (35) :517-547.