基于模糊集理论的Ad Hoc网络优化的研究
2016-11-23柴宝仁谷文成韩金库
柴宝仁, 谷文成, 韩金库
(1.齐齐哈尔大学 应用技术学院, 黑龙江,齐齐哈尔 161006;2.齐齐哈尔大学 现代教育技术中心,黑龙江,齐齐哈尔 161006;3.齐齐哈尔大学 计算机与控制工程学院,黑龙江,齐齐哈尔 161006)
基于模糊集理论的Ad Hoc网络优化的研究
柴宝仁1, 谷文成2, 韩金库3
(1.齐齐哈尔大学 应用技术学院, 黑龙江,齐齐哈尔 161006;2.齐齐哈尔大学 现代教育技术中心,黑龙江,齐齐哈尔 161006;3.齐齐哈尔大学 计算机与控制工程学院,黑龙江,齐齐哈尔 161006)
为了提高Ad Hoc网络的综合性能,满足不同领域对Hd Hoc网络的应用需求,基于模糊集理论(FST)提出了一种对Ad Hoc网络的优化的方法,构建了包含新增覆盖网络节点数量相对度和剩余能量相对度的评价指标集合、等级标准集合,并定义了评价指标相关的权重. 利用模糊集理论的关系合成运算法则,对Ad Hoc网络重播分组时进行优化,达到了对Ad Hoc网络优化的目的. 基于网络模拟器NS-3对FSTA和BCAST进行了仿真实验测试,通过对网络生命周期、丢包率和网络吞吐率3个性能指标的对比分析和评估,结果表明FSTA优于BCAST,验证了FSTA对Ad Hoc网络优化的有效性,改善了Ad Hoc网络的性能.
模糊集理论(FST);Ad Hoc网络;网络优化;评价矩阵
Ad Hoc网络是一种具有独立组网、自组织、动态拓扑、由移动网络节点组成的无线移动网络. 最早出现于20世纪70年代末期,Ad Hoc网络最初是为了满足军事需求[1]. 随着网络技术的不断发展,Ad Hoc网络逐渐被用于商业领域和民用领域.
模糊集理论是L.A.Zadeh 1965年创立的[2],L.A.Zadeh把模糊性问题和数学统一了起来,模糊集理论的出现使数学能够描述那些过去无法用精确数学处理的模糊性事物.
Ad Hoc网络由于网络移动性和网络无线通信信道的不稳定性,导致Ad Hoc网络的网络拓扑结构不稳定[3],从而导致Ad Hoc网络局部信息的不确定性,而模糊集理论对于不确定性问题则具有很好的鲁棒性和适应性[4-5]. 本文提出一种新的基于模糊集理论的Ad Hoc网络优化算法FSTA,以新增覆盖网络节点数量的相对度、剩余能量的相对度和重播分组的延迟时间等作为评价指标,优化重播分组的优先权. 仿真实验表明FSTA提高了网络生命周期和吞吐率,降低了平均端对端延迟和平均丢包次数,提高了Ad Hoc网络组播效率.
1 模糊集理论
模糊集理论由于引入了隶属函数,从而突破了传统经典几何理论,模糊集理论针对模糊集定义了运算规则及其推理逻辑,从而完成模糊逻辑推理过程,解决具有模糊特性的实际问题.
模糊集的运算规则定义如下:
① 并运算规则.
设A和B为对象空间X中的模糊集,则模糊集A和B的并运算为
(1)
式中μC(xi)为模糊集C的隶属函数,且
② 交运算规则.
设A和B为对象空间X中的模糊集,则模糊集A和B的交运算为
(2)
式中μC(xi)为模糊集C的隶属函数,且
③ 关系合成运算规则.
设Q为U×V上的一个模糊关系,R为V×W上的一个模糊关系,S为U×W上的一个模糊关系,即
Q=(qi,k)m×l,R=(rk,j)l×n,S=(si,j)m×n
(i=1, 2,…,m,j=1,2,…,n,k=1,2,…,l),
则Q对R的合成运算为
(3)
2 FSTA的评价指标
2.1 新增覆盖网络节点数量的相对度
设G(V,E)为可用有向图,表示一个AdHoc网络,其中V={V1,V2,…,Vn}为网络节点集合, E={(i,j)|d(i,j)≤r}为网络节点之间的逻辑链路集合,其中:d(i,j)为网络节点Vi和Vj间的距离,r为网络节点的传输半径.
若网络节点在一方形区域内随机移动,设此区域的长宽分别为W与H,在此区域内有N个网络节点,则每个网络节点平均相邻网络节点数目为
(4)
若网络节点A向网络节点B发送重播分组信息,网络节点A和B的传输半径为r,网络节点A和B间的距离为d,且0 (5) 因此 (6) 由式(6)可知,网络节点在重播分组时新增覆盖的网络节点个数和网络节点新增覆盖面积是成正比的. 另外为了避免那些几乎不能到达新的相邻网络节点的网络节点浪费网络资源,可以优先让新增覆盖网络节点数量多的节点进行分组. 设网络节点A和网络节点B的相邻网络节点集合为VA和VB,网络节点A发送分组时,查询相邻网络节点列表,获取相邻网络节点重播分组后新增覆盖网络节点数量的最大值为 (7) (8) 2.2 网络节点剩余能量的相对度 网络节点消耗的总能量为 (9) 式中:n为需发送分组信息的网络节点个数;m为需接收分组信息的个数;ESE为网络节点发送一个分组信息所消耗的能量;ERE为网络节点接收一个分组信息所消耗的能量;ESL为网络节点处于休眠状态所需消耗的能量;EDE为网络节点处于侦听状态所需消耗的能量. 网络节点接收分组信息后,其剩余能量为 (10) 式中EIN为网络节点的初始能量. 网络节点A发送或转发重播分组信息时,通过查询相邻网络节点列表获取网络节点A相邻网络节点的剩余能量最大值Emax(A),即 (11) 式中U∈VA,ECUR(U)为网络节点U的剩余能量. 当网络节点B接收到A的重播分组信息后,若ECUR(B)>Emax(A),则Emax(A)=ECUR(B). 若Emax(A)>0,则网络节点B的剩余能量的相对度定义为 (12) 2.3 网络节点重播分组的延迟时间 通常,若新增覆盖网络节点数量多,网络节点剩余能量多,则网络节点重播分组的延迟时间相对较短. 而新增覆盖网络节点数量少,网络节点剩余能量少,则网络节点重播分组的延迟时间相对较长. 若网络节点转发重播分组的延迟时间为tdelay,为了避免网络节点重播分组的延迟时间值相近的网络节点在重播分组时产生竞争冲突,定义实际重播分组的延迟时间为 (13) 式中:σ为常数;Q为0到1间均匀分布的随机数. 为避免网络资源的浪费,FSTA在网络节点重播分组时,根据新增覆盖网络节点数量设置重播分组的延迟时间,让新增覆盖网络节点数量多并且剩余能量相对多的网络节点优先转发分组,这样可以减少转播冗余,抑制冗余大的网络节点重播分组,避免产生网络节点竞争和冲突,同时均衡了网络中的能量消耗,延长网络的生命周期,并且能够快速地将重播分组信息覆盖整个网络,从而提高了重播分组信息覆盖网络所有节点的速度,提高了数据分发的比率,提高了重播分组的性能. 3.1 评价矩阵 由于Ad Hoc网络一般应用于战场、抢险救灾等恶劣环境,同时Ad Hoc网络也广泛应用于环境监控、商务会议等特殊环境,因此Ad Hoc网络受到人为因素、设备自身因素、天气情况、空气质量、电磁噪音干扰等多方面因素的影响. 为此针对某类特定环境中,可以抽取该环境中一些具有代表性的影响因素作为评判因子,例如雷雨、大雾、暴风雪、沙尘暴等特殊天气情况,空气的湿度、温度、不同颗粒的含量、电磁信号等,提取这些具有代表性的影响因素作为评价指标,构建评估方案. 本文以新增覆盖网络节点数量和网络节点的剩余能量对Ad Hoc网络影响比较重要的两个因素作为评价指标,构建了评估方案,实际上在很多情况下,地理环境和天气情况等因素也是影响Ad Hoc网络性能的重要因素,因此在构建评估方案时,要尽可能充分考虑各方面的因素. 设EV={e1,e2,…,ek},其中k为抽取评价指标的个数. 在一特定的环境中,由于各个评价指标在评价方案中作用和地位不同,因此根据实际情况定义一个与评价指标相关的权重向量 W=[w1w2… wk], 其中W的分量wi值为评价指标ei的参考权重. 另外定义一个评价等级标准G={g1,g2,…,gp},其中p为定义的等级标准数目. 例如令p=4,并定义g1=A等级(优秀),g2=B等级(良好),g3=C等级(合格),g4=D等级(不合格). 这样针对特定环境,对一个评估对象可以获取k个评价指标组成的集合EV,并获取权重向量W,根据定义的评价等级标准G,评价指标ei(i=1,2,…,k)针对p个评价等级标准获取一个隶属值,从而得到一个k×p的矩阵R,矩阵R就是评价矩阵. 在获取评价矩阵R时,可以针对典型的环境进行多次测试,然后根据实际情况调整评价矩阵R,这样可以尽可能地获取更加理想和切合实际情况的评价矩阵. 3.2 FSTA的Ad Hoc网络优化的实现 这样评估对象Vi(i=1,2,…,m)将获得一个1×p的评估结果D(Vi)={d1,d2,…,dp},若在评估结果D(Vi)中p个值中最大值为dj(1≤j≤p),则评估对象Vi的最终评价结果的等级标准为gj,具体处理步骤如下(见图3): 步骤2 若Vi接收到的分组信息使重复分组信息或者网络分组的TTL值为0,则转步骤8; 步骤4 若网络节点A在网络节点Vi相邻网络节点列表中,则更新网络节点Vi相邻网络节点列表;否则将网络节点A的信息添加到网络节点Vi相邻网络节点列表中; 步骤7 根据FSTA所获得的结果重播分组; 步骤8 放弃分组. 当FSTA在Ad Hoc网络进行重播分组时,丢弃新增覆盖网络节点数量较少和剩余能量较少的那些网络节点,这样就可以减少广播冗余,也减少了网络节点的竞争和冲突,同时还减少了丢弃分组的网络节点转发分组次数,减少丢弃分组网络节点的能量消耗,从而也就延长了网络的生命周期. 本文在基于面向对象网络模拟器NS-3仿真环境中,针对FSTA的Ad Hoc网络优化效果进行仿真实验分析. 仿真实验设置为100个移动网络节点随机分布在1.5 km×1.5 km矩形区域内,网络节点传输半径r设置为200 m,仿真时间为设置180 s. 仿真实验通过网络生命周期、网络节点丢包率和吞吐率3个性能指标对FSTA和BCAST进行性能对比分析,仿真实验结果见图4~图6所示. 由于FSTA转发分组时,减少丢弃分组网的络节点的能量消耗,从而延长了网络生命周期,结果使FSTA的网络生命周期长于BCAST(见图4). FSTA转发分组时,新增覆盖网络节点数量多的网络节点优先重播分组,同时减少广播冗余,也减少了网络节点竞争和冲突,因此FSTA的丢包率低于BCAST(见图5). FSTA延长了网络生命周期,增加了重播分组的时间,提高了重播分组的数量,因此FSTA的网络吞吐率优于BCAST(见图6). 本文利用基于NS-3仿真实验测试评估了FSTA的Ad Hoc网络优化效果. 为使仿真实验更接近真实情况,获得更真实可靠的仿真实验数据,每个仿真实验数据都是通过多次仿真实验获得,并取其平均值作为最终仿真实验结果. 实验结果表明FSTA的网络生命周期、丢包率和网络吞吐率优于BCAST,改善了Ad Hoc网络的性能,这充分说明基于FSTA的Ad Hoc网络优化的有效性. [1] Barry L M, Robert R J, Ambatipudisastry R. Goals and challenges of the DARPA GloMo program[J]. IEEE Personal Communications, 1996,3(6):34-43. [2] Zadeh L A. Fuzzy sets[J]. Information and Control, 1965,8(3):338-353. [3] Alahdal T, Subramaniam S, Othman M, et al.An adaptive reliable multicast protocol in ad hoc networks[C]∥Proceedings of the 2007 IEEE International Conference on Telecommunications and Malaysia International Conference on Communications. Penang: IEEE, 2007:68-74. [4] 王庆林,陈锦娣,黄西士,等.智能模糊控制器[J].北京理工大学学报,1993,13(3):361-366. Wang Qinglin, Chen Jindi, Huang Xishi, et al. On intelligent fuzzy controllers[J]. Transactions of Beijing Institute of Technology, 1993,13(3):361-366. (in Chinese) [5] 徐勇,侯朝桢,萝莉.基于模糊状态的可修表决系统可靠性分析[J].北京理工大学学报,2000,20(6):698-702. Xu Yong,Hou Chaozhen,Luo li. Reliability analysis of repairable vote systems based on fuzzy-state[J]. Transactions of Beijing Institute of Technology, 2000,20(6):698-702.(in Chinese) (责任编辑:刘雨) Research on Ad Hoc Network Optimization Based on Fuzzy Sets Theory CHAI Bao-ren1, GU Wen-cheng2, HAN Jin-ku3 (1.School of Applied Technology, Qiqihar University, Qiqihar, Heilongjiang 161006, China;2.Modern Education Technology Center, Qiqihar University, Qiqihar, Heilongjiang 161006, China;3.College of Computer and Control Engineering, Qiqihar University, Qiqihar, Heilongjiang 161006, China) In order to improve the comprehensive performance of Ad Hoc network and satisfy the application the need to Hd Hoc network in different fields, a Ad Hoc network optimization method was proposed based on fuzzy set theory (FST). And an evaluation index set and degree standard set were also constructed, which contain the relative degree of new overlay network node number and the relative degree of residual energy, and the relative weight to evaluation index was defined. The relation synthesis algorithm rules of fuzzy set theory were applied to optimize the replay packet for Ad Hoc network. Based on network simulator NS-3, a simulation test of FSTA and BCAST was conducted. Comparing and evaluating the capability about network lifetime, packet loss and network throughput, results show that FSTA is more excellent than BCAST, verify the FSTA validity on Ad Hoc network optimization and improvement performance of Ad Hoc network. fuzzy sets theory(FST); Ad Hoc network; network optimization; evaluation matrix 2014-06-10 国家“九七三”计划项目(2010CB731800);国家自然科学基金资助项目(41075103) 柴宝仁(1958—),男,副教授,E-mail:cbr0418@126.com. TP 301.6 A 1001-0645(2016)08-0795-05 10.15918/j.tbit1001-0645.2016.08.0053 FSTA对Ad Hoc网络的优化
4 仿真实验结果及分析
5 结 论