认知无线电网络信道交汇加速算法

田宏伟，王宜怀

(1. 苏州大学 应用技术学院，江苏 苏州 215325; 2.苏州大学 计算机科学与技术学院，江苏 苏州 215006)



认知无线电网络信道交汇加速算法

田宏伟1，王宜怀2

(1. 苏州大学 应用技术学院，江苏 苏州 215325; 2.苏州大学 计算机科学与技术学院，江苏 苏州 215006)

在认知无线电网络中，二级用户需要首先发现邻居信息并形成通信链路，被称为信道交汇过程。有很多的信道跳频算法，但它们的目标是要形成一个集合点图案或保证在有限时间内会合。在这项研究中，提出了一种算法，以加快与多个用户认知无线电网络的交汇过程，即最近最少使用策略。其基本思路是减少已经交汇用户之间交汇的重复。为了评估所提出的方案，进行了大量的实验。

认知无线电网络;信道跳频;盲信道交汇;信息共享;交汇时间

0 引言

由于各种无线设备的指数增长和固定频谱分配规则，一些频谱已经人满为患，而多数频谱未利用或者利用率不高。为了缓解频谱资源使用不平衡的问题，利用已经提出的认知无线电技术[1-2]，使二级用户能有效地利用宝贵的频谱资源。

在认知无线电网络(Cognitive Radio Networks, CRNS)[3]中，二级用户甚至事先不知道彼此的存在。在他们可以交换信息之前，应该检测彼此的存在来建立通信链路。信道交汇是二级用户的两个或更多的无线电相交并且建立常用信道上的一条链路的基本过程[4]。信道跳频(Channel Hopping)技术[5]是盲信道交汇[6]最具代表性的技术之一。利用信道跳频技术，认知无线电网络的每个用户选择一组信道和信道中的跳序列与潜在的邻居交汇。如果所有用户都具有相同的可用信道，则称之为对称模型;如果用户有不同的可用频道，则称之为非对称模型。

基于认知无线电网络有许多新的算法。信道交汇协议可以使用随机算法生成序列。一个平凡的信道跳频算法是可以让每个用户以一个绝对随机的方式决定它自己的跳频序列。

有一种自适应的多元交汇控制信道的算法[7]，其基本思想是对主用户干扰较低的信道在信道跳频序列中有较大的使用机会。随机算法的缺陷是，它们不能保证用户在有限的时间内交汇。有几种算法在一般情况下可以保证交汇。环行走(Ring-walk，RW)算法[8]保障不对称模型的交汇以及一些附加条件，比如用户不同的标识符和网络规模的知识。跳转停留(Jump-stay，JS)算法[9]是另一个可以保证交汇的基于模块化的算法。跳转停留算法的基本思想是产生循环信道跳频序列，每一轮由一个跳跃模式和停留模式组成。用户在跳跃模式时可以在可用信道上跳跃，而停留模式时只能在特定信道停留。

本项研究专注于对认知无线电网络两个或多个用户交汇的信道跳频算法进行改进：

(1)提出了一种方法来显著提高信道跳频的交汇性能；

(2)使用普通的随机算法和现有的交汇算法实现更快的交汇；

(3)进行了大量的模拟以评估所提出的算法，推导这些算法交汇所需要的时间。这两种实验的结果表明，使用本文提出的算法，性能得到明显改善。

1 研究的动机

用一个简单的例子来说明算法的原理和加速交汇的过程。如图1所示，有三个用户U1，U2，U3，这三个用户有6个常用信道，这意味着当他们存在于相同的跳频信道上时可以直接通信。每个用户独立地采用同一种跳频算法来生成信道跳频序列。假设两个用户交汇之后，他们将在接下来的几个时隙里交换彼此的跳频序列，在最初的情况下，三个用户用他们自己的方式跳频。当U2在信道4时隙1和U3第一次交汇后，他们会持续跳频直到U1和U2在通道4时隙9交汇，然后U1和U3将在下一时隙交汇。因此，这三个用户的交汇时间(Time to Rendezvous, TTR)为11个时隙。

图1 三个用户的积极性的例子

在加速的情况下，一旦U2和U3在信道4时隙1第一次交汇，他们将改变其跳频序列，以保证他们不会在任何时隙的一段时间跳频到同一信道上。例如，U2改变了时隙4和时隙5的序列，然后，当U1和U2交汇在时隙4中时，他们所有的交汇时间从11减少到6。

2 加速交汇算法

2.1 系统模型

本文认为一个认知无线电网络由N(N≥2)个二级用户组成，他们可以用集合N={u1，…，uN}表示。假定系统是有时隙的且所有的时间间隙都具有相同的和固定的长度。许可频谱被划分成M(M≥1)个非重叠的信道，用M={c1，…，cM}表示。假设网络中的所有次级用户知道所有这些信道，并且每个用户配备了一个单一的认知无线电。考虑到频谱的异质性，让Mi⊆M表示组UI的可用信道。

计划利用现有的信道跳频算法。如果用户i和用户j跳上同一时隙的同一信道，那么他们就交汇了。加速算法是集合了交汇的用户，每个用户都作为一个无线电的整体[10]。因此，他们可以尝试与其他用户交汇成一组。其工作原理如下：

然而，我们似乎应当在惊恐中保持一份冷静，向上述逻辑推理的起点回溯，就法律监督是否影响审判机关在民事诉讼中的独立地位作出事实上的判断而不仅仅是依靠理论的推演。只要查阅一下抗诉案件维持原审结果的裁判文书，就能知晓检察机关对民事诉讼的法律监督主要是程序上的启动权。如果一定要说法律监督会对审判机关在民事诉讼中的审判造成影响，那么这种影响主要体现在抗诉案件裁判文书说理性的增强，而裁判文书的说理恰恰是对个案公正的论证，与审判独立的目标相契合。

(1)所有用户使用相同的信道跳频算法来生成他们的序列，并从不同的时间段独立启动通道。

(2)当任两个用户交汇时，他们将从接下来的时隙中分享彼此的跳频序列信息[11]。定义信息长度为L，然后他们使用最近最少使用(Least Recently Used Strategy，LRUS)算法生成L接下来的新的时隙序列，并在这个时隙通知接触方法的变化。

(3)当新的序列被完成时，每个用户都使用由信道跳频算法生成的默认跳频序列来尝试交汇。

2.2 最近最少使用算法

当任何两个用户在某个时隙中交汇时，他们将在下一个时隙中共享跳频序列信息。使用最近最少使用算法以减少重复交汇来加速与其他用户的交汇。在这个算法中，仅仅改变了用户即将再次交汇的这些时隙的信道。基本要求是在这些时隙中他们不会跳频到同一信道上。其工作原理如下：

(2)拥有更多可用信道的用户会被选择改变他们的序列，这将使序列更加灵活。如果他们具有相同数量的可用信道就可以被随机选择。

(3)在这些选定的时隙中重新排序所有通道。从第一个标记的时隙，选择最近没有做过跳频信道的信道。

(4)如果剩下的选定的信道都是相同的，那么将用信道跳频算法来生成在这些特定的时隙与之前的信道相同的新的序列。

2.3 分析

当任意两个用户在某些时段交汇时，他们有一定的可能性跳频到同一个通道上，可能性的大小由他们的可用信道的数量和信道跳频的方式决定。任何用户交汇之后他们将会成为一个整体，并尝试与其他用户交汇。因此，如果在以下的任一个时隙中，交汇过的用户在不同的信道上跳频，他们将有更多的机会与其他用户交汇。

3 模拟

用C++编写的模拟器来评估本文的算法和协议的性能。在模拟中，选择在对称和非对称的情况下都有效的随机算法作为序列生成算法。

如图2所示，在对称情况下，交汇的时间随着L=20的用户的增加而增加，并且所有用户都具有6个共同可用的信道。但是，最近最少使用算法大大降低了交汇需要的时间。

图2 对称情况下，总时间与用户的数量(L= 20)

如图3所示，在对称的情况下，随机算法和最近最少使用算法之间交汇的时间比是低的。而当L很小的时候，比率随着L的增大而减小，当L到达一个定值时，比率也会获得一个动态稳定值。

图3 对称情况下，时间比率与交汇信息长度(N=10)

如图4所示，在非对称情况下，交汇的时间随着L=20的用户数的增加而增加，并且所有用户都具有至少3个共同可用的信道。但是，最近最少使用算法大大降低了交汇需要的时间。

如图5所示，在非对称的情况下，随机算法和最近最少使用算法之间交汇的时间比是低的。而当L很小的时候，比率随着L的增大而减小，当L达到一个定值时，比率也会获得一个动态稳定值。

图4 非对称情况下，总时间与用户数的数量(L=20)

图5 非对称情况下，时间比率与交汇信息长度(N=10)

4 结论

本文提出了一种算法，以加快认知无线网络交汇的过程，其关键思想是减少已交汇用户之间的重复交汇，提出最近最少使用算法用来改进交汇。模拟结果表明了该算法的性能。

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

[2] 滕志军, 杨旭, 韩雪. 基于多次博弈的认知无线电频谱动态分配算法[J]. 电子技术应用, 2012,38(7):95-98.

[3] AKYILDIZ I F, LEE W Y, CHOWDHURY K R. CRAHNs: cognitive radio ad hoc networks[J]. Ad Hoc Networks, 2009,7(5):810-836.

[4] 刘权,赵光胜,王晓东,等.认知无线电网络信道交汇研究综述[J].软件学报,2014,25(3):606-630.

[5] 王必烈,陈瑾,龚玉萍,等.认知无线网络中基于信道跳频的盲交会技术[J].军事通信技术,2014, 35(3): 26-33.

[6] THEIS N C, THOMAS R W, DASILVA L A. Rendezvous for cognitive radios[J]. IEEE Transactions on Mobile Computing, 2010, 10(2):216-227.

[7] CORMIO C, CHOWDHURY K R. An adaptive multiple rendezvous control channel for cognitive radio wireless ad hoc networks[C]. IEEE International Conference on Pervasive Computing and Communications Workshops, 2010:346-351.

[8] Liu Hai, Lin Zhiyong, Chu Xiaowen, et al. Ring-walk based channel-hopping algorithms with guaranteed rendezvous for cognitive radio networks[C]. IEEE/ACM International Conference on Green Computing and Communications & International Conference on Cyber, Physical and Social Computing, 2010:755-760.

[9] Lin Zhiyong, Liu Hai, Chu Xiaowen, et al. Jump-stay based channel-hopping algorithm with guaranteed rendezvous for cognitive radio networks[J]. Proceedings of IEEE INFOCOM, 2011, 34(17):2444-2452.

[10] Yu Lu, Liu Hai, LEUNG Y W, et al. Multiple radios for effective rendezvous in cognitive radio networks[C]. 2013 IEEE International Conference on Communications (ICC), 2013, 14(9):2857-2862.

[11] Jia Juncheng, Zhang Qian. Rendezvous protocols based on message passing in cognitive radio networks[J]. IEEE Transactions on Wireless Communications, 2013,12(11): 5594-5606.

Rendezvous accelerating algorithm in cognitive radio networks

Tian Hongwei1, Wang Yihuai2

(1. Applied Technology College of Soochow University, Suzhou 215325, China;2. School of Computer Science and Technology, Soochow University, Suzhou 215006, China)

In cognitive radio networks, secondary users need firstly to discover neighbor information and establish a communication link through rendezvous. There are several channel hopping algorithms to achieve rendezvous, yet these algorithms aim to form a set point pattern or guarantee joining together in a limited time. An algorithm is proposed in this research to accelerate rendezvous in cognitive radio networks with several users, and the new algorithm is least recently used strategy(LRUS) which is used to reduce the repetition of rendezvoused users. A lot of experiments were carried out to evaluate this algorithm.

cognitive radio networks; channel hopping; blind rendezvous; information sharing; time to rendezvous

TP393

A

10.19358/j.issn.1674- 7720.2017.12.018

田宏伟，王宜怀.认知无线电网络信道交汇加速算法[J].微型机与应用，2017,36(12)：61-63，67.

2016-12-27)

田宏伟(1981-)，男，硕士，高级工程师，主要研究方向：嵌入式系统应用。

王宜怀(1962-)，男，博士，教授，博士生导师，主要研究方向：嵌入式系统与传感网技术。