基于布谷鸟搜索算法的认知车载网络频谱分配方法

刘彩丽，肖海林

(桂林电子科技大学 信息与通信学院，广西 桂林　541004)



基于布谷鸟搜索算法的认知车载网络频谱分配方法

刘彩丽，肖海林

(桂林电子科技大学 信息与通信学院，广西 桂林541004)

针对认知车载网络频谱分配中网络吞吐量低的问题，提出一种基于布谷鸟搜索算法的频谱分配方法。该方法考虑了认知车载网络中授权频段可用时长的差异性，将最大化网络吞吐量转化为求最大化可用时长内认知车载用户成功完成的总数据量，建立目标函数，并将频谱分配变量映射为布谷鸟鸟巢位置，采用布谷鸟搜索算法求解。数值分析表明，基于布谷鸟搜索算法的频谱分配方法所获得的网络吞吐量高于基于遗传算法的频谱分配。

认知车载网络；布谷鸟搜索算法；频谱分配；吞吐量

随着车辆道路安全服务需求的不断增长，车载自组织网络的可用频谱资源变得尤为紧缺，而认知无线电能解决这一问题[1]。认知车载网络是将认知无线电(cognitive radio，简称CR)技术应用到车载自组织网络(vehicular ad hoc network，简称VANET)的新型车载网络[2]。在认知车载网络(CR-VANET)中，认知车载用户可以“伺机”接入空闲授权频谱，以缓解车载网络频谱资源的匮乏，提高频谱利用率。

频谱分配是认知无线电的关键技术之一[3]，近年来国内外学者对其进行了大量研究。文献[4]把频谱分配问题抽象成图着色问题，提出了基于图论着色理论的频谱分配算法，但该算法存在不公平性，且时间开销较大。文献[5]以实现最大化网络效益为目标，将频谱分配问题归化为优化问题，采用遗传算法(genetic algorithm，简称GA)求解，减少了时间开销。文献[6]提出了基于遗传算法的多目标频谱分配方法，该方法能使认知用户在频谱分配过程中实现最大网络效益的同时获得最大比例公平，比图论着色理论的频谱分配更具优越性，但遗传算法难以克服易陷入局部最优的缺点。

上述方法所应用的认知无线网络均考虑的是静态的认知用户，并不适用于具有动态认知用户的车载网络。文献[7]将认知用户实体化为高速行驶的车辆，根据实际的交通状况模拟网络拓扑随时间快速变化的车载网络场景，运用基于协作最大化带宽总和算法进行频谱分配，实现网络吞吐量的最大化。文献[8]研究了认知车载网络中基于QoS保障的频谱共享，将多认知小区间的频谱分配构建为基于广义纳什讨价还价解模型。文献[9]针对认知车载网络中授权频段的动态特性，采用基于部分可观测马尔科夫决策过程的机会式频谱接入，认知车载用户选择空闲概率最大的授权频段进行感知及接入，使自身吞吐量最大化。文献[10]根据车载用户的速度和行驶方向建立一种频谱资源分配框架，将频谱分配问题转化为最大化网络可用频谱资源利用率的优化问题，并采用分支界定算法求解，以降低复杂度，但其未考虑由认知车载的移动而导致的授权频段在空间上存在的空闲。文献[11]研究了城市场景下认知车载网络中授权频谱在时间和空间上的空闲持续时长分布，根据各个授权频段不同的空闲时长，提出了一种基于博弈论的频谱接入方法，但该方法未解决多个车载用户接入同一授权频段可能造成的干扰问题。

为此，以最大化网络吞吐量为准则，提出一种基于布谷鸟搜索算法的频谱分配方法，消减车载用户间的同频干扰。

1　系统模型

1.1认知车载网络模型

考虑的CR-VANET模型如图1所示[10-12]。网络包括K个主用户、M个认知车载用户和若干个路边单元。其中，主用户按泊松点过程随机分布。网络共有N(N≥K)个授权频段，每一个授权频段对应一个信道。认知车载用户已知每个授权频段上的主用户平均密度和主用户的频谱使用统计特性，且工作在同一频段的主用户具有相同的系统特性和相同的频谱使用统计特性，如频谱占用和空闲的持续时间。假设认知车载用户已完成频谱感知获得可用频谱，并将相关信息发送给路边单元，由路边单元进行频谱分配。

图1　认知车载网络模型Fig.1　CR-VANET model

在认知车载网络中，由于车载的移动性，认知车载用户的状态可分为3种：1)处于空闲频段的覆盖范围之内；2)处于被占用频段的覆盖范围之内；3)处于被占用频段的覆盖范围之外。显然，授权频段是否空闲不仅取决于是否被主用户占用，还因车载进入或离开主用户的通信覆盖范围而改变。因此，对于认知车载，授权频段存在时间和空间上的空闲[11]。

1.2频谱可用性建模

主用户的频谱使用统计特性为主用户占用和离开授权频段的转换过程，主用户占用某一频段进行通信时，处于该主用户覆盖范围之内的认知车载用户不能使用该频段，以避免对主用户造成干扰。根据认知网络中广泛使用的频谱使用统计模型，主用户占用和离开授权频段i的持续时间服从参数为λbusy,i、λidle,i的指数分布：

Tidle,i～exp(λidle,i)，Tbusy,i～exp(λbusy,i)。

(1)

为避免对主用户造成干扰，认知车载用户只有当授权频段在时间或空间上空闲时，才可以使用，否则，不可使用。因此，对于认知车载用户，授权频段的可用性综合为2种状态：可用(OFF)和不可用(ON)。2种状态转换如下：

1)ON→OFF。认知车载用户驶出正占用授权频谱的主用户的保护区域或主用户停止占用。

2)OFF→ON。认知车载用户驶入正占用授权频谱的主用户的保护区域或主用户开始占用。

授权频段“OFF”状态和“ON”状态之间的转换满足马尔科夫过程，因此，授权频段的可用性可建模为一个连续时间马尔科夫链。授权频段i的可用状态持续时长服从参数为λOFF,i的指数分布[12]：

TOFF,i～exp(λOFF,i)。

(2)

其分布参数为：

(3)

假设授权频段i的可用时长为TOFF,i，当认知车载用户接入到频段i时，频段i的可用时长已经持续了时间t，则授权频段i的剩余可用时长不小于T(T<)的概率为：

(4)

显然，Pi(T)越大，认知车载用户在[t，t+T]时间段内能够成功完成数据传输的概率越大，则越有利于车载用户进行数据传输。

1.3频谱分配优化问题建模

认知车载用户m在频段i上的传输速率为：

(5)

其中：w为每个授权频段的带宽；ψ为认知车载用户的发射功率；hm,i为认知车载用户m在频段i上的信道增益；σ2为噪声方差；i∈1,2,…,N，m∈1,2,…,M。

当认知车载用户在t时刻接入频段i时，只有频段i的可用时长至少达到T，其在[t，t+T]时间内的数据传输才不会中断。因此，综合考虑授权频段的可用时长和传输速率，在时长T内，认知车载用户每次接入频段能够成功完成的数据量可表示为：

(6)

其中：xm,i为0-1频谱分配变量，其为1时表示频段i分配给了认知车载用户m，为0时表示频段i未分配给用户m；Pi(T)为授权频段i的可用时长不小于T的概率。

(7)

其中：Rm、Rk分别为认知车载用户m、k的传输半径；dm,k为认知车载用户m、k之间的距离。

只有当频段i为认知车载用户m的可用频段时，该频段才可被分配给认知车载用户m，因而约束条件(8)表明，若频段i不为认知车载用户m的可用频段，则xm,i=0。此外，采用认知车载用户之间的地理距离和各自的传输半径来判断两者同时使用频段i是否产生干扰。约束条件(9)表明，当认知车载用户m与认知车载用户k的距离小于两者传输半径之和时，只能将频段i分配给这2个用户中的一个。

上述约束优化问题为非线性0-1规划问题，此类问题属于NP难问题[14]，直接进行求解较为困难，因此，采用布谷鸟搜索算法对该问题进行求解。

2　基于布谷鸟算法的频谱分配方法

2.1布谷鸟搜索算法

布谷鸟搜索(cuckoosearch，简称CS)是一种源于自然界中布谷鸟孵育寄生行为和Lévy飞行搜索原理开发的一种新型智能算法，其探索解空间的性能高，能灵活地跳出局部极值，并且结构十分简单，控制参数较少，参数的调整和设置方便，易于实施，在非线性规划问题求解方面得到广泛应用[15-17]。CS算法的个体更新方式有2种：

1)通过Lévy飞行。根据Lévy飞行模式，布谷鸟寻窝路径和位置的更新公式为：

(10)

2)通过一个固定的发现概率ε。用一个随机数r与发现概率ε对比，以确定是否更新鸟巢位置，更新公式为：

(11)

在实际的优化中，鸟巢位置用向量Xj=[xj,1,xj,2,…,xj,d]表示所有优化变量的d维有效取值空间，鸟巢位置的适应度值则代表优化变量取不同值所对应的目标函数[16]。

2.2种群编码

其中：Xj为第j个鸟巢位置，其对应一种可能的频谱分配策略，j∈1,2,…,P；P为种群数。

由于频谱分配变量的0-1特性，需采用二进制CS算法。在二进制CS算法中，所求解通过保留基本的CS算法中的更新公式对更新位置进行二进制编码，即鸟巢位置矢量仍属于实属空间，而所求解属于二进制空间[17]。鸟巢位置进行二进制编码的公式为：

(12)

基于CS算法的频谱分配步骤为：

1)根据给定的可用频谱矩阵确定优化维数D，并设定最大迭代次数。

3)计算每个鸟巢位置的适应度值，选出最大的适应度值，并记录其对应的鸟巢位置Xbest，Xbest即为当前最优鸟巢位置。

5)按照式(11)更新鸟巢位置，计算每个鸟巢位置的适应度值，再与步骤4)中的每个鸟巢位置对应的适应度值比较，保留较大适应度值对应的鸟巢位置，记录此时最大的适应度值对应的鸟巢位置X″best。

6)判断是否达到预先设定的最大迭代次数。若是，则输出X″best，终止迭代；否则，迭代次数加1，返回至步骤4)，继续迭代。

3　仿真实验

仿真实验中，可用频谱矩阵L和车载用户间的距离按照文献[4]产生，主用户保护半径Ri为2 km，车载用户平均速度为4 m/s，发射功率ψ为50 mW；频段带宽w为1 kHz，参数λidle,i和稳态概率ωbusy,i均为[0,1]上随机数，信道增益hm,i服从均值为1的瑞利分布，每个频段上的主用户平均密度ρp,i均为1 km-2，噪声功率σ2为10-5W，时长T为1 s。最大迭代次数为150，ε=0.25，GA算法中交叉概率为0.8，变异概率为0.01。

图2为N=8、M=10时本频谱分配方法的收敛曲线。从图2可看出，种群数为P=20时，由于种群数多样性偏低，算法发生早熟现象，随着种群数的增大，本方法收敛得更快，在P=60和P=100时，体现出良好的收敛性能。

图2　N=8、M=10时本方法的收敛曲线Fig.2　The convergence curve of the proposed method when N=8 and M=10

当N=18、M=20时，本方法的收敛曲线如图3所示。从图3可看出，当用户和频谱数量增大后，方法仍具有较好的收敛性能，表明了本方法的优越性。

图3　N=18、M=20时本方法收敛曲线Fig.3　The convergence curve of the proposed method when N=18 and M=20

图4为P=20、N=8、M=10时进行30次相同参数的仿真结果。从图4可看出，基于CS算法比基于GA算法的频谱分配方法所得到的网络吞吐量高。

图4　P=20、N=8、M=10时不同实验次数下的吞吐量Fig.4　The throughput in different numbers of test when P=20, N=8 and M=10

图5为P=20、N=18、M=20时进行30次相同参数的仿真结果。从图5可看出，本方法所得的网络吞吐量均高于基于GA算法的频谱分配方法。

图5　P=20、N=18、M=20时不同实验次数下的吞吐量Fig.5　The throughput in different numbers of test when P=20, N=18 and M=20

4　结束语

针对认知车载网络中的可用频谱资源，提出基于布谷鸟搜素算法的频谱分配方法。该方法以最大化网络吞吐量作为频谱分配的优化目标函数，实现可用频谱在认知车载用户间分配时获得最大网络吞吐量。仿真结果表明，本方法使网络吞吐量得到提高。

[1]MITOLA J I,MAGUIRE G Q.Cognitive radio:making software radios more personal[J].IEEE Personal Communications,1999,6(4):13-18.

[2]FELICE M D,DOOST-MOHAMMADY R,CHOWDHURY K R,et al.Smart radios for smart vehicles:cognitive vehicular networks[J].IEEE Vehicular Technology Magazine,2012,7(2):26-33.

[3]DING L,MELODIA T,BATALAMA S N,et al.Cross-layer routing and dynamic spectrum allocation in cognitive radio ad hoc networks[J].IEEE Transactions on Vehicular Technology,2010,59(4):1969-1979.

[4]PENG C,ZHENG H,ZHAO B Y.Utilization and fairness in spectrum assignment for opportunistic spectrum access[J].Mobile Networks and Applications,2006,11(4):555-576.

[5]WEN K,FU L,LI X.Genetic Algorithm Based Spectrum Allocation for Cognitive Radio Networks[M].Germany:Pringer Berlin Heidelberg,2011:693-700.

[6]姚再英，黄玉清.基于多目标遗传算法的认知无线电频谱分配[J].西南科技大学学报，2010,25(4):82-86.

[7]张超，郭爱煌，杨曦，等.基于车载通信网络的认知无线电信道分配技术的研究[J].电子测量技术，2009,32(8):49-51.

[8]ZHANG Jianfeng.Cooperative spectrum allocation with QoS support in cognitive cooperative vehicular ad hoc networks[J].Wireless Communication Over Zigbee for Automotive Inclination Measurement China Communications,2014,11(10):49-59.

[9]张雪飞，章国安，季彦呈.CVANET中基于POMDP模型的频谱接入算法[J].电信科学，2014(9):111-115.

[10]JIANG T,WANG Z,ZHANG L,et al.Efficient spectrum utilization on TV band for cognitive radio based high speed vehicle network[J].IEEE Transactions on Wireless Communications,2014,13(10):5319-5329.

[11]CHENG N,ZHANG N,LU N,et al.Opportunistic spectrum access for CR-VANETs:a game-theoretic approach[J].IEEE Transactions on Vehicular Technology,2014,63(1):237-251.

[12]MIN A W,KIM K H,SINGH J P,et al.Opportunistic spectrum access for mobile cognitive radios[C]//2011 Proceedings IEEE INFOCOM,2011:2993-3001.

[13]GUPTA P,KUMAR P R.The capacity of wireless networks[J].IEEE Transactions on Information Theory,2000,46(2):388-404.

[14]TRAGOS E Z,ZEADALLY S,FRAGKIADAKIS A G,et al.Spectrum assignment in cognitive radio networks:a comprehensive survey[J].IEEE Communications Surveys and Tutorials,2013,15(3):1108-1135.

[15]EL-FERGANY A A,ABDELAZIZ A Y.Capacitor allocations in radial distribution networks using cuckoo search algorithm[J].IET Generation Transmission and Distribution,2014,8(2):223-232.

[16]KHODIER M.Optimisation of antenna arrays using the cuckoo search algorithm[J].IET Microwaves Antennas and Propagation,2013,7(6):458-464.

[17]BHATTACHARJEE K K,SARMAH S P.A binary cuckoo search algorithm for knapsack problems[C]//2015 International Conference on IEEE Industrial Engineering and Operations Management,2015:1-5.

编辑：翁史振

Spectrum allocation based on cuckoo search algorithm in cognitive vehicular network

LIU Caili, XIAO Hailin

(School of Information and Communication Engineering, Guilin University of Electronic Technology, Guilin 541004, China)

To improve the network throughput in spectrum allocation of cognitive vehicular network, a spectrum allocation method based on cuckoo search algorithm is proposed. The method has considered the diversity of authorized spectrum available time, formulates the network throughput maximization as total data maximization problem of cognitive vehicular users successfully transmit in the time slot to establish objective function, and uses cuckoo search algorithm to solve it by mapping the spectrum allocation variables to the position of cuckoo’s nest. Numerical simulation shows that compared with the genetic algorithm, the network throughput is improved.

cognitive vehicular network; cuckoo search algorithm; spectrum allocation; throughput

2016-01-05

广西自然科学基金重点项目(2011GXNSFD018028)；广西自然科学基金(2013GXNSFFA019004)

肖海林(1976-)，男，湖北黄冈人，教授，博士。研究方向为智能天线、MIMO移动通信系统、协同通信技术。E-mail：xhl_xiaohailin@163.com

TN929.5

A

1673-808X(2016)03-0173-05

引文格式： 刘彩丽，肖海林.基于布谷鸟搜索算法的认知车载网络频谱分配方法[J].桂林电子科技大学学报，2016,36(3):173-177.