Research on Automatic Generation of Test Data in MX Based on Genetic Algorithms
-
摘要: 利用遗传算法进行测试数据自动生成是近年来的研究热点,其有效性高度依赖于适应度函数的选取和初始种群的筛选。该文探索将遗传算法应用到IMX(Integrated Management X-software)系统测试数据自动生成以提高其回归测试的质量,将IMX系统专业测试人员手动生成的测试数据作为基础测试数据,并提出一种基于测试路径对目标路径覆盖率的初始种群筛选标准。在三角形程序和IMX系统平台上的实验表明,所提方法在寻找测试数据时所用的时间和迭代次数较少,且生成的测试数据具有较好的多样性。Abstract: Using genetic algorithms to generate test data automatically is becoming a hot topic in recent years, the method on effectively generating data is highly dependent on choosing the proper fitness function and the selecting standard. The genetic algorithm is used on Integrated Management X-software (IMX) system to help it improve the quality of regression test. Those basic test data used in this paper are taken from the data that generated by professional testers in IMX, and an initial population selecting standard is proposed based on the coverage. Experiments on IMX and triangle program show that the proposed algorithm is more effective than others, for example, with less time and iteration the method can find the testing data correctly, especially on data variety.
-
1. 引言
紫外(UltraViolet, UV)波长在200~280 nm的波段,由于臭氧分子的强烈吸收作用,使得该波段的紫外光在近地面几乎衰减为零,称该波段为“日盲区”[1]。无线紫外光通信主要利用该波段的紫外光作为载体,通过大气分子、气溶胶等微粒的散射作用进行信息的传递[2],具有非直视(Non-Line-Of-Sight, NLOS)、高保密性、低窃听率、抗干扰能力强等优点,特别适用于无人机编队飞行、海军舰艇编队、陆军装甲编队、导弹车车队在无线电静默和复杂环境下的军事隐秘通信[3,4]。但由于紫外光的散射通信以及大气湍流的偏折作用,大气信道衰减严重、接收信号微弱、具有高路径损耗等,使得紫外光通信传输距离有限[5]。因此,通过多跳中继方式来延长无线紫外光通信距离成为研究的热点。
目前已有学者对紫外光多跳中继通信进行了相关研究,文献[6]在紫外光通信网中通过多跳中继方式增加了通信范围,并节省了功率消耗。文献[7]研究了紫外光多跳中继通信中节点连通问题,适当调整节点密度、发射功率和数据速率,使得紫外光多跳中继通信网络中中继孤立节点存在的概率趋近于零。文献[8]针对紫外光通信中光源器件发射功率受限和大气信道衰减严重造成传输距离近的问题,提出采用多跳中继方式构建紫外光长距离通信链路,提高了系统功率利用率。文献[9]研究结果表明,选择合适的无线紫外光通信系统配置对提高多跳中继通信系统性能是至关重要的。
上述研究都是建立在节点等距离分布下的性能研究,而对于紫外光多跳中继通信系统中节点随机分布的最优跳数问题研究较少。文献[10]为减少无线传感器网络节点的能量消耗,使用紫外光作为信息载体,在等距离分布下得出了使能量消耗最低的最优跳数表达式。但研究未考虑紫外光通信系统配置问题,而紫外光通信的整体性能高度依赖于系统配置,特别是收发仰角[9]。因此,本文基于无线紫外光非直视单次散射模型,研究了车队中车辆在随机分布状态下无线紫外光多跳中继通信的收发仰角与最优跳数的关系,根据信道容量和路径损耗得出两者之间的近似表达式,并分析了不同收发仰角下的系统性能。
2. 无线紫外光多跳中继通信系统模型
2.1 无线紫外光非直视单次散射模型分析
由于大气对紫外光强散射作用,使紫外光通信信道能够构成非直视通信链路。实际中紫外光通信是多次散射的,但在短距离通信中,单次散射传输为主[11],因此本文以单次散射模型作为研究基础。紫外光单次散射模型如图1所示[12],βT是发射仰角,βR是接收仰角,θT是发散角,θR是接收视场角,V是有效散射体,θS是散射角,r是收发端基线距离。
发射端TX以βT和θT的角度向空间发射光信号,光信号在有效散射体V内散射后,接收端RX以βR和θR的角度进行光信号接收,则紫外光单次散射通信的接收光功率为[12]
Pr=PtArKsPsθRθ2Tsin(βT+βR)32π3rsinβT(1−cosθT2)⋅exp[−Ker(sinβT+sinβR)sin(βT+βR)] (1) 其中,Pt是发射光功率,Ar是接收孔径面积,Ks是大气散射系数,Ps是散射角θs的相函数,Ke是大气信道衰减系数,且Ke=Ka+Ks, Ka是大气吸收系数。
非直视紫外光散射通信的路径损耗可表示为发射光功率与接收光功率的比值,如式(2)所示
L=PtPr=32π3rsinβT(1−cosθT2)ArKsPsθRθ2Tsin(βT+βR)⋅exp[Ker(sinβT+sinβR)sin(βT+βR)] (2) 式(2)为路径损耗计算表达式,只适用于收发仰角较小的状态,当收发仰角较大时,不再适用于分析非直视紫外光散射通信。而在实际应用中当通信距离小于1 km时,通常采用路径损耗简化公式[13]
L=ξrα (3) 其中,
ξ 是路径损耗因子,α 是路径损耗指数,其都是与收发仰角有关的参数。2.2 无线紫外光多跳中继节点随机分布结构模型
本文研究的紫外光多跳通信结构模型,考虑1维N跳网络结构且每跳的距离是随机性的,其无线紫外光多跳中继节点随机分布模型如图2所示,当
r1=r2=···=rN=d/N 时,即为等距离分布。紫外光多跳中继通信系统有一个源节点S,一个目的节点D, N–1个中继节点Ri (i=1, 2, ···, N–1),且Ri随机分布在S到D的距离范围内。假设所有节点采用半双工通信方式,考虑经典N跳时分解码转发协议,每个中继节点Ri接收Ri–1发送的信息,并解码转发到Ri+1节点。假设中继节点位置是独立随机变量,并设Xi是第i个中继节点在S到D间的随机位置,则Xi的概率密度函数为[14]
f(Xi)={1rδ, r(i−δ2)≤Xi≤r(i+δ2)0,其他 (4) 其中,r=d/N是等分距离,d是S到D的实际距离,
δ∈[0,1] 是随机偏移范围,其表征中继节点位置的随机性或者不确定性。定义
ri=Xi−Xi−1(i=2,3,···,N−1) ,特别地,r1=X1 ,rN=d−XN−1 ,则ri的累积分布函数表示为对于i=1或N时,
F(ri)={0,ri≤r(1−δ2)1rδ(ri−r(1−δ2)), r(1−δ2)≤ri≤r(1+δ2)1,ri≥r(1+δ2) (5) 对于i=2, 3, ···, N–1时,
F(ri)={0,ri≤r(1−δ)12(1rδ)2[ri−r(1−δ)]2, r(1−δ)≤ri≤r12(1rδ)2[r(1+δ)−ri]2, r≤ri≤r(1+δ)1,ri≥r(1+δ) (6) 3. 无线紫外光多跳中继节点随机分布最优跳数分析
根据紫外光NLOS单次散射模型,其紫外光通信在量子极限条件下的信噪比为[12]
γSNR=ηfηrPtλ2hcBL=μξ−1r−α (7) 其中,
μ=ηfηrPtλ2hcB ,ηf 和ηr 分别表示滤光片透过率和光电倍增管(Photo Multiplier Tube, PMT)探测效率,λ 是紫外波长,h是普朗克常数,c是光速,B=Kec2π 是紫外光通信信道带宽。利用香农公式可以计算出紫外光NLOS通信的信道容量[12],则紫外光单跳通信的频谱效率为
ηsh=log2(1+μξ−1d−α) (8) 在源节点到目的节点等距离分布N跳通信传输时,假设在任何时间点上只有一个节点进行传输,即在接收端无干扰,且每个节点在1/N时间传输相同的信息量,则每跳频谱效率是单跳通信的N倍,其等距离分布的频谱效率为
ηeq=1Nlog2(1+μξ−1(dN)−α) (9) 从式(9)可以看出频谱效率与跳数和收发仰角有关,因此研究使用近似理想路径路由计算方法[15],通过最大化频谱效率得到紫外光多跳中继通信系统节点等距离分布下的最优跳数近似表达式为
Nop=argmaxηeq≈[(2ε−1γ)1/α]+ (10) 其中,
ε=α+w(−αe−α)ln2 是仅取决于路径损耗指数的常数,w(⋅) 是郎伯W函数的主分支[16],γ=μξ−1d−α 是单跳情况下的接收信噪比。从式(10)可以看出最优跳数受到收发仰角的影响,在基于等距离分布的分析下,对中继节点随机分布时最优跳数进行了分析。在节点随机分布时,系统性能将取决于N跳中最长的一跳[17],则在此情况下频谱效率度量将是最长一跳距离上的平均值,如式(11)所示
¯η=Ermax[1Nlog2(1+μξ−1r−αmax)] (11) 其中,
rmax=maxi=1,⋯,Nri ,E[⋅] 是期望算子。为了求解节点随机分布下最优跳数值,需要求得
¯η 的闭合表达式,由式(5)和式(6)的累积分布函数可得r≤rmax≤r(1+δ) (12) 对式(11)应用Jensen不等式
E[f(x)]≥f(E[x]) ,则式(11)变换如式(13)所示E[log2(1+μξ−1r−αmax)]≥log2(1+μξ−1(E[rmax])−α) (13) 根据式(13),联合式(11)和式(12)求解得到
¯η 的上下界1Nlog2(1+μξ−1(dN(1+δ))−α)≤¯η≤1Nlog2(1+μξ−1(dN)−α) (14) 根据等距离分布最优跳数近似值的分析过程,求解式(14)的
¯η 下界最大化,即节点随机分布的最优跳数近似求解式如式(15)所示N′op≈[(2ε−1γ′)1/α]+ (15) 其中,
γ′=μξ−1d−α(1+δ)−α 是最大距离单跳情况下节点随机分布的接收信噪比。在节点随机分布情况下,通过式(15)求解得到的最优跳数值是源节点到目的节点多跳中继通信中的最大值。当
δ=0 时,式(15)等于式(10),最优跳数值达到最小值,即紫外光通信链路的频谱效率有最大值。4. 仿真结果及分析
4.1 仿真实验参数设置
通常在车队中车辆与车辆之间的距离根据车速应保持在30~100 m,而整个车队的最大距离不超过1~3 km[18]。基于此参数规定和最优跳数的分析,对节点等距离分布和随机分布的两种情况进行了仿真分析。其仿真实验的主要参数见表1。
表 1 系统主要仿真参数参数 数值 紫外波长 260 nm PMT探测效率 0.3 滤光片透过率 0.6 吸收系数 0.802×10–3 m–1 米氏散射系数 0.284×10–3 m–1 瑞利散射系数 0.266×10–3 m–1 普朗克常数h 6.6×10–34 4.2 节点等距离分布最优跳数仿真分析
在车队中车辆等间隔匀速运动时,通常满足节点等距离分布状态,即
δ=0 。根据不同收发仰角下ξ 和α 的取值分析[14],在Pt=30 mW, d=500 m和等距离分布情况下,本文对βT<βR, βT=βR和βT>βR 3种不同状态的收发仰角的单跳通信、多跳通信和最优跳通信进行了仿真,在d=500 m的多跳通信中,设定最大通信跳数为9跳,即车队有10辆车辆,其他仿真参数如表1所示,分析了3种通信方式的性能。从图3、图4和图5可以看出,当发射功率大于18 mW时,针对不同的收发仰角求得的最优跳数值都要比单跳通信和9跳通信获得较好的通信传输能力。另外,对比分析了相同最优跳数值下的不同收发仰角的频谱效率。从图6(a)和图6(b)可以看出,在相同最优跳数值下,紫外光通信的收发仰角对通信传输能力有着较大的影响。并且在紫外光多跳中继通信系统中,当有相同跳数时,使用小发射仰角和大接收仰角,能够使紫外光多跳通信系统获得更好的通信性能。
基于等距离分布模型的分析结果,将本文等距离分布下的最大频谱效率计算方法与最优能量计算方法进行对比分析。在βT<βR的紫外光几何结构配置下,不同方法下最优跳数和通信传输能力的对比情况如图7和图8所示。从图7可以看出两种方法的效果能够基本达到一致。当发射仰角固定时,增大接收仰角角度,其最优跳数随着通信距离的增加,最大频谱效率计算方法比最优能量计算方法的跳数值多一个数量级。
图8是根据图7中d=600 m时的最优跳数的分界点值的性能对比。此时,最大频谱效率计算方法最优跳数为6,最优能量计算方法最优跳数为5。从图8可以看出,当采用小功率传输时,最大频谱效率计算方法的通信传输能力优于最优能量计算方法,同时也达到节约功率的需求。在等距离分布模型下,当源节点到目的节点的通信距离确定时,根据无线紫外光通信的收发仰角得到适当的中继数,能够使整体通信传输能力达到最大。
4.3 节点随机分布最优跳数仿真分析
当车队在行驶中根据路况和调配信息,随时调整车速,此过程导致车队处于非匀速状态,不再满足等距离分布。本节对节点随机分布下的最优跳数进行了仿真分析。主要仿真参数如表1所示,在发射功率Pt=30 mW, S到D的距离d=500 m下,对比分析了不同随机偏移范围下的不同收发仰角的频谱效率与跳数的关系。从图9(a)、图9(b)、图9(c)和图9(d)可以看出,在紫外光多跳通信系统中,随着
δ 的增加系统总体性能呈下降趋势。并且不同收发仰角在不同随机偏移范围下,都存在一个使总体系统的频谱效率下界达到最大值的最优跳数值。通过图9进一步可以看出在紫外光中继通信系统中,使用小发射仰角和大接收仰角系统配置,能够使紫外光多跳通信系统获得更好的传输能力。为进一步说明随机分布模型的实际应用,本文在Pt=30 mW和
δ=0.2 下,对比分析了βT<βR和βT>βR下的收发端距离变化的频谱效率与跳数的关系,如图10所示。从图10可以看出,频谱效率随着跳数的增加存在最大值,并且随着S到D距离的增加,当达到最优跳数时,频谱效率不再随着跳数的增加有较大的变化。进一步说明当紫外光长距离通信时,并不是跳数越多其通信性能就越好。5. 结束语
本文针对车队中车辆在等距离和随机分布状态下的最优跳数进行了研究。基于非直视紫外光单次散射模型、信道容量和路径损耗,依据使频谱效率最大化原则,得出计算收发仰角与频谱效率的近似关系表达式。通过分析等距离分布最优跳数,求得随机分布的最优跳数近似表达式。仿真结果表明,收发仰角影响着紫外光多跳中继通信系统的最优跳数。不同随机偏移范围和不同收发仰角都对应特定的最优跳数,与最优能量计算方法相比,最大频谱效率计算方法在发射功率小于25 mW时有更好的信息传输能力,并达到节约功率的需求。在紫外光长距离通信时,选取合适的中继数及小发射仰角和大接收仰角的几何结构配置,不仅能够提高车队间无线紫外光多跳中继通信系统的传输能力,也满足车队间保持稳定可靠的隐秘通信需求。
-
Swain S and Mohapatra D P. Genetic Algorithm-Based Approach for Adequate Test Data Generation[M]. India: Intelligent Computing, Networking, and Informatics, Springer, 2014: 453-462. 邝继顺, 刘杰镗, 张亮. 基于镜像对称参考切片的多扫描链测试数据压缩方法[J]. 电子与信息学报, 2015, 37(6): 1513-1519. Kuang Ji-shun, Liu Jie-tang, and Zhang Liang. Test data compression method for multiple scan chain based on mirror-symmetrical reference slices[J]. Journal of Electronics Information Technology, 2015, 37(6): 1513-1519. Michael C C, McGraw G E, Schatz M A, et al.. Genetic algorithms for dynamic test data generation[C]. Proceedings of the 12th IEEE International Conference on Automated Software Engineering, 1997: 307-308. 张岩, 巩敦卫. 基于稀有数据扑捉的路径覆盖测试数据进化生成方法[J]. 计算机学报, 2013, 36(12): 2429-2440. Zhang Yan and Gong Dun-wei. Evolutionary generation of test data for paths coverage based on scarce data capturing[J]. Chinese Journal of Computers, 2013, 36(12): 2429-2440. 刘向辉, 韩文报, 权建. 基于遗传策略的格基约化算法[J]. 电子与信息学报, 2013, 35(8): 1940-1945. Liu Xiang-hui, Han Wen-bao, and Quan Jian. A new lattice reduction algorithm based on genetic strategy[J]. Journal of Electronics Information Technology, 2013, 35(8): 1940-1945. Tian T and Gong D. Test data generation for path coverage of message-passing parallel programs based on co-evolutionary genetic algorithms[J]. Automated Software Engineering, 2014, 22(79): 1-32. 严韬, 陈建文, 鲍拯. 基于改进遗传算法的天波超视距雷达二维阵列稀疏优化设计[J]. 电子与信息学报, 2014, 36(12): 3014-3020. Yan Tao, Chen Jian-wen, and Bao Zheng. Optimization design of sparse 2-D arrays for Over-The-Horizon Readar (OTHR) based on improved genetic algorithm[J]. Journal of Electronics Information Technology, 2014, 36(12): 3014-3020. 巩敦卫, 任丽娜. 回归测试数据进化生成[J] . 计算机学报, 2014, 37(3): 489-499. Gong Dun-wei and Ren Li-na. Evolutionary genetation of regression test data[J]. Chinese Journal of Computers, 2014, 37(3): 489-499. 曹凯, 陈国虎, 江桦, 等. 自适应引导进化遗传算法[J]. 电子与信息学报, 2014, 36(8): 1884-1890. Cao Kai, Chen Guo-hu, Jiang Hua, et al.. Guided self-adaptive evolutionary genetic algorithm[J]. Journal of Electronics Information Technology, 2014, 36(8): 1884-1890. 徐宗本, 高勇. 遗传算法过早收敛现象的特征分析及其预防[J]. 中国科学: E 辑, 1996, 26(4): 364-375. Xu Zong-ben and Gao Yong. The analysis and prevention of genetic algorithm premature convergence[J]. Science in China (Series E), 1996, 26(4): 364-375. Suzuki J. A Markov chain analysis on simple genetic algorithms[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1995, 25(4): 655-659. 何大阔, 王福利, 贾明兴. 遗传算法初始种群与操作参数的均匀设计[J]. 东北大学学报: 自然科学版, 2005, 26(9): 828-831. He Da-kuo, Wang Fu-li, and Jia Ming-xing. Uniform design of initial population and operation parameters of genetic algorithm[J]. Journal of Northeastern University (Natural Science), 2005, 26(9): 828-831. Xuan J and Monperrus M. Test case purification for improving fault localization[C]. FSE 2014 Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering, New York, NY, USA, 2014: 52-63. McMinn P. Evolutionary search for test data in the presence of state behaviour[D]. [Master dissertation], University of Sheffield, 2005: 1-242. Harman M and McMinn P. A theoretical and empirical study of search-based testing: local, global, and hybrid search[J]. IEEE Transactions on Software Engineering, 2010, 36(2): 226-247. Arcuri A. It does matter how you normalise the branch distance in search based software testing[C]. Proceedings of the 3rd International Conference on Software Testing, Verification and Validation, Pairs, France, 2010: 205-214. Xie X Y, Xu B W, Shi L, et al.. Genetic test case generation for path-oriented testing[J]. Journal of Software, 2009, 20(12): 3117-3136. 雷英杰, 等. MATLAB 遗传算法工具箱及应用[M]. 西安: 西安电子科技大学出版社, 2005: 60-61. Lei Ying-jie, et al.. Application of Genetic Algorithm ToolBox Based on MATLAB[M]. Xian: Xidian University Publisher, 2005: 60-61. 刘晓霞. 种群规模对遗传算法性能影响的研究[D]. [硕士论文], 华北电力大学, 2010: 1-37. Liu Xiao-xia. A research on population aize impaction on the performance of genetic algorithm[D]. [Master dissertation], North China Electric Power University, 2010: 1-37. -
计量
- 文章访问数: 1261
- HTML全文浏览量: 75
- PDF下载量: 427
- 被引次数: 0