CRN中基于單位圓盤圖模型的廣播調度算法

祝 青,何建新

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

CRN中基于單位圓盤圖模型的廣播調度算法

祝 青,何建新

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

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

認知無線網絡;廣播調度;連通支配集;單位圓盤圖模型;延時

1 概述

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

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

2 相關工作

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

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

3 系統模型

3.1 網絡模型

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

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

3.2 問題定義

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

4 廣播樹的構建

本節首先構建一個基于連通支配集(CDS)的廣播樹,表示為T,作為調度的基礎結構。對于圖G= (Vs,Es)的次要用戶網絡,圖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。

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

圖1 廣播樹構建示例

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

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

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

5 廣播調度算法

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

算法1 BS-UDGM算法

輸入 基于CDS的廣播樹

輸出 廣播調度策略

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

算法2 Scheduling-subset(Di)

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

6 仿真實驗

6.1 廣播延時分析

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

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

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

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

6.2 廣播冗余分析

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

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

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

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

7 結束語

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

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

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

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

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

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

［6］ 鄺祝芳,陳志剛,劉 蕙.一種認知無線Mesh網絡中負載均衡的組播路由算法［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-),女,副教授、碩士,主研方向:信息檢索,認知無線網絡;何建新,副教授、碩士。

2013-11-04

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

中文引用格式:祝 青,何建新.CRN中基于單位圓盤圖模型的廣播調度算法［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.