田宏偉，王宜懷

(1. 蘇州大學(xué) 應(yīng)用技術(shù)學(xué)院，江蘇 蘇州 215325; 2.蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006)

?

認(rèn)知無(wú)線(xiàn)電網(wǎng)絡(luò)信道交匯加速算法

田宏偉1，王宜懷2

(1. 蘇州大學(xué) 應(yīng)用技術(shù)學(xué)院，江蘇 蘇州 215325; 2.蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006)

在認(rèn)知無(wú)線(xiàn)電網(wǎng)絡(luò)中，二級(jí)用戶(hù)需要首先發(fā)現(xiàn)鄰居信息并形成通信鏈路，被稱(chēng)為信道交匯過(guò)程。有很多的信道跳頻算法，但它們的目標(biāo)是要形成一個(gè)集合點(diǎn)圖案或保證在有限時(shí)間內(nèi)會(huì)合。在這項(xiàng)研究中，提出了一種算法，以加快與多個(gè)用戶(hù)認(rèn)知無(wú)線(xiàn)電網(wǎng)絡(luò)的交匯過(guò)程，即最近最少使用策略。其基本思路是減少已經(jīng)交匯用戶(hù)之間交匯的重復(fù)。為了評(píng)估所提出的方案，進(jìn)行了大量的實(shí)驗(yàn)。

認(rèn)知無(wú)線(xiàn)電網(wǎng)絡(luò);信道跳頻;盲信道交匯;信息共享;交匯時(shí)間

0 引言

由于各種無(wú)線(xiàn)設(shè)備的指數(shù)增長(zhǎng)和固定頻譜分配規(guī)則，一些頻譜已經(jīng)人滿(mǎn)為患，而多數(shù)頻譜未利用或者利用率不高。為了緩解頻譜資源使用不平衡的問(wèn)題，利用已經(jīng)提出的認(rèn)知無(wú)線(xiàn)電技術(shù)[1-2]，使二級(jí)用戶(hù)能有效地利用寶貴的頻譜資源。

在認(rèn)知無(wú)線(xiàn)電網(wǎng)絡(luò)(Cognitive Radio Networks, CRNS)[3]中，二級(jí)用戶(hù)甚至事先不知道彼此的存在。在他們可以交換信息之前，應(yīng)該檢測(cè)彼此的存在來(lái)建立通信鏈路。信道交匯是二級(jí)用戶(hù)的兩個(gè)或更多的無(wú)線(xiàn)電相交并且建立常用信道上的一條鏈路的基本過(guò)程[4]。信道跳頻(Channel Hopping)技術(shù)[5]是盲信道交匯[6]最具代表性的技術(shù)之一。利用信道跳頻技術(shù)，認(rèn)知無(wú)線(xiàn)電網(wǎng)絡(luò)的每個(gè)用戶(hù)選擇一組信道和信道中的跳序列與潛在的鄰居交匯。如果所有用戶(hù)都具有相同的可用信道，則稱(chēng)之為對(duì)稱(chēng)模型;如果用戶(hù)有不同的可用頻道，則稱(chēng)之為非對(duì)稱(chēng)模型。

基于認(rèn)知無(wú)線(xiàn)電網(wǎng)絡(luò)有許多新的算法。信道交匯協(xié)議可以使用隨機(jī)算法生成序列。一個(gè)平凡的信道跳頻算法是可以讓每個(gè)用戶(hù)以一個(gè)絕對(duì)隨機(jī)的方式?jīng)Q定它自己的跳頻序列。

有一種自適應(yīng)的多元交匯控制信道的算法[7]，其基本思想是對(duì)主用戶(hù)干擾較低的信道在信道跳頻序列中有較大的使用機(jī)會(huì)。隨機(jī)算法的缺陷是，它們不能保證用戶(hù)在有限的時(shí)間內(nèi)交匯。有幾種算法在一般情況下可以保證交匯。環(huán)行走(Ring-walk，RW)算法[8]保障不對(duì)稱(chēng)模型的交匯以及一些附加條件，比如用戶(hù)不同的標(biāo)識(shí)符和網(wǎng)絡(luò)規(guī)模的知識(shí)。跳轉(zhuǎn)停留(Jump-stay，JS)算法[9]是另一個(gè)可以保證交匯的基于模塊化的算法。跳轉(zhuǎn)停留算法的基本思想是產(chǎn)生循環(huán)信道跳頻序列，每一輪由一個(gè)跳躍模式和停留模式組成。用戶(hù)在跳躍模式時(shí)可以在可用信道上跳躍，而停留模式時(shí)只能在特定信道停留。

本項(xiàng)研究專(zhuān)注于對(duì)認(rèn)知無(wú)線(xiàn)電網(wǎng)絡(luò)兩個(gè)或多個(gè)用戶(hù)交匯的信道跳頻算法進(jìn)行改進(jìn)：

(1)提出了一種方法來(lái)顯著提高信道跳頻的交匯性能；

(2)使用普通的隨機(jī)算法和現(xiàn)有的交匯算法實(shí)現(xiàn)更快的交匯；

(3)進(jìn)行了大量的模擬以評(píng)估所提出的算法，推導(dǎo)這些算法交匯所需要的時(shí)間。這兩種實(shí)驗(yàn)的結(jié)果表明，使用本文提出的算法，性能得到明顯改善。

1 研究的動(dòng)機(jī)

用一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明算法的原理和加速交匯的過(guò)程。如圖1所示，有三個(gè)用戶(hù)U1，U2，U3，這三個(gè)用戶(hù)有6個(gè)常用信道，這意味著當(dāng)他們存在于相同的跳頻信道上時(shí)可以直接通信。每個(gè)用戶(hù)獨(dú)立地采用同一種跳頻算法來(lái)生成信道跳頻序列。假設(shè)兩個(gè)用戶(hù)交匯之后，他們將在接下來(lái)的幾個(gè)時(shí)隙里交換彼此的跳頻序列，在最初的情況下，三個(gè)用戶(hù)用他們自己的方式跳頻。當(dāng)U2在信道4時(shí)隙1和U3第一次交匯后，他們會(huì)持續(xù)跳頻直到U1和U2在通道4時(shí)隙9交匯，然后U1和U3將在下一時(shí)隙交匯。因此，這三個(gè)用戶(hù)的交匯時(shí)間(Time to Rendezvous, TTR)為11個(gè)時(shí)隙。

圖1 三個(gè)用戶(hù)的積極性的例子

在加速的情況下，一旦U2和U3在信道4時(shí)隙1第一次交匯，他們將改變其跳頻序列，以保證他們不會(huì)在任何時(shí)隙的一段時(shí)間跳頻到同一信道上。例如，U2改變了時(shí)隙4和時(shí)隙5的序列，然后，當(dāng)U1和U2交匯在時(shí)隙4中時(shí)，他們所有的交匯時(shí)間從11減少到6。

2 加速交匯算法

2.1 系統(tǒng)模型

本文認(rèn)為一個(gè)認(rèn)知無(wú)線(xiàn)電網(wǎng)絡(luò)由N(N≥2)個(gè)二級(jí)用戶(hù)組成，他們可以用集合N={u1，…，uN}表示。假定系統(tǒng)是有時(shí)隙的且所有的時(shí)間間隙都具有相同的和固定的長(zhǎng)度。許可頻譜被劃分成M(M≥1)個(gè)非重疊的信道，用M={c1，…，cM}表示。假設(shè)網(wǎng)絡(luò)中的所有次級(jí)用戶(hù)知道所有這些信道，并且每個(gè)用戶(hù)配備了一個(gè)單一的認(rèn)知無(wú)線(xiàn)電?？紤]到頻譜的異質(zhì)性，讓Mi?M表示組UI的可用信道。

計(jì)劃利用現(xiàn)有的信道跳頻算法。如果用戶(hù)i和用戶(hù)j跳上同一時(shí)隙的同一信道，那么他們就交匯了。加速算法是集合了交匯的用戶(hù)，每個(gè)用戶(hù)都作為一個(gè)無(wú)線(xiàn)電的整體[10]。因此，他們可以嘗試與其他用戶(hù)交匯成一組。其工作原理如下：

然而，我們似乎應(yīng)當(dāng)在驚恐中保持一份冷靜，向上述邏輯推理的起點(diǎn)回溯，就法律監(jiān)督是否影響審判機(jī)關(guān)在民事訴訟中的獨(dú)立地位作出事實(shí)上的判斷而不僅僅是依靠理論的推演。只要查閱一下抗訴案件維持原審結(jié)果的裁判文書(shū)，就能知曉檢察機(jī)關(guān)對(duì)民事訴訟的法律監(jiān)督主要是程序上的啟動(dòng)權(quán)。如果一定要說(shuō)法律監(jiān)督會(huì)對(duì)審判機(jī)關(guān)在民事訴訟中的審判造成影響，那么這種影響主要體現(xiàn)在抗訴案件裁判文書(shū)說(shuō)理性的增強(qiáng)，而裁判文書(shū)的說(shuō)理恰恰是對(duì)個(gè)案公正的論證，與審判獨(dú)立的目標(biāo)相契合。

(1)所有用戶(hù)使用相同的信道跳頻算法來(lái)生成他們的序列，并從不同的時(shí)間段獨(dú)立啟動(dòng)通道。

(2)當(dāng)任兩個(gè)用戶(hù)交匯時(shí)，他們將從接下來(lái)的時(shí)隙中分享彼此的跳頻序列信息[11]。定義信息長(zhǎng)度為L(zhǎng)，然后他們使用最近最少使用(Least Recently Used Strategy，LRUS)算法生成L接下來(lái)的新的時(shí)隙序列，并在這個(gè)時(shí)隙通知接觸方法的變化。

(3)當(dāng)新的序列被完成時(shí)，每個(gè)用戶(hù)都使用由信道跳頻算法生成的默認(rèn)跳頻序列來(lái)嘗試交匯。

2.2 最近最少使用算法

當(dāng)任何兩個(gè)用戶(hù)在某個(gè)時(shí)隙中交匯時(shí)，他們將在下一個(gè)時(shí)隙中共享跳頻序列信息。使用最近最少使用算法以減少重復(fù)交匯來(lái)加速與其他用戶(hù)的交匯。在這個(gè)算法中，僅僅改變了用戶(hù)即將再次交匯的這些時(shí)隙的信道。基本要求是在這些時(shí)隙中他們不會(huì)跳頻到同一信道上。其工作原理如下：

(2)擁有更多可用信道的用戶(hù)會(huì)被選擇改變他們的序列，這將使序列更加靈活。如果他們具有相同數(shù)量的可用信道就可以被隨機(jī)選擇。

(3)在這些選定的時(shí)隙中重新排序所有通道。從第一個(gè)標(biāo)記的時(shí)隙，選擇最近沒(méi)有做過(guò)跳頻信道的信道。

(4)如果剩下的選定的信道都是相同的，那么將用信道跳頻算法來(lái)生成在這些特定的時(shí)隙與之前的信道相同的新的序列。

2.3 分析

當(dāng)任意兩個(gè)用戶(hù)在某些時(shí)段交匯時(shí)，他們有一定的可能性跳頻到同一個(gè)通道上，可能性的大小由他們的可用信道的數(shù)量和信道跳頻的方式?jīng)Q定。任何用戶(hù)交匯之后他們將會(huì)成為一個(gè)整體，并嘗試與其他用戶(hù)交匯。因此，如果在以下的任一個(gè)時(shí)隙中，交匯過(guò)的用戶(hù)在不同的信道上跳頻，他們將有更多的機(jī)會(huì)與其他用戶(hù)交匯。

3 模擬

用C++編寫(xiě)的模擬器來(lái)評(píng)估本文的算法和協(xié)議的性能。在模擬中，選擇在對(duì)稱(chēng)和非對(duì)稱(chēng)的情況下都有效的隨機(jī)算法作為序列生成算法。

如圖2所示，在對(duì)稱(chēng)情況下，交匯的時(shí)間隨著L=20的用戶(hù)的增加而增加，并且所有用戶(hù)都具有6個(gè)共同可用的信道。但是，最近最少使用算法大大降低了交匯需要的時(shí)間。

圖2 對(duì)稱(chēng)情況下，總時(shí)間與用戶(hù)的數(shù)量(L= 20)

如圖3所示，在對(duì)稱(chēng)的情況下，隨機(jī)算法和最近最少使用算法之間交匯的時(shí)間比是低的。而當(dāng)L很小的時(shí)候，比率隨著L的增大而減小，當(dāng)L到達(dá)一個(gè)定值時(shí)，比率也會(huì)獲得一個(gè)動(dòng)態(tài)穩(wěn)定值。

圖3 對(duì)稱(chēng)情況下，時(shí)間比率與交匯信息長(zhǎng)度(N=10)

如圖4所示，在非對(duì)稱(chēng)情況下，交匯的時(shí)間隨著L=20的用戶(hù)數(shù)的增加而增加，并且所有用戶(hù)都具有至少3個(gè)共同可用的信道。但是，最近最少使用算法大大降低了交匯需要的時(shí)間。

如圖5所示，在非對(duì)稱(chēng)的情況下，隨機(jī)算法和最近最少使用算法之間交匯的時(shí)間比是低的。而當(dāng)L很小的時(shí)候，比率隨著L的增大而減小，當(dāng)L達(dá)到一個(gè)定值時(shí)，比率也會(huì)獲得一個(gè)動(dòng)態(tài)穩(wěn)定值。

圖4 非對(duì)稱(chēng)情況下，總時(shí)間與用戶(hù)數(shù)的數(shù)量(L=20)

圖5 非對(duì)稱(chēng)情況下，時(shí)間比率與交匯信息長(zhǎng)度(N=10)

4 結(jié)論

本文提出了一種算法，以加快認(rèn)知無(wú)線(xiàn)網(wǎng)絡(luò)交匯的過(guò)程，其關(guān)鍵思想是減少已交匯用戶(hù)之間的重復(fù)交匯，提出最近最少使用算法用來(lái)改進(jìn)交匯。模擬結(jié)果表明了該算法的性能。

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

[2] 滕志軍, 楊旭, 韓雪. 基于多次博弈的認(rèn)知無(wú)線(xiàn)電頻譜動(dòng)態(tài)分配算法[J]. 電子技術(shù)應(yīng)用, 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] 劉權(quán),趙光勝,王曉東,等.認(rèn)知無(wú)線(xiàn)電網(wǎng)絡(luò)信道交匯研究綜述[J].軟件學(xué)報(bào),2014,25(3):606-630.

[5] 王必烈,陳瑾,龔玉萍,等.認(rèn)知無(wú)線(xiàn)網(wǎng)絡(luò)中基于信道跳頻的盲交會(huì)技術(shù)[J].軍事通信技術(shù),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

田宏偉，王宜懷.認(rèn)知無(wú)線(xiàn)電網(wǎng)絡(luò)信道交匯加速算法[J].微型機(jī)與應(yīng)用，2017,36(12)：61-63，67.

2016-12-27)

田宏偉(1981-)，男，碩士，高級(jí)工程師，主要研究方向：嵌入式系統(tǒng)應(yīng)用。

王宜懷(1962-)，男，博士，教授，博士生導(dǎo)師，主要研究方向：嵌入式系統(tǒng)與傳感網(wǎng)技術(shù)。