CRN中基于單位圓盤圖模型的廣播調(diào)度算法

祝 青,何建新

(湖南城市學院信息科學與工程學院,湖南益陽413000)

CRN中基于單位圓盤圖模型的廣播調(diào)度算法

祝 青,何建新

(湖南城市學院信息科學與工程學院,湖南益陽413000)

廣播調(diào)度是目前認知無線電網(wǎng)絡中的研究熱點之一,現(xiàn)有廣播調(diào)度算法主要為近似算法,存在方案性能與最優(yōu)解方案差距太大的問題。為此,提出一種基于單位圓盤圖模型的廣播調(diào)度算法BS-UDGM。構(gòu)建一棵基于連通支配集的廣播樹,作為調(diào)度的基礎結(jié)構(gòu),采用平面細分和著色技術(shù)對廣播樹進行優(yōu)化,通過混合使用單播和廣播通信模式,完成廣播任務。仿真實驗結(jié)果表明,相比其他調(diào)度算法,該算法在延時和冗余方面的性能明顯提高。

認知無線網(wǎng)絡;廣播調(diào)度;連通支配集;單位圓盤圖模型;延時

1 概述

無線電頻譜是一種珍貴有限的資源,現(xiàn)有的頻譜分配方案［1］大多采用靜態(tài)分配原則,即把頻譜資源條狀分割成若干個子頻段,每個子頻段通常只分配給一種授權(quán)用戶使用,只有很少的一部分頻段未被分配。這種分配的不平衡性造成頻譜資源日益枯竭,開放使用的非授權(quán)頻段只占整個頻譜資源的很小一部分,但在該頻段的用戶卻很多,已基本趨于飽和;而授權(quán)頻段占用了整個頻譜資源的絕大部分,但根據(jù)美國聯(lián)邦通信委員會(Federal Communications Commission,FCC)的調(diào)查發(fā)現(xiàn),在不同地方不同時間,不少授權(quán)頻段處于空閑狀態(tài),平均使用率僅為5.2%。

認知無線電網(wǎng)絡［2］(Cognitive Radio Networks, CRN)可以提高無線頻譜的使用效率,是下一代超寬帶無線網(wǎng)接入的首要選擇。CRN由主要用戶(PU,認證用戶)和次要用戶(SU,未認證用戶)組成,它們共享相同的時間、空間、頻譜。其中,SU用戶通過頻譜感知,找到可以使用的空間頻譜,在不對PU用戶造成干擾的前提下,進行數(shù)據(jù)傳輸。在CRN中,有效的廣播調(diào)度是一個重要的問題,它關(guān)系到SU用戶的頻譜感知效率、認知路由的可靠性［3］等方面,對于提高CRN運行的可靠性具有重要影響。因此,本文將主要針對CRN中的廣播調(diào)度問題展開研究。

2 相關(guān)工作

廣播調(diào)度問題是CRN中的研究熱點之一,相繼有眾多研究者提出了一系列解決CRN廣播調(diào)度問題的方法,如文獻［4］提出了基于首要信道半雙工的無線認知傳感器網(wǎng)絡廣播協(xié)議。仿真實驗表明,與完全廣播相比,該協(xié)議降低了廣播延遲和開銷,更利于應用于無線認知傳感器網(wǎng)絡。文獻［5］利用靜態(tài)博弈方法,根據(jù)最小增量按需驅(qū)動思想建立了節(jié)約能量的組播樹,提出基于能量優(yōu)化的適用于認知無線電網(wǎng)絡的按需組播路由協(xié)議。文獻［6］提出了一種負載均衡的無線鏈路權(quán)值函數(shù)及計算算法LBWC,在此基礎上,設計了一種滿足QoS約束的負載均衡組播路由與頻譜分配算法 LMRS2A。LMRS2A算法首先采用LBWC算法計算無線鏈路的權(quán)值,進行負載均衡組播樹的構(gòu)造,然后采用基于無線廣播特性的QoS約束頻譜分配算法WBA2S對無線鏈路進行信道分配。仿真結(jié)果表明,LMRS2A能達到預定目標,不僅避免了擁塞節(jié)點的產(chǎn)生,而且僅需較少的傳輸次數(shù)。

另外,文獻［7］提出了一種不需使用共同控制信道的分布式廣播協(xié)議。該協(xié)議不需要網(wǎng)絡全局拓撲信息及時間同步信息。然而該協(xié)議未給出明確的廣播延時邊界。文獻［8］研究了多跳CRN網(wǎng)絡選擇性廣播問題,廣播消息通過預先選擇的信道進行傳輸。通過引入相鄰圖和最小相鄰圖概念,提出了一種選擇性廣播近似算法,并通過仿真實驗驗證了算法的有效性。文獻［9］提出一種CRN網(wǎng)絡廣播算法,以實現(xiàn)消息到達率最大化,降低數(shù)據(jù)冗余和傳輸時延。然而,該文獻沒有對算法進行分析,只是通過仿真對算法做了評估。文獻［10］基于簡單的網(wǎng)絡干擾模型,將廣播調(diào)度問題建模為整數(shù)線性規(guī)劃問題,然后提出了復雜度分別為O(RMN3logN+LN3logN)和O(LMN3logN)的近似算法,其中,R是網(wǎng)絡半徑;M是CRN網(wǎng)絡的可用信道數(shù)量;N是SU用戶數(shù)量;L是一次性調(diào)度中的時隙數(shù)量。然而,這2種近似算法的性能遠低于最優(yōu)解(O(R))。鑒于此,本文在現(xiàn)有工作的基礎上,提出了一種基于單位圓盤圖模型的廣播調(diào)度算法BS-UDGM。

3 系統(tǒng)模型

3.1 網(wǎng)絡模型

本文假設,主要用戶網(wǎng)絡由N個服從泊松分布的PU用戶組成,用集合Vp={S1,S2,…,SN}表示。PU用戶的傳輸半徑和干擾半徑表示為R和RI。網(wǎng)絡時間分為多個時隙,每個時隙的長度為τ,PU用戶在時隙內(nèi)傳輸數(shù)據(jù)報文。在每個時隙期間,主發(fā)送方的分布服從密度為λ的二維泊松點過程XT分布。根據(jù)位移定理［11］,在每個時隙期間,主要接收方的分布與XT存在關(guān)聯(lián),形成了另一個密度為λ的二維泊松點過程XR。

次要用戶網(wǎng)絡由一個隨機分布的廣播源次要用戶(SU用戶)(表示為s0)和n個隨機分布的SU用戶(表示為s1,s2,…,sn)組成。SU用戶的傳輸半徑和干擾半徑分別為r和rI。對2個SU用戶si和sj,如果歐幾里德距離D(si,sj)滿足D(si,sj)≤r,則認為兩者間存在一條鏈接。因此,次要用戶網(wǎng)絡可以建模為圖G=(Vs,Es),其中,Vs={s0,s1,…,sn}為結(jié)點集,Es為Vs中SU用戶可能形成的所有鏈路集。另外,本文采用UDG模型［12］作為干擾模型,在該模型中,干擾范圍等于發(fā)射范圍,即有 RI∈R, rI=r。

3.2 問題定義

根據(jù)上述定義的網(wǎng)絡模型,可以定義CRN的廣播調(diào)度問題(BSP)如下:設次要用戶網(wǎng)絡表示為圖G={Vs={s0,s1,…,sn},Es},其中,s0為廣播源,s0需要將數(shù)據(jù)報文發(fā)送給網(wǎng)絡所有其他SU用戶。然后,延遲為l的廣播調(diào)度表示為一個子集序列〈V0, V1,…,Vl〉,且滿足:(1)V0={s0},?1≤i≤l,Vi?Vs;(2)在時隙1≤i≤l內(nèi),Vi中的所有SU用戶可以成功接收中部分 SU用戶廣播的數(shù)據(jù)報文; (3)=Vs,即所有SU用戶在調(diào)度結(jié)束時都有被廣播的數(shù)據(jù)報文的一份拷貝。依據(jù)以上定義,設廣播延時為l,廣播冗余為max{di|si(0≤i≤n)在整個廣播調(diào)度期間發(fā)送di次數(shù)據(jù)報文},則本文要研究的問題是:確定一種廣播調(diào)度策略,使延時l最低。

4 廣播樹的構(gòu)建

本節(jié)首先構(gòu)建一個基于連通支配集(CDS)的廣播樹,表示為T,作為調(diào)度的基礎結(jié)構(gòu)。對于圖G= (Vs,Es)的次要用戶網(wǎng)絡,圖G的支配集(DS)為Vs的一個子集D,于是對?si∈Vs,si∈D或者si與D中部分 SU用戶相鄰。如果 G在 D上的導出子圖G［D］相連,則D為圖G的相連支配集(CDS)。圖G的最大獨立集(MIS)M為Vs的一個子集,于是有:(1)對?si∈Vs,si∈M 或者?sj∈M,滿足(si,sj)∈Es;(2)?si,sj∈M,使(si,sj)?Es。很明顯,MIS也為DS。

本文根據(jù)如下3個步驟構(gòu)建基于CDS集的廣播樹T:(1)以s0為起點,對圖G實施寬度優(yōu)先搜索,確定一個 MIS,表示為圖 G的集合 D。如圖1(a)所示,黑色節(jié)點集合為該網(wǎng)絡的MIS集。很明顯,集合D也為一個DS集。D中的黑色節(jié)點經(jīng)常稱為支配節(jié)點。(2)確定一個節(jié)點最小集C,將D中的支配節(jié)點連接起來,使D∪C成為圖G的一個CDS集。如圖1(a)所示,C由灰色節(jié)點組成,也稱為連接節(jié)點。黑色節(jié)點和灰色節(jié)點共同構(gòu)成圖1(a)中的CDS集。(3)對Vs(D∪C)中剩余的每個白色節(jié)點,稱為受支配節(jié)點,將距離最短的相鄰支配節(jié)點分配給s0作為其母節(jié)點。對C(D)中的每個連接節(jié)點(除了s0的支配節(jié)點),將距離最短的相鄰支配節(jié)點(連接節(jié)點)分配給s0作為其母節(jié)點。此時,基于 CDS集的廣播樹T構(gòu)建完畢。例如,圖1(b)即圖1(a)中次要用戶網(wǎng)絡構(gòu)建的廣播樹。

圖1 廣播樹構(gòu)建示例

對T樹的節(jié)點si∈Vs,定義p(si)(si≠s0)為其母節(jié)點,c(si)={sj|p(si)=si}為其子節(jié)點集。設Δ(si)=|c(si)∩(Vs/(D∪C))|為子節(jié)點si在樹T中擁有的受支配節(jié)點的數(shù)量。很明顯,如果si為連接節(jié)點或受支配節(jié)點,則 Δsi=0。同時定義ΔT= max{Δ(si)|si∈Vs},表示一個支配節(jié)點所能擁有的受支配子節(jié)點的最大數(shù)量。樹T中節(jié)點s0的高度定義為h(s0)=0,對其他節(jié)點si≠s0,它在樹T中的高度定義為h(si)=(p(si))+1。此外,樹T的高度定義為h-=max{h(si)|si∈Vs}。根據(jù)以上分析,有如下的引理:

引理1 對?si∈C,si最多與D中5個支配節(jié)點相鄰,其中一個為其母節(jié)點。對?si∈D,如果si≠s0且|c(s0)∩C|≤12,則|c(si)∩C|≤11,即如果si不是根支配節(jié)點(不是s0),且s0最多有12個連接子節(jié)點,則si最多有11個連接子節(jié)點。

引理2 半徑 2r(3r)范圍圓盤內(nèi),最多有21(42)個支配節(jié)點。

5 廣播調(diào)度算法

在本文提出的廣播調(diào)度算法BS-UDGM中,一個時隙被分為2個部分:(1)τs,表示SU用戶的感應窗口,用于進行頻譜感知;(2)τd,表示數(shù)據(jù)傳輸窗口,用以傳輸數(shù)據(jù)報文。算法偽代碼如下:

算法1 BS-UDGM算法

輸入 基于CDS的廣播樹

輸出 廣播調(diào)度策略

算法1由 2個階段組成:第一階段(1行 ～6行),將數(shù)據(jù)報文發(fā)送給樹T的支配節(jié)點和連接節(jié)點,即{s0}?D∪C。第2階段(7行～10行),將數(shù)據(jù)報文發(fā)送給樹T的所有受支配節(jié)點,即D?Vs/(D∪C)。第1階段的廣播調(diào)度用單播模式完成。第2階段首先用六邊形對網(wǎng)絡平面進行細分并著色,然后將支配節(jié)點集D分割為互相分離的子集。最后由支配節(jié)點在樹T中的母節(jié)點對這些支配節(jié)點子集采用Scheduling-subset(Di)函數(shù)(算法2)進行調(diào)度,直到所有受支配節(jié)點接收到數(shù)據(jù)報文。

算法2 Scheduling-subset(Di)

從算法2中可以看出,Scheduling-subset(Di)函數(shù)通過使用混合單播和廣播模式完成廣播調(diào)度任務。對SU用戶si∈Di,如果它還沒有接收到數(shù)據(jù)報文的子節(jié)點數(shù)量不低于閾值exp(πλ(r2+R2)),則它將廣播數(shù)據(jù)報文。否則,它將通過單播方式將數(shù)據(jù)發(fā)送給仍在等待接收廣播報文的子節(jié)點。

6 仿真實驗

6.1 廣播延時分析

圖2給出了3種算法的延時性能比較結(jié)果。

圖2 BS-UDGM算法的廣播延時

將SU用戶密度確定為ρ=4.0時,網(wǎng)絡規(guī)模對3種算法的影響見圖2(a)。從圖中可以看出,當網(wǎng)絡規(guī)模上升時,所有算法的延時均有上升。這主要是因為:有更多SU用戶參與到廣播任務中,廣播樹的高度增加。BS-UDGM算法性能優(yōu)于H1和H2,面對大型CRN時更是如此。這是因為成功的廣播機會往往比成功的單播機會更為難得。利用這一特點,BS-UDGM首先通過單播方式,將報文發(fā)送給部分SU用戶。然后,BS-UDGM通過混合使用單播和廣播模式,對這些SU用戶同時調(diào)度,以實現(xiàn)通信效率最大化,顯著提高了廣播調(diào)度的速度。平均來說, BS-UDGM算法的延時相比H1和H2分別下降了297.89%和297.98%。

當β變大時,3種算法的延時變化情況見圖2(b)。從中可以看出,β增大時,3種算法的延時也會增大。這是因為:β越大,SU和PU的干擾范圍越大。所以,3種算法的傳輸并行性和頻譜機會下降,從而導致延時上升。另外,由于BS-UDGM可以根據(jù)不同網(wǎng)絡情況自適應地運用混合單播和廣播通信模式來完成廣播調(diào)度任務,因此延時要低于H1和H2算法。

6.2 廣播冗余分析

圖3給出了3種算法的廣播冗余性能比較結(jié)果。

圖3 BS-UDGM算法的廣播冗余

從圖3(a)中可以看出,如果網(wǎng)絡密度固定,改變網(wǎng)絡規(guī)模,所有算法的廣播冗余保持穩(wěn)定。這主要是因為廣播冗余與網(wǎng)絡的規(guī)模無關(guān),它只取決于廣播樹中的子節(jié)點數(shù)量和可用頻譜機會的多少。因此,網(wǎng)絡規(guī)模對3種算法的冗余度影響很小。此外, BS-UDGM性能優(yōu)于H1和H2。這是由于H1和H2只使用廣播通信模式,由于CRN廣播傳輸可能會頻譜機會的不足使得接收方數(shù)量極低,因此,H1和H2算法中的SU用戶需要廣播多次以保證子節(jié)點接收到報文,既浪費了SU用戶的能量,又給PU用戶造成了更大的干擾。而BS-UDGM算法可用根據(jù)網(wǎng)絡情況自適應地采用單播和廣播模式,從而實現(xiàn)通信效率最大化。因此,BS-UDGM的廣播冗余效率更高,冗余度平均比H1和H2算法降低了63.68%和63.79%。

另外,β對3種算法的影響見圖3(b)。從圖中可以看出,當β變大時,H1和H2的冗余顯著上升。這是因為它們的冗余度主要取決于廣播頻譜機會,而頻譜機會受β值影響。β值越大,SU和PU用戶的干擾范圍越大。因此,β較大時,頻譜機會減少, H1和H2冗余變大。另一方面,BS-UDGM算法冗余度的決定性因素是SU用戶擁有的子節(jié)點數(shù)量。因此,β值較大時,對BS-UDGM延時性能有較大影響,但對冗余性能的影響很小。總的來說,BS-UDGM冗余基本保持穩(wěn)定,而H1和H2的冗余度是BSUDGM的8.46倍和8.47倍。

7 結(jié)束語

廣播調(diào)度問題一直是CRN研究中較為重要的內(nèi)容,針對現(xiàn)有廣播調(diào)度算法的不足,本文基于單位圓盤圖模型,提出了一種改進的廣播調(diào)度算法,仿真實驗結(jié)果表明,本文算法相對當前其他算法延時更低,冗余效率更高。下一步工作的重點是考慮采用隨機圖理論對認知無線電網(wǎng)絡中的路由問題進行建模,研究基于最小化延遲的認知路由算法。

［1］ 鄺祝芳,陳志剛,楊藝清.基于SNR和譜熵的協(xié)作式頻譜感知算法仿真研究［J］.系統(tǒng)仿真學報,2013,25 (4):662-667.

［2］ 趙賀楠,黃劉生,張銀東,等.認知無線電網(wǎng)絡中終端群的接入網(wǎng)切換算法［J］.小型微型計算機系統(tǒng), 2013,34(8):1732-1735.

［3］ 張光華,張玉清,劉雪峰.認知無線電網(wǎng)絡中基于信任的安全路由模型［J］.通信學報,2013,34(2):56-64.

［4］ 普健杰,曾凡仔.基于首要信道的無線認知傳感器網(wǎng)絡多信道廣播協(xié)議［J］.通信學報,2013,34(7):81-86.

［5］ 王 超,張 羲,周賢偉,等.基于能量優(yōu)化的認知無線電網(wǎng)絡組播路由協(xié)議［J］.計算機工程與應用, 2012,48(7):99-101.

［6］ 鄺祝芳,陳志剛,劉 蕙.一種認知無線Mesh網(wǎng)絡中負載均衡的組播路由算法［J］.計算機學報,2013,36 (3):521-531.

［7］ Song Yi,Xie Jiang.A Distributed Broadcast Protocol in Multi-hop Cognitive Radio Ad Hoc Networks Without a Common ControlChannel［C］//Procceedings of INFOCOM'12.［S.l.］:IEEE Press,2012:2273-2281.

［8］ Kondareddy Y R,Agrawal P.Selective Broadcasting in Multi-hop Cognitive Radio Networks［C］//Procceedings of Sarnoff Symposium.［S.l.］:IEEE Press,2008:1-5.

［9］ Ert?ugrul O,Buzluca F.An Efficient Broadcasting Scheme for Cognitive Radio Ad Hoc Networks［C］//Procceedings of the 4th International Conference on Cognitive Radio and Advanced Spectrum Management.［S.l.］:ACM Press, 2011:5-13.

［10］ Arachchige C J L,Venkatesan S,Chandrasekaran R,et al.Minimal Time Broadcasting in Cognitive Radio Networks［M］.Berlin,Germany:Springer,2011.

［11］ Abramson J,Pitman J.Concave Majorants of Random Walks and Related Poisson Processes［J］.Combinatorics, Probability&Computing,2011,20(5):651-682.

［12］ Lotker Z,Peleg D.Structure and Algorithms in the SINR Wireless Model［J］.ACM SIGACT News,2010,41(2): 74-84.

編輯 任吉慧

Broadcasting Scheduling Algorithm Based on Unit Disk Graph Model in Cognitive Radio Networks

ZHU Qing,HE Jianxin
(School of Information Science and Engineering,Hunan City University,Yiyang 413000,China)

Broadcasting scheduling problem is a hot research problem in Cognitive Radio Networks(CRN),and existing works for the broadcast scheduling issue in CRN are either heuristic solutions without performance guarantee or with performance far from the optimal solution.This paper proposes a Broadcasting Scheduling Algorithm Based on Unit Disk Graph Model(BS-UDGM).It constructs a Connected Dominating Set(CDS)based broadcasting tree,which serves as the scheduling infrastructure,and subsequently,the broadcasting tree is optimized by using the tessellation and coloring of a plane.The broadcast task is finished by employing mixed unicast and broadcast communication modes.Simulation results show that compared with the existing algorithms,the performance of the proposed algorithm is improved with respect to both latency and redundancy.

Cognitive Radio Networks(CRN);broadcasting scheduling;Connected Dominating Set(CDS);unit disk graph model;latency

1000-3428(2014)11-0101-05

A

TP393

10.3969/j.issn.1000-3428.2014.11.020

湖南省科技計劃基金資助項目(2014FJ3111)。

祝 青(1976-),女,副教授、碩士,主研方向:信息檢索,認知無線網(wǎng)絡;何建新,副教授、碩士。

2013-11-04

2014-01-10E-mail:404685796@qq.com

中文引用格式:祝 青,何建新.CRN中基于單位圓盤圖模型的廣播調(diào)度算法［J］.計算機工程,2014,40(11):101-105.

英文引用格式:Zhu Qing,He Jianxin.Broadcasting Scheduling Algorithm Based on Unit Disk Graph Model in Cognitive Radio Networks［J］.Computer Engineering,2014,40(11):101-105.