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

田宏偉，王宜懷

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

?

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

田宏偉1，王宜懷2

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

在加速的情況下，一旦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ǎng)絡(luò)由N(N≥2)個(gè)二級用戶組成，他們可以用集合N={u1，…，uN}表示。假定系統(tǒng)是有時(shí)隙的且所有的時(shí)間間隙都具有相同的和固定的長度。許可頻譜被劃分成M(M≥1)個(gè)非重疊的信道，用M={c1，…，cM}表示。假設(shè)網(wǎng)絡(luò)中的所有次級用戶知道所有這些信道，并且每個(gè)用戶配備了一個(gè)單一的認(rèn)知無線電。考慮到頻譜的異質(zhì)性，讓Mi?M表示組UI的可用信道。

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

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

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

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

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

2.2 最近最少使用算法

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

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

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

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

2.3 分析

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

3 模擬

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

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

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

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

圖3 對稱情況下，時(shí)間比率與交匯信息長度(N=10)

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

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

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

圖5 非對稱情況下，時(shí)間比率與交匯信息長度(N=10)

4 結(jié)論

本文提出了一種算法，以加快認(rèn)知無線網(wǎng)絡(luò)交匯的過程，其關(guān)鍵思想是減少已交匯用戶之間的重復(fù)交匯，提出最近最少使用算法用來改進(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)知無線電頻譜動(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ǎng)絡(luò)信道交匯研究綜述[J].軟件學(xué)報(bào),2014,25(3):606-630.

[5] 王必烈,陳瑾,龔玉萍,等.認(rè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ǎng)絡(luò)信道交匯加速算法[J].微型機(jī)與應(yīng)用，2017,36(12)：61-63，67.

2016-12-27)

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

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