基于ISOA的VANET自适应数据传输算法*

陈秉试

(厦门海洋职业技术学院, 福建 厦门 361012)

基于ISOA的VANET自适应数据传输算法*

陈秉试

(厦门海洋职业技术学院, 福建 厦门 361012)

针对基于802.11p的车载自组织网络(VANET, Vehicular Ad hoc Network)的吞吐量最优化问题，采用启发式搜索优化的思想，在数据传输方面提出了改进的搜索者优化算法(ISOA, Improved Seeker Optimization Algorithm)。该算法通过对节点发送概率的最优化实现节点平均吞吐量的最大化；通过对吞吐量变化的检测调整发送概率，实现对通信环境变化的自适应性；通过对在VANET场景下传统SOA的改进，提高了搜索全局最优解的成功率。仿真结果表明，ISOA较传统算法在环境变化自适应性方面更好，在收敛速度及准确度等方面性能也更优。

车载自组织网络 改进的搜索者优化算法 自适应数据传输算法

0 引 言

车载自组织网以车-车、车-路边节点通信为主要模式，以自组织性为核心，并具有拓扑高动态变化、节点运动受道路约束、能量不受限等特点受到关注，近年来逐渐成为研究热点[1-2]。

2010年7月，IEEE802.11p修正案发布并成为VANET中经典的MAC层标准。该标准的MAC层方案以IEEE802.11 DCF和IEEE802.11e EDCA为基础，相关的性能已经有学者进行了研究[3-6]。网络吞吐量是一个重要的性能指标，可以通过对时隙占用的近似最优化[5]或者对节点发送概率的最优化[7]实现最大吞吐量。然而在VANET中，节点拓扑高度动态化，如何在低复杂度、低网络开销的情况下，让节点自适应地根据通信环境变化调整参数保持在最优吞吐量已成为挑战。

启发式搜索优化算法能很好地解决非线性、多峰目标函数的最优化问题，具有很强的实用性。其中，2007年提出的搜索者优化算法(SOA, Seeker Optimization Algorithm)[7]在搜索全局最优解方面具有良好的性能，已经被应用于电子、通信及自动化等多个领域[8-10]，充分体现了该算法的竞争力。

通过在VANET场景下对SOA的改进，并应用于吞吐量最优化中，提出基于ISOA的数据传输算法。仿真结果表明，ISOA不仅能快速、高效地获得全局最优解，还能根据通信环境自适应调整参量值，具有很强的实用价值。

1 VANET吞吐量分析

1.1 VANET场景设定

将网络分簇可提高资源的复用性并减少竞争，因此假设讨论的VANET为已分簇的情况，即预先已将车辆分组。为增强簇的稳定性，假定簇内均为同向行驶的车辆。总体场景示意图及基本参数设置如图1所示。

图1 场景示意图及基本参数设置

1.2 吞吐量分析

在802.11 DCF给定的访问模式下k为常数，但用户数n的获取是个难题，通常可以利用节点之间交互信息或者理论上的近似解决[5]。节点之间通过信息交互可获得周边节点分布，从而获知n值，但这将增大网络开销。为了削减交互开销，可以通过其他参量的检测间接感知n的变化，文献[5]定义了“时隙利用率”，通过公式的近似推导发现该参量与节点数无关，并且是可检测，每个节点通过调整发送概率使时隙利用率达到最佳，从而达到最优吞吐量。由于近似条件的约束，该方案在n较大时才会有较好的近似度，而n较小时会有误差。

然而更棘手的问题在于，现实场景中由于物理层机制、信道衰减、多用户干扰及环境噪声干扰、多普勒频移等因素的不同，即使相同的n也会有不同的最佳吞吐量。这些影响因素具有很强的随机性，并且常常难以用数学模型准确描述。因此，在不同的并且难以数学建模的通信环境下，如何让节点将发送概率τ自适应地调整到最佳值成为关键。

2 基于ISOA的吞吐量最优化

SOA是以并行搜索以及迭代更新的方式收敛于全局最优，与目前主流的启发式算法类似，采用的是“尝试”的思想，适用于多维、非线性全局最优化问题[8-10]。在目标函数构成的空间中，SOA构造K个种群，每个种群拥有P个搜索者，而每个搜索者含有D个变量，变量个数即为待优化的参量的个数。根据文献[8]中公式确定第G代中第i个搜索者的第j维的搜索步长aij及搜索方向di(G)从而递推出下一代搜索者位置，直到满足收敛条件或者达到最大迭代次数。

ISOA以SOA为基础，有3个关键阶段：①利用SOA生成候选发送概率集合{τd,i}(i=1,2,…,KP)；②检测τd,i对应的吞吐量Sd,i是否为最佳值；③ 附加搜索空间再次搜索最优解以缓解局部收敛现象。以上三个阶段不断循环迭代直到收敛于全局最优值Sd,max后即可获得对应的最佳发送概率τopt。下面将阐述具体过程，主要目标是：①实现对通信环境的自适应性；② 解决SOA局部收敛问题。

总体流程如图2所示。

图2 ISOA流程

2.1 生成搜索空间

ISOA的核心思想是在最优解可能存在的取值范围内筛选，因此首先需要估计待优化变量τ取值范围，即生成搜索空间。该取值范围理论上应为[0,1]，但由于所讨论的问题的用户数最少为2，则对应最大的τopt=1/(2k)。另外，τ=0表示节点不发送数据，也不具有讨论价值，因此最终取值范围可缩小为(0,1/(2k)]，然后在该搜索空间中随机生成KP个第1代的搜索者。需要说明的是，实际中节点对发送概率的调整可通过对节点接入信道请求依照概率过滤的方法实现[5]。

2.2 设定收敛条件

需要说明的是，车辆节点自身运动速度固然快，但是同向道路上车辆间相对速度较小，除非遇到岔路口或快速超车等情况，一般而言在城市环境下簇内相对拓扑关系可维持在几秒到几十秒，而在相对封闭的高速公路上拓扑持续时间会更长，因此毫秒级的吞吐量检测持续时间是可接受的。节点通过周期地检测吞吐量变化自适应地调整发送概率，这将从根本上实现对通信环境变化的自适应，而不需要节点间交互信息，也不需要对通信环境进行建模，该方法简单易行且具有实用性。

2.3 解决局部收敛

传统的SOA机制会出现一定概率的早熟现象，即收敛于局部最优解。出现这种情况时，节点以为已经达到最优吞吐量，而不再调整τd,i。ISOA在节点收敛后引入阶段③解决该问题。关键环节是当节点收敛后并不停止搜索，而是在收敛后附加一个小范围搜索空间再次搜索，即在收敛点附近一定范围内搜索，若有更优解则说明之前收敛于局部节点，否则认为已获得全局最优解。假设节点已收敛于发送概率τopt,pre，定义附加搜索空间的半径为Δτ=α·τopt,pre，其中α为附加因子，则附加的搜索空间为[τopt,pre-Δτ,τopt,pre+Δτ]，若在该空间内再次利用SOA搜索后得到的结果τopt,now等于τopt,pre则认为得到全局最优。有两点需要说明：①理论上，在附加搜索空间搜索后仍有可能导致局部收敛，但实验表明出现这种情况的概率很小；②该方法是以增加一定迭代次数为代价换取更高的全局收敛准确度，但由于附加空间一般不大，因此新一轮搜索的收敛速度很快，新增的迭代次数并不多，从而高效地解决了SOA收敛于局部最优解的问题。

3 仿真及分析

表1 DCF参数设定

再次，还需要设定ISOA相关参数。一部分是沿用传统SOA中的参数，则设定成典型值[8-9]：子种群数K=3，子种群内搜索者个数P=4，步长最小及最大隶属度分别为μmin=0.011 1及μmax=0.98。另一部分为根据实际需要重新设定的SOA参数以及新增参数：只需要对τ优化，则D=1；根据实验经验值设定最大迭代次数1 800，附加因子α=5%，吞吐量容错误差ΔS=1 b/s，吞吐量检测周期为TSd=5 ms。下面将从收敛性及自适应性等角度分析ISOA的性能。

3.1 收敛速度及准确度

对于启发式算法而言，收敛速度越快、收敛到全局最优解的准确度越高，则算法性能越好。收敛速度可以迭代次数衡量，收敛准确度则可以总实验次数中，收敛到全局最优解的次数所占的比例表征。假设参与竞争的仿真节点数为10，不考虑其他环境变化及干扰的理想情况下，根据表1参数可计算出最佳发送概率为0.044 98，对应的最佳吞吐量为1.759 2 Mb/s。由于实际中吞吐量是检测参量，并且与发送概率一一对应，因此以吞吐量为仿真量检验算法性能。启发式算法具有一定随机性，实验中重复仿真105次(实验发现大于105次的重复仿真的结果与之相同)并统计的收敛误差及迭代次数分别如图3和图4所示。

(a) ISOA

(b) SOA

假定收敛值与真值误差在1 b/s之内时认为收敛成功，由图3可以直观地看出，ISOA在100b/s以上的部分比SOA稀疏的多，这就说明ISOA的收敛成功率更高。定量上，在105次的重复实验中，SOA成功收敛的次数为63 019次，收敛准确度为63.019%；而ISOA成功收敛的次数为99 941次，收敛准确度为99.941%，这主要因为ISOA增加了附加搜索过程，从而大大改善了准确度。这一优势在图4中也可以看出。SOA有36 981次实验迭代数达到最大迭代次数1 800，而成功收敛的情况下迭代次数一般远小于该值，这意味着每一次实验SOA都有36.981%的概率在尽最大努力后也无法准确收敛。但需要说明的是，ISOA是以增加迭代次数为代价换取准确度的提升。从图4的数据统计中发现，在成功收敛的情况下，SOA平均迭代次数为141.710 024次，而ISOA也取收敛速度最快的前63 019个实验结果求得的均值为158.245 883，增幅为11.67%。当TSd=5 ms时大约相当于多耗费58 ms，这段时间对于VANET而言节点间相对拓扑几乎不变，因此这少量的迭代次数增幅换取大幅度的准确度提升是值得的。

3.2 对通信环境变化的自适应性

通信环境复杂多变，固定的数学模型通常只能拟合部分特殊场景，启发式算法却能有很好的自适应性。保持参与竞争的仿真节点数为10，考虑环境变化及干扰时，最佳吞吐量不总保持在1.759 2 Mb/s，一般会更差且为时变值。为了模拟该场景，假设仿真时间为500个TSd，最佳吞吐量初始状态为理论最佳值1.759 2 Mb/s，第250个TSd时衰减为1 Mb/s，将分别仿真ISOA、SOA的性能。

如图5所示，当节点数不变但通信环境改变导致最佳吞吐量变化时，ISOA及SOA都能很好地做出自适应地调整，使吞吐量维持在当前最优值。显然，只由节点数n决定最佳发送概率的传统算法[7]不能实现这种自适应性。

值得注意的是，由于启发式算法收敛过程需要一定时间，并且迭代次数具有一定随机性，因此通信环境变化越频繁、变化时间间隔越短，对算法性能的挑战越大。为了比对ISOA及SOA在不同环境变化频度下自适应性能，定义环境变化周期ΔTSC，即假定最佳吞吐量真值每间隔ΔTSC随机变化一次，保持仿真时间为2 000个TSd，分别取不同的ΔTSC观测收敛准确度(为了分析方便，设ΔTSC为TSd的整数倍)。

图5 ISOA及SOA的自适应性

如图6所示，当ΔTSC较小时，ISOA及SOA的准确度都不高，这是因为两种算法都需要一定的迭代次数以收敛到最优解，若环境变化过于频繁，允许的迭代次数不足将导致收敛准确度降低。随着ΔTSC增大，两种算法的性能都有所提升，这说明允许迭代次数越充足对收敛性能越有利，但ISOA的准确度明显优于SOA，这得益于ISOA采用抗局部收敛措施。当ΔTSC>1 300时收敛准确度趋于稳定，实际情况中，VANET节点拓扑及通信环境一般在几秒内变化不大，已位于收敛准确度稳定区域，可见ISOA具有很强的实用性。

图6 不同ΔTSC下，ISOA及SOA的收敛准确度

4 结 语

在基于IEEE 802.11p的分簇VANET环境下，提出基于ISOA的数据传输算法实现吞吐量的最优化。该算法在传统SOA的基础上引入了附加搜索空间的方法，在增加少量迭代次数的情况下大幅提升收敛准确度。在通信环境自适应性方面，ISOA可自发调整参数值以使节点保持在最优吞吐量，并且性能优于SOA，较传统算法更具有绝对优势。仿真结果表明，在VANET环境的特征下，ISOA有很强的实用价值。

[1] 徐婷，王新红，王平. 车联网中基于多优先级的自适应动态路由协议[J]. 通信技术，2014，47(02)：163-166. XU ting,WANG Xin-long,WANG Ping. Multi-Priority Dynamic Adaptive Routing Protocol for VANET[J]. Communications Technology，2014，47(02)：163-166.

[2] 彭好佑，冯文龙. VANET网络中一种新的认证方法[J]. 通信技术，2012，45(03)：46-48. PENG Hao-you, FENG Wen-long. A Novel Authentication Method in VANET Network[J]. Communications Technology，2012，45(03)：46-48.

[3] 张本宏，陆阳，吴其林等. 有限负载下IEEE802.11DCF机制时延分析[J].电子测量与仪器学报，2011,25(02):176-180. ZHANG Ben-hong, LU Yang, WU Qi-lin，et al. Delay Analysis for IEEE 802.11 DCF Mechanism in Finite Load[J]. Journal of Electronic Measurement and Instrument, 2011, 25(02): 176-180.

[4] 毛建兵，毛玉明，冷甦鹏等.支持QoS的IEEE802.11EDCA性能研究[J].软件学报，2010,21(04):750-770. MAO Jian-bin，MAO Yu-ming，LENG Su-peng． Research of the QoS-Supporting IEEE 802.11 EDCA Performance[J]． Journal of Software，2010，21(04): 750-770． (in Chinese)

[5] 毛建兵，毛玉明，冷甦鹏． 一种提高IEEE 802. 11 吞吐量和公平性的自适应优化算法[J]． 电子与信息学报，2009，31( 11): 2731-2737．

MAO Jian-bin，MAO Yu-ming，LENG Su-peng． An Adaptive Optimization Scheme for IEEE 802. 11 to Improve Throughput and Fairness Performance[J]． Journal of Electronics & Information Technology，2009，31(11): 2731-2737． (in Chinese)

[6] 张和生，张明洋，孙伟. 基于IEEE802.11p高速车路通信环境研究[J]. 仪器仪表学报，2013，34(05): 1181-1187. ZHANG He-sheng, ZHANG Ming-yang, SUN Wei. Research on Vehicle to Infrastructure High Speed Communication based on IEEE 802.11p [J]. Chinese Journal of Scientific Instrument，2013，34(05):1181-1187.

[7] Binachi G. PerformanceAnalysis of the IEEE 802.11 Distributed Coordination Function[J]. IEEE Journal on Selected Areas in Communications, 2000, 18(3): 535-547.

[8] DAI Chao-hua, ZHU Yun-fang and CHEN Wei-rong. Seeker Optimization Algorithm [C]//2006 International Conference on Computational Intelligence and Security, Guangzhou, 2006. Berlin, Germany:Springer-Verlag, 2007:167-176.

[9] DAI Chao-hua, ZHU Yun-fang and CHEN Wei-rong. Seeker Optimization Algorithm for Digital IIR Filter Design [J]. IEEE Transactions on Industrial Electronics, 2010, 57(5): 1710-1718.

[10] Saha, S.K., Kar, R. and Mandal, D. et al. Seeker Optimisation Algorithm: Application to the Design of Linear Phase Finite Impulse Response Filter [J]. IET Signal Processing, 2012, 6(8): 763-771.

CHEN Bing-shi(1978-), male, lecturer, mainly engaged in communication and information system.

VANET Adaptive Data Transmission Algorithm based on ISOA

CHEN Bing-shi

(Xiamen Ocean Vocational College,Xiamen Fujian 361012,China)

Aiming at the throughput optimization of VANET (Vehicular Ad hoc Network) based on 802.11p, the idea of heuristic-searching optimization is adopted and ISOA (Improved Seeker Optimization Algorithm) proposed in data transmission. By optimizing the transmission probability, this algorithm maximizes the average throughput of each node, and data transmission probability is adjusted automatically by detecting the variation of throughput, thus to achieve self-adaption in accordance with the change of communication environment. Traditional SOA in VANET scene is modified so as to improve the success rate for searching the global optimal solution. Simulation results show that ISOA is more adaptable to the change of communication environment than traditional algorithm and enjoys superiority in the aspect of convergence rate and accuracy.

VANET; ISOA; adaptive data transmission algorithm

date:2014-10-11；Revised date：2015-01-20

TN929.52

A

1002-0802(2015)03-0289-06

陈秉试(1978—)，男，讲师，主要研究方向为通信与信息系统。

10.3969/j.issn.1002-0802.2015.03.009

2014-10-11；

2015-01-20