多類型異構(gòu)無線網(wǎng)絡(luò)連通性研究*

郭敬元，楊 濤，馮 輝，胡 波

（復(fù)旦大學(xué)電子工程系 上海200433）

1 引言

隨著網(wǎng)絡(luò)中越來越靈活的接入需求的發(fā)展，不同類型的用戶終端之間的交互變得越來越頻繁，網(wǎng)絡(luò)也越來越多地體現(xiàn)出異構(gòu)和動態(tài)的特性。異構(gòu)性體現(xiàn)在網(wǎng)絡(luò)中用戶節(jié)點類型和分布的不同；動態(tài)性體現(xiàn)在自組織網(wǎng)絡(luò)可以靠節(jié)點之間的通信組織相連網(wǎng)絡(luò)，而不需要中心節(jié)點進(jìn)行協(xié)調(diào)。典型的例子是認(rèn)知無線電技術(shù)，主用戶和次用戶之間通過機(jī)會頻譜共享進(jìn)行交互。近年來，連續(xù)滲流理論[1]的發(fā)展和在全局網(wǎng)絡(luò)行為方面的應(yīng)用得到了重視。對于同構(gòu)的自組織網(wǎng)絡(luò)的連通性已有很多研究[2～6]，但對于異構(gòu)網(wǎng)絡(luò)，只有零星的文獻(xiàn)有所研究，其中Ren W等人[7]定義了連通區(qū)域的概念，并推導(dǎo)出以節(jié)點密度、干擾范圍和傳輸范圍形式給出的連通性充分和必要條件，首創(chuàng)了將機(jī)會頻譜的占有和釋放與布爾滲流模型中的連通分量和空分量進(jìn)行耦合求解。而對于次用戶之間的合作對連通性的影響，Chon W[8]將異構(gòu)網(wǎng)絡(luò)建模為多個自組織網(wǎng)絡(luò)，得到噪聲受限和干擾受限普通衰落信道條件下的平均度和度分布，并以此為基礎(chǔ)分析了合作滲流。參考文獻(xiàn)[9]引入了認(rèn)知無線電圖模型，并考慮可用信道的個數(shù)和活動的主用戶，由此得出在滿足次用戶網(wǎng)絡(luò)滲流前提下的主用戶臨界密度。Wang P等[10]考慮到動態(tài)連接對連通性的影響，證明如果次用戶密度大于一個臨界值，則網(wǎng)絡(luò)在任意時刻都可以保持連通，即使網(wǎng)絡(luò)一直經(jīng)歷動態(tài)變化；還證明即使在任意時刻整個次用戶網(wǎng)絡(luò)是不連通的，也有可能存在一條時延通路使得某個次用戶以概率1發(fā)送信息到目的地，而這一時延與發(fā)送端到接收端的歐式距離呈漸進(jìn)線性關(guān)系。

網(wǎng)絡(luò)連通性的研究，分為有限范圍和無限范圍，本文研究后者。從滲流角度研究無線多跳網(wǎng)絡(luò)的連通性，主要特點是連通性取決于某個參數(shù)，滲流模型的分量可能有兩種情況：所有連通分量全部有限；存在一條無限長的連通分量。后者被定義為無限網(wǎng)絡(luò)的連通。

網(wǎng)絡(luò)連通性研究的目標(biāo)就是要找到使得網(wǎng)絡(luò)能夠連通的條件，參見如下連通性的定義：如果網(wǎng)絡(luò)中存在一條無限長的連通分量，則稱網(wǎng)絡(luò)是連通的。所謂無限長的連通分量，指圖中無限長的由節(jié)點連接而成的一個分簇，只要存在無限長連通分量的概率不為0，就認(rèn)為網(wǎng)絡(luò)是連通的。

網(wǎng)絡(luò)滲流的概念是從物理學(xué)領(lǐng)域發(fā)展出來的，指的是從無連通分量到出現(xiàn)連通分量的相變過程，即物質(zhì)在外部參數(shù)（如溫度、壓力等）的連續(xù)變化之下，從一種相忽然變成另一種相，最常見的是冰變成水。將網(wǎng)絡(luò)滲流應(yīng)用到信息科學(xué)領(lǐng)域，通過隨機(jī)幾何圖實現(xiàn)。隨機(jī)幾何圖描述了點和邊的關(guān)系，點和邊的分布以及邊和邊的連接方式?jīng)Q定了一個隨機(jī)幾何圖的性質(zhì)，點的分布服從某個特定的點過程。點過程是從概率空間到某空間E上的點度量空間的映射Φ，點度量是局部有限的，且只取整數(shù)值，表示如下：

其中，δXi是狄拉克測度，Xi是隨機(jī)變量，在E上取值，是d維歐幾里德空間,d≥1。連續(xù)滲流領(lǐng)域普遍采用的模型是泊松點過程分布的點，當(dāng)且僅當(dāng)它們之間的距離不超過r時，這兩點相連，記為G（X，r）。雖然泊松分布過程被廣泛用作分析隨機(jī)網(wǎng)絡(luò)連通性，但并不總是符合實際情況，簇分布被證明更加接近城市熱點地區(qū)的實際情況[11,12]，不過此類分布的連通性仍然未知。常規(guī)的異構(gòu)網(wǎng)絡(luò)分析主要側(cè)重于兩類異構(gòu)用戶，即主用戶和次用戶之間的交互行為，但實際上次用戶也是由多種類型的終端構(gòu)成的，如具有不同傳輸范圍的終端。本文通過對單類型節(jié)點和多類型用戶節(jié)點組成的異構(gòu)網(wǎng)絡(luò)的分析，推導(dǎo)網(wǎng)絡(luò)的連通性與各參數(shù)之間的影響。

2 網(wǎng)絡(luò)模型與應(yīng)用

目前主要從兩個角度進(jìn)行網(wǎng)絡(luò)連通性研究，分別是泊松布爾模型和隨機(jī)連接模型。布爾模型中，點的分布隨機(jī)，每個點的覆蓋范圍隨機(jī)（連續(xù)滲流中采用固定大小圓盤模型），任意節(jié)點可以和自己覆蓋范圍內(nèi)的所有節(jié)點連接；隨機(jī)連接模型中，點的分布隨機(jī)，但每個點并不是跟自己圓形覆蓋范圍內(nèi)的節(jié)點連接，而是由一個隨機(jī)連接函數(shù)決定與某一個節(jié)點進(jìn)行連接。

從布爾模型和隨機(jī)連接模型兩個角度分別分析異構(gòu)網(wǎng)絡(luò)的連通性，其中布爾模型又分為單類型節(jié)點異構(gòu)網(wǎng)絡(luò)和多類型節(jié)點異構(gòu)網(wǎng)絡(luò)。對于每種模型，都有一個對應(yīng)的實際應(yīng)用網(wǎng)絡(luò)進(jìn)行舉例分析，如移動自組織（Ad Hoc）網(wǎng)絡(luò)、認(rèn)知無線電。

2.1 布爾模型

2.1.1 單類型節(jié)點異構(gòu)網(wǎng)絡(luò)

Ad Hoc網(wǎng)絡(luò)的連通性受到廣泛關(guān)注。Ad Hoc網(wǎng)絡(luò)是一種多跳的臨時性自治系統(tǒng)，原型是美國早在1968年建立的ALOHA網(wǎng)絡(luò)。作為一種分布式網(wǎng)絡(luò)，Ad Hoc網(wǎng)絡(luò)是一種自治、多跳網(wǎng)絡(luò)，整個網(wǎng)絡(luò)沒有固定的基礎(chǔ)設(shè)施，能夠在不能利用或者不便利用現(xiàn)有網(wǎng)絡(luò)基礎(chǔ)設(shè)施（如基站、AP）的情況下，提供終端之間的相互通信。由于終端的發(fā)射功率和無線覆蓋范圍有限，距離較遠(yuǎn)的兩個終端如果要進(jìn)行通信就必須借助于其他節(jié)點進(jìn)行分組轉(zhuǎn)發(fā)，這樣節(jié)點之間構(gòu)成了一種無線多跳網(wǎng)絡(luò)。

簡單地用泊松分布分析Ad Hoc網(wǎng)絡(luò)過為理想化，因為假定所有用戶節(jié)點平均分布在有限區(qū)域中不太符合實際情況。實際的用戶節(jié)點分布經(jīng)常是在某些熱點地區(qū)稠密，在其他非熱點地區(qū)稀疏，從而可引出簇分布，即用戶節(jié)點有向各個中心節(jié)點靠攏的趨向。分析單類型用戶時，用簇分布中的一種——Thomas分布模擬真實用戶節(jié)點分布。

當(dāng)次用戶只有一種類型（即所有次用戶傳輸范圍相同）且分簇分散在各處時，研究臨界點與其他簇分布參數(shù)的關(guān)系。采用Thomas點過程作為簇分布的模型，圖1(a)為一個Thomas過程在單位方格中的示例。在Thomas過程中，節(jié)點分為兩類：一類是簇頭節(jié)點，即中心節(jié)點，如圖1(a)中的“”點，服從泊松分布，均勻密度為λ；另一類是圍繞在各個中心節(jié)點周圍的普通節(jié)點，如圖1(a)中的黑色圓點，服從高斯分布，均值為μ，協(xié)方差矩陣為σ=diag(σx,σy)，圖1(a)中的圓圈是以中心節(jié)點為圓心、某個固定的σ=σx=σy為半徑所做的圓。所有普通節(jié)點都可作為發(fā)送端和接收端，傳輸范圍均為r。

直觀來說，當(dāng)節(jié)點分布從泊松分布擴(kuò)展到Thomas分布時，滲流產(chǎn)生將變得更加困難。原因在于隨著進(jìn)一步的聚簇，越來越多的內(nèi)部節(jié)點的連接效應(yīng)會遞減，直到逐步發(fā)展到全局連通性主要由每個簇的邊緣節(jié)點決定。一旦這些邊緣節(jié)點可以連接相鄰的簇的邊緣節(jié)點，這兩個簇就可以連通。從這種思路出發(fā)，引用平均場估計 （mean field approximation）理論推導(dǎo)傳輸半徑的臨界值。平均場估計理論被用來分析多體物理系統(tǒng)中的交互行為，用均值代替所有交互，將多體問題有效地簡化為單體問題。建模時將所有周邊信息視為一個統(tǒng)一的變量，并將所有的殘余節(jié)點視為確定性的平均場，本質(zhì)即統(tǒng)計均值。

對于Thomas過程而言，可以把簇的內(nèi)部和外部的節(jié)點等效為一個半徑確定但未知的圓，使得這些節(jié)點等效于這個圓上某些均勻分布的點（如圖1(b)所示）。根據(jù)參考文獻(xiàn)[13]，可以先得到圓內(nèi)點的距離分布以及圓上點的平均距離（即圓上點的個數(shù)）。假設(shè)兩個簇的等效圓上各有3個均勻分布的節(jié)點，為了研究這兩個簇之間的隨機(jī)連通性，假定左邊的簇O1固定，讓右邊的簇O2以簇頭為中心，沿某方向轉(zhuǎn)動。當(dāng)總存在至少一個節(jié)點在弧de上時，則總存在一個節(jié)點c可以連接到O2的邊緣節(jié)點，以使兩個簇連通，途經(jīng)節(jié)點{a，b，c，d，e}。

2.1.2 多類型節(jié)點異構(gòu)網(wǎng)絡(luò)

單一類型的簇分布的用戶節(jié)點并不能反映其他一些重要的實際場景，應(yīng)當(dāng)引入混合類型的用戶節(jié)點。例如在認(rèn)知無線電中，有主用戶和次用戶兩類，而次用戶本身也可能有多種類型。考慮到理論分析的可行性，構(gòu)建以下泊松分布的認(rèn)知無線電模型。

無限的二維歐式空間中，泊松分布的次用戶網(wǎng)絡(luò)疊加在泊松分布的主用戶網(wǎng)絡(luò)上。這與同構(gòu)網(wǎng)絡(luò)有著顯著的區(qū)別，即多類次用戶節(jié)點之間通信鏈路的存在與否不僅取決于它們之間的距離，還跟周圍主用戶的特征（荷載、拓?fù)洹⒏蓴_容限）和收發(fā)行為有關(guān)。

假設(shè)主用戶發(fā)射端以密度為λp的二維泊松點過程分布，對每個主用戶發(fā)射端來說，它的接收端均勻分布在傳輸距離為Rp的范圍內(nèi)。假定所有主用戶發(fā)射端的發(fā)射功率相同，信號經(jīng)過相同的路徑損耗，則主用戶接收端也以密度為λp的二維泊松點過程分布且與發(fā)射端點過程相關(guān)，主用戶對周圍次用戶的干擾范圍是RI。

次用戶疊加在主用戶之上，也服從泊松分布，分為兩類（T1與T2），具有混合密度λs，即T1次用戶密度為pλs，T2次用戶密度為（1-p）λs，傳輸范圍分別是rp1、rp2，干擾范圍分別是rI1、rI2。以參考文獻(xiàn)[7]中的模型為參考，并拓展到兩類次用戶的情況，構(gòu)建次用戶之間的雙向連接，如圖2所示。

圖1 Thomas過程

圖2主用戶與次用戶示意

圖2 (a)中，次用戶A到次用戶B的通信鏈路可分為4種情況：T1→T1、T1→T2、T2→T1、T2→T2。圖2(b)為T1→T2放大后的詳細(xì)情況。為了解決網(wǎng)絡(luò)連通性的問題，構(gòu)建隨機(jī)場多類型分支（MBPR）過程，從理論上推導(dǎo)分布參數(shù)對網(wǎng)絡(luò)連通性的影響?？梢韵胂螅瑥哪硞€用戶節(jié)點S1開始，把與之相連的用戶節(jié)點組成的連通分量“提起來”變成一棵以S1為根的樹（如圖3所示），這樣無限長連通分量的存在性就等價于這棵樹（分支過程）能否無限生長下去。問題的本質(zhì)就是，隨機(jī)場如何決定樹的每一代的復(fù)制分布。如前所述，用戶的不同類型指的是不同的傳輸半徑，從而MBPR可以被歸結(jié)為具有不同傳輸半徑的用戶能否通過合作使得這棵樹無限延伸，由此引出兩類次用戶連通的必要條件。當(dāng)有更多類型的次用戶時，可以方便地從兩類次用戶進(jìn)行拓展。

圖3 多類型分支過程

定理 以上定義的混合次用戶網(wǎng)絡(luò)能夠發(fā)生滲流的必要條件是：

證明 基本思路是構(gòu)建一個MBPR，每個節(jié)點都分別對應(yīng)一個類型t∈T={1，2}，每個節(jié)點都可以“生出”任意類型的子節(jié)點，即任意次用戶都可以和滿足以下條件的T1和T2次用戶進(jìn)行通信。

·條件1：它們之間的距離至多為max{rp1，rp2}；

·條件2：它們之間存在雙向機(jī)會頻譜，即次用戶A的rI1或rI2范圍內(nèi)無主用戶接收端，RI范圍內(nèi)無主用戶發(fā)射端，見圖2(b)。

對于每個節(jié)點來說，如果它屬于類型t，則有一個與它關(guān)聯(lián)的隨機(jī)向量ζt={ζt1，ζt2}，其中ζtj是一個隨機(jī)變量，表示由第t類節(jié)點產(chǎn)生第j類節(jié)點的個數(shù)。把它的期望記為mij，則一階矩量矩陣可由A構(gòu)建。根據(jù)參考文獻(xiàn)[16]的定理，MBPR在ρ=1、ρ<1、ρ>1時分別為臨界、次臨界和超臨界狀態(tài)，其中ρ是矩陣A的譜半徑，即A的最大正特征值。

在上述分支過程中，矩陣A的4個元素可以用與參考文獻(xiàn)[7]類似的方法求得，式(4)給出m12元素的求解，其他3個元素可采用類似方法求得。

圖4 SI2（r，θ，Rp，t，rI1，rI2）為陰影部分

2.2 隨機(jī)連接模型

用圓盤模型進(jìn)行理論分析較為方便，但在實際應(yīng)用場景中，由于功率限制與通信干擾及能量消耗等因素，用戶節(jié)點并不可能跟通信范圍內(nèi)的所有節(jié)點都建立連接，而只能跟通信范圍內(nèi)的某些節(jié)點建立連接。此場景可抽象為由隨機(jī)連接函數(shù)決定節(jié)點間連接的隨機(jī)連接模型。先介紹不考慮用戶節(jié)點間距離的Erd仵s-Rényi（ER）模型，再擴(kuò)展增加距離約束。

在圖模型中，ER模型指在每一對節(jié)點中，都以相同的概率p存在一條邊。近年來，Achilioptas過程因為能夠提前或推遲滲流相變的發(fā)生而受到很多關(guān)注。在2000年的一個會議中，Achlioptas D提出，從一個沒有邊的圖出發(fā)，每一步從所有可能的邊中找到兩條獨立的邊e1和e2，再根據(jù)“乘積規(guī)則”[15]選擇兩條邊的一條進(jìn)行連接。而“乘積規(guī)則”，就是通過選擇邊的兩點所在分量的度的乘積大的一條，選擇對應(yīng)的邊。問題在于：乘積規(guī)則會對產(chǎn)生的邊的大小有何變化？對圖的滲流有什么影響？這里給出一個仿真來展示ER模型和乘積規(guī)則對于Thomas過程臨界行為的影響。

如圖5(a)所示，橫坐標(biāo)為次數(shù)，即每次根據(jù)乘積規(guī)則添加一條邊，縱坐標(biāo)為最大連通分量的大小?？梢钥吹?，乘積規(guī)則會一開始推遲相變的發(fā)生，最大連通分量一直保持較小的增長，直到到達(dá)臨界點，最大連通分量迅速增大到90%以上，產(chǎn)生爆炸效應(yīng)，從ER模型的一階相變變?yōu)槎A相變，這種選擇方法產(chǎn)生所謂的“爆炸滲流”現(xiàn)象。

更進(jìn)一步考慮爆炸滲流，一種方法是增加距離約束，即讓兩個用戶節(jié)點之間的連通概率與距離有關(guān)。一般連通性會隨著距離的增大而減少，而是否連通取決于兩個節(jié)點在實際網(wǎng)絡(luò)中的真實距離，這樣乘積規(guī)則就可以修改為增加距離參數(shù)，即選擇以下值：

這被稱為“最小引力規(guī)則”，用來衡量距離對最大連通分量出現(xiàn)的影響。其中，d是一個可調(diào)參數(shù)，衡量距離對乘積規(guī)則的影響，M1與M2表示第一條邊的兩個節(jié)點所對應(yīng)的連接分量的大小，R12表示這兩個點的距離，M3與M4表示第二條邊的兩個節(jié)點所對應(yīng)的連接分量的大小，R34表示這兩個點的距離。引入距離對爆炸滲流的影響如圖5(b)所示，其中粗線表示ER模型，其他7條曲線分別是d從1～7時的乘積規(guī)則模型，隨著d的增大，爆炸特性逐漸減少?？梢酝茰y存在某種標(biāo)度，當(dāng)d趨于無窮大時，爆炸滲流趨于ER模型。

3 仿真試驗與分析

使用蒙特卡洛仿真驗證第2.1節(jié)中二維Thomas過程的臨界連接現(xiàn)象，目的是研究何時以及在哪里會發(fā)生滲流、不同參數(shù)之間的交互如何影響相變的發(fā)生。通過有限尺度的標(biāo)定，首先設(shè)置初始值，在單位方格內(nèi)以Thomas分布確定點的位置。保持3個參數(shù)不變而改變另一個參數(shù)，得到如圖5所示的觀察結(jié)果，其中，縱坐標(biāo)是最大連通分量所占總節(jié)點個數(shù)的比例，橫坐標(biāo)是對應(yīng)的改變參數(shù)。

圖5 兩種爆炸滲流模型相變比較

圖6(a)是通信范圍r對連通性的影響。顯然，如果不要求全連通，則可以顯著地減小r。聚簇參數(shù)σ對最大連通分量的影響較微小，因為較小的σ會加速最大連通分量的出現(xiàn)。圖6(b)是μ對連通性的影響，可以看出，增大μ對于增強(qiáng)網(wǎng)絡(luò)連通性的效率不高，原因是這只是增大了簇頭節(jié)點周圍的平均節(jié)點數(shù)目，如果沒有增大λ，連通性很難通過只擴(kuò)大每個簇的節(jié)點數(shù)而提高。圖6(c)是λ對連通性的影響，因為增大λ不僅會增加簇頭點數(shù)，而且還有附帶的周圍節(jié)點，密度參數(shù)λ對整個網(wǎng)絡(luò)連通性的影響最大。圖6(d）是σ對連通性的影響，這個參數(shù)的影響比其他幾個參數(shù)更復(fù)雜些，隨著σ的增大，最大連通分量的大小先增后減。

尋找臨界值rc、λc較為困難，可以從工程應(yīng)用角度擬合得到rc的近似值。擬合的一種方法是對圖6(b)曲線中的μ進(jìn)行微分，尋找最大的斜率點r作為臨界值rc并與每個μ對應(yīng)，從而得到二階對數(shù)多項式擬合。

4 結(jié)束語

從滲流角度研究了自組織異構(gòu)通信網(wǎng)絡(luò)的連通性問題，分別從布爾模型和隨機(jī)模型的角度出發(fā)，對單類型用戶網(wǎng)絡(luò)和多類型用戶網(wǎng)絡(luò)在不同場景下進(jìn)行建模，從理論推導(dǎo)和仿真的角度分析了認(rèn)知無線電系統(tǒng)中次用戶網(wǎng)絡(luò)的連通性。上述研究對多類型異構(gòu)網(wǎng)絡(luò)的部署與設(shè)計具有一定的指導(dǎo)意義。

圖6 各參數(shù)對最大連通分量的影響

1 Meester R,Roy R.Continuum percolation.Cambridge University,1996

2 Cheng Y C,Robertazzi T G.Critical connectivity phenomena in multi-hop radio models.IEEE Transactions on Communications,1989,37(7)

3 Dousse O,Baccelli F,Thiran P.Impact of interferences on connectivity of Ad Hoc networks.ACM/IEEE Transactions on Networking,2009,13(2):425～436

4 Dousse O,Franceschetti M,Macris N,et al.Percolation in the signal to interference ratio graph.Journals on Appl Prob,2006(43):552～562

5 Kong Z,Yeh E.Connectivity,percolation,and information dissemination in large-scale wireless networks with dynamic links.IEEE Transactions on Information Theory,2009(1)

6 Vaze R.Percolation and connectivity on the signal to interference ratio graph.Proceedings of the IEEE Conference on Computer Communications(INFOCOM 2012),Orlando,Florida,USA,March 2012

7 Ren W,Zhao Q,Swami A.Connectivity of heterogeneous wireless networks.IEEE Transactions on Information Theory,2011,57(7):4315～4332

8 Ao W C,Chen K C.Cognitive radio-enabled network-based cooperation:from a connectivity perspective.IEEE Journal on Selected Areas in Communications,2012,30(10):1969～1982

9 Lu D,Huang X,Li P,et al.Connectivity of large-scale cognitive radio Ad Hoc networks.IEEE INFOCOM,2012(1)

10 Wang P,Akyildiz I F,Al-Dhelaan A M.Percolation theory based connectivity and latency analysis of cognitive radio Ad Hoc networks.Wireless Networks,2011(17):659～669

11 Li D,Gross J.Robust clustering of Ad Hoc cognitive radio networks under opportunistic spectrum access.Proceedings of IEEE International Conference on Communication,Kyoto,Japan,Jun 2011

12 Liu S S,Lazos L,Krunz M.Cluster-based control channel allocation in opportunistic cognitive radio networks.IEEE Transactions on Mobile Computing,2012,11(10):1436～1449

13 Srinivasa S,Hartin M.Distance distributions in finite uniformly random networks:theory and applications.IEEE Transactions on Vehicular Technology,2010,59(2):940～948

14 Erdos P,Renyi A.On the evolution of random graphs.Publ Math Inst Hungary Acad Sci,1960(5):17～61

15 Achlioptas D,Souza R M D,Spencer J.Explosive percolation in random networks.Science,2009(323)

16 Serra M C.A Multi-Type Branching Processes Approach to the Evolutionary Dynamics of Escape,2007