基于Ad Hoc網(wǎng)絡(luò)覆蓋模型的信道分配策略及其抗毀性分析

潘 立 彥

(上海建橋?qū)W院 商學(xué)院, 上海 201306)

0 引 言

圖1 多跳無線Ad Hoc網(wǎng)絡(luò)示例Fig.1 Example of multi-hop wireless Ad Hoc network

隨著無線網(wǎng)絡(luò)技術(shù)的迅速發(fā)展, 人們?cè)絹碓絻A向于使用無線移動(dòng)終端進(jìn)行溝通與通信. Ad Hoc網(wǎng)絡(luò)與普通的固定網(wǎng)絡(luò)相比, 無需建立固定通信網(wǎng)絡(luò)基礎(chǔ)設(shè)施, 且無需設(shè)置任何中心控制節(jié)點(diǎn)[1]. 與移動(dòng)網(wǎng)絡(luò)相比, Ad Hoc網(wǎng)絡(luò)中的所有節(jié)點(diǎn)地位均等, 是各網(wǎng)絡(luò)節(jié)點(diǎn)相互協(xié)作, 通過無線鏈路交換信息的多跳無線網(wǎng)絡(luò)[2], 如圖1所示. 在Ad Hoc網(wǎng)絡(luò)中, 各節(jié)點(diǎn)之間可根據(jù)移動(dòng)終端需要實(shí)現(xiàn)的功能, 靈活自由構(gòu)建各種Ad Hoc網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu). 為了保持整體網(wǎng)絡(luò)系統(tǒng)的穩(wěn)定性和可靠性, 這種對(duì)等式網(wǎng)絡(luò)的規(guī)模一般較小[3]. 同時(shí), 由于各節(jié)點(diǎn)之間的功能相互獨(dú)立, 通過算法協(xié)調(diào)各自的行為, 因而每個(gè)節(jié)點(diǎn)發(fā)生故障后都不會(huì)妨礙其他節(jié)點(diǎn), 更不會(huì)影響整體網(wǎng)絡(luò)的運(yùn)行, 抗毀性較強(qiáng)[4]. Ad Hoc網(wǎng)絡(luò)在拓?fù)浣Y(jié)構(gòu)、 網(wǎng)絡(luò)組織及服務(wù)協(xié)議等方面的特點(diǎn), 使其可靈活擴(kuò)展到通信系統(tǒng)中的任何領(lǐng)域[5-9]. 無線Ad Hoc網(wǎng)絡(luò)的區(qū)域劃分和資源分配是困擾網(wǎng)絡(luò)建設(shè)的問題. 因此, 提出一種有效的數(shù)學(xué)模型對(duì)解決該問題有重要意義.

本文從無線Ad Hoc網(wǎng)絡(luò)構(gòu)建的實(shí)際問題出發(fā), 先對(duì)無線網(wǎng)絡(luò)覆蓋模型進(jìn)行建模, 再在覆蓋模型的基礎(chǔ)上進(jìn)一步考察無線Ad Hoc網(wǎng)絡(luò)的穩(wěn)定性和可靠性. 實(shí)際問題來源于符合假設(shè)條件的一個(gè)特定1 000×1 000(面積單位)的正方形區(qū)域, 需要在該正方形區(qū)域內(nèi)構(gòu)建一個(gè)Ad Hoc網(wǎng)絡(luò)[10].

1 數(shù)學(xué)模型的建立與求解

由于Ad Hoc網(wǎng)絡(luò)采用節(jié)點(diǎn)、 跳覆蓋區(qū), 其覆蓋面積是一個(gè)圓, 覆蓋整個(gè)服務(wù)區(qū)時(shí)不允許留空隙, 即不允許出現(xiàn)盲區(qū), 而在一個(gè)圓形的跳覆蓋區(qū), 會(huì)出現(xiàn)多個(gè)圓域相交, 有效覆蓋區(qū)實(shí)際上是圓的內(nèi)接多邊形. 因此如何確定圓域的相交方案, 用最少的覆蓋圓數(shù)量保證所有區(qū)域被圓域覆蓋是問題的關(guān)鍵.

要將邊長(zhǎng)為1 000長(zhǎng)度單位的正方形區(qū)域用若干半徑為100長(zhǎng)度單位的圓完全覆蓋. 從正方形和圓的幾何形狀出發(fā), 為找到覆蓋圓的最優(yōu)交疊方案, 本文主要考慮如下幾方面：

1) 圖形自身的有效面積越大越好, 這樣對(duì)同樣大小的服務(wù)區(qū)所需的區(qū)數(shù)就越少, 故所需的信道也越少(為避免同頻干擾, 相鄰小區(qū)的機(jī)站使用頻率應(yīng)不同)；

2) 重疊區(qū)越小越好, 重疊區(qū)的面積越小, 寬度越窄, 相鄰頻道(相鄰小區(qū)所使用的兩個(gè)頻率)干擾越??； 但必須給定覆蓋比例, 以作為中轉(zhuǎn)節(jié)點(diǎn)的使用；

3) 相鄰小區(qū)中心點(diǎn)的距離(中心間距)越大越好, 可減少同頻干擾.

模型假設(shè)如下：

1) 假設(shè)需要覆蓋正方形區(qū)域的地面足夠平坦, 且節(jié)點(diǎn)的覆蓋區(qū)為圓形；

2) 對(duì)覆蓋正方形區(qū)域的圓, 如果出現(xiàn)兩個(gè)圓相切的臨界情形, 則視為這兩個(gè)圓不相交；

3) 不考慮地形對(duì)信號(hào)中值傳輸損耗的影響, 不考慮節(jié)點(diǎn)的高度, 即將發(fā)射源視為點(diǎn)發(fā)射源；

4) 忽略天氣變化、 地面反射等因素對(duì)電磁波的干擾；

5) 不考慮建筑物等的穿透性；

6) 在基站覆蓋的圓域內(nèi)能保證信號(hào)的正常接收；

圖2 圓覆蓋示意圖Fig.2 Schematic diagram of round cover

7) 點(diǎn)在隨機(jī)運(yùn)動(dòng)中, 如果碰到正方形區(qū)域的邊界, 則向相反方向運(yùn)動(dòng).

1.1 模型參數(shù)

該問題是用固定大小的圓對(duì)正方形區(qū)域進(jìn)行覆蓋, 要獲得最合理的圓覆蓋方案, 首先需計(jì)算出相交部分在圓中對(duì)應(yīng)位置的相應(yīng)參數(shù). 如圖2所示, 需確定3個(gè)未知參數(shù)r,d,θ. 其中：R為覆蓋圓的半徑；r和d分別為圓相交陰影部分的兩條相交弦長(zhǎng)；θ為相交弦d對(duì)應(yīng)的圓心角.

根據(jù)平面解析幾何的相關(guān)原理, 可知

相交陰影部分的面積為S1=2×[θR2-d×(R-r)], 覆蓋圓的面積為S=πR2.

1.2 求解覆蓋區(qū)域圓的最少數(shù)量

在已知覆蓋圓的半徑R=100, 相交比例為k≥5%的條件下, 首先可建立如下關(guān)于r的不等式：

計(jì)算可得:r≥12.167;θ≥28.558°；d≥47.805.

為了確定合理的圓覆蓋方案, 需要對(duì)所有可能的圓相交方案進(jìn)行比較分析. 考慮到需要圓的數(shù)量要盡可能少, 所以, 需定義圓組合的利用率, 該利用率應(yīng)體現(xiàn)如下兩方面的內(nèi)容：

1) 在滿足重合比率要求的情形下, 相鄰圓的重合部分要盡可能的??；

2) 能夠覆蓋的區(qū)域面積要大. 因此, 定義利用率為

利用率越高, 組合方案越好. 其中, 有效覆蓋面積表示由正方形區(qū)域的邊界或相鄰圓的交線所包圍的區(qū)域, 由于正方形區(qū)域內(nèi)覆蓋圓的內(nèi)接多邊形均由與其相鄰的圓相交線組成, 所以在固定數(shù)量的圓組合中, 利用率最高的圓組合是： 這些圓的交線可構(gòu)成某個(gè)圓的內(nèi)接正多邊形[11].

表1 不同圓覆蓋利用率的對(duì)比圖

表2 六邊形組合的利用率

圖3 六邊形的對(duì)稱圖Fig.3 Symmetric graphs of hexagons

1.3 確定最少數(shù)量圓的覆蓋

在圓相交比例為5%的情形下, 使用六邊形鋪設(shè)有如圖4所示的兩種方法. 運(yùn)用MATLAB編程進(jìn)行計(jì)算, 結(jié)果顯示共使用45個(gè)圓實(shí)現(xiàn)了對(duì)正方形區(qū)域的覆蓋, 如圖5所示.

圖4 運(yùn)用正六邊形進(jìn)行覆蓋的邊界Fig.4 Boundary covered by regular hexagon

圖5 相交比例為5%情形下的覆蓋結(jié)果Fig.5 Coverage results of intersection proportion 5% case

1.4 信道的分配方案

分給每個(gè)圓域不同的信道, 用盡可能少的信道數(shù)滿足對(duì)有公共部分圓域分配不同的信道. 該問題可歸結(jié)為圖論中圖的染色問題[13-14], 即使用最少數(shù)量的顏色對(duì)圖進(jìn)行染色, 保證相鄰區(qū)域顏色不同. 由五色定理和四色猜想[15]比較分析可知, 使用固定大小的圓對(duì)矩形區(qū)域進(jìn)行覆蓋時(shí), 如果采用正六邊形對(duì)矩形區(qū)域進(jìn)行分區(qū), 最多使用3種顏色即可保證相鄰區(qū)域的顏色不同. 圖6為使用六邊形對(duì)矩形區(qū)域進(jìn)行覆蓋的一個(gè)分區(qū)單元, 整個(gè)矩形區(qū)域均由一系列這樣的分區(qū)單元構(gòu)成. 該分區(qū)單元的中心是節(jié)點(diǎn)A, 將該節(jié)點(diǎn)所在的3個(gè)相鄰區(qū)域分別涂上紅、 黃、 藍(lán)不同的顏色, 則當(dāng)節(jié)點(diǎn)B作為一個(gè)分區(qū)單元的中心時(shí), 其所在的另一個(gè)區(qū)域應(yīng)被涂上與區(qū)域1相同的顏色, 以保證與其相鄰的3個(gè)區(qū)域顏色不同. 依次類推, 可實(shí)現(xiàn)用3種顏色對(duì)所有區(qū)域進(jìn)行染色, 并保證所有的相鄰區(qū)域顏色不同. 根據(jù)確定的染色方案對(duì)圖5所有區(qū)域進(jìn)行染色, 即可得所需如圖7所示的信道分配方案, 因此, 使用3種信道(標(biāo)注為紅、 黃、 藍(lán))即可保證正常的通信.

圖6 正六邊形進(jìn)行覆蓋的分區(qū)單元Fig.6 Partition unit of regular hexagonal coverage

圖7 相交比例為5%情形下的信道分配方案Fig.7 Channel allocation scheme of intersection proportion 5% case

1.5 網(wǎng)絡(luò)的抗毀性分析

因每個(gè)公共部分中心與相應(yīng)圓心各有一個(gè)節(jié)點(diǎn), 通過MATLAB編程, 可仿真出相交比例為5%情形下各節(jié)點(diǎn)與六邊形覆蓋區(qū)域的位置關(guān)系, 如圖8所示. 對(duì)于六邊形區(qū)域, 其中心有一個(gè)節(jié)點(diǎn), 6個(gè)邊中心各有一個(gè)節(jié)點(diǎn), 除在區(qū)域邊界上節(jié)點(diǎn)外的其他每個(gè)節(jié)點(diǎn), 均與周圍的6個(gè)節(jié)點(diǎn)相連接. 在關(guān)系圖的基礎(chǔ)上進(jìn)一步構(gòu)建相應(yīng)的網(wǎng)絡(luò)圖. 統(tǒng)計(jì)分析表明, 在這種情形下, 覆蓋圓的個(gè)數(shù)為45個(gè), 節(jié)點(diǎn)數(shù)為152個(gè), 節(jié)點(diǎn)的連接邊為409條.

由于該正方形區(qū)域內(nèi)的任何位置都能被網(wǎng)絡(luò)覆蓋, 因此如果在某個(gè)位置沒有網(wǎng)絡(luò)覆蓋, 則該位置所在的覆蓋圓內(nèi)不存在節(jié)點(diǎn). 因此可得網(wǎng)絡(luò)損壞概率的表達(dá)式[16]為

對(duì)圖8中的所有覆蓋圓進(jìn)行標(biāo)號(hào), 得到各覆蓋區(qū)域的標(biāo)號(hào)如圖9所示. 表3列出了統(tǒng)計(jì)各圓形覆蓋區(qū)域內(nèi)的節(jié)點(diǎn)數(shù), 總節(jié)點(diǎn)數(shù)n=152. 由表3可見, 由于各區(qū)域內(nèi)的節(jié)點(diǎn)數(shù)目不同, 所以這些區(qū)域內(nèi)節(jié)點(diǎn)的去除對(duì)各區(qū)域內(nèi)網(wǎng)絡(luò)的連通性影響也不同. 在考慮網(wǎng)絡(luò)的抗毀性時(shí), 本文根據(jù)需要隨機(jī)抽掉2%,5%,10%,15%的節(jié)點(diǎn), 對(duì)4種網(wǎng)絡(luò)連通情形下的網(wǎng)絡(luò)損壞概率分別進(jìn)行分析. 為討論方便, 對(duì)表3中的數(shù)據(jù)進(jìn)行整理列于表4.

圖8 相交比例為5%情形下節(jié)點(diǎn)與覆蓋區(qū)域的位置關(guān)系Fig.8 Location relationship between nodes and coverage areas of intersection proportion 5% case

圖9 相交比例為5%情形下節(jié)點(diǎn)與覆蓋區(qū)域的標(biāo)號(hào)Fig.9 Label of nodes and coverage areas of intersection proportion 5% case

標(biāo)號(hào)1234567891011121314151617181920212223節(jié)點(diǎn)數(shù)45555436363455554444667標(biāo)號(hào)24252627282930313233343536373839404142434445節(jié)點(diǎn)數(shù)7777777777777777777777

表4 節(jié)點(diǎn)統(tǒng)計(jì)數(shù)據(jù)匯總

情形1) 抽掉節(jié)點(diǎn)的比例為2%, 則抽掉的節(jié)點(diǎn)數(shù)目為m1=[152×2%]=3.

情形2) 抽掉節(jié)點(diǎn)的比例為5%, 則抽掉的節(jié)點(diǎn)數(shù)目為m2=[152×5%]=8.

導(dǎo)致網(wǎng)絡(luò)不通的情形, 即出現(xiàn)某個(gè)區(qū)域內(nèi)的所有節(jié)點(diǎn)均被去掉的情形. 由表3和表4可見, 由于去掉的節(jié)點(diǎn)數(shù)為8, 以上區(qū)域均可能出現(xiàn)沒有網(wǎng)絡(luò)覆蓋的情形. 下面進(jìn)行分類討論：

① 節(jié)點(diǎn)數(shù)為3的區(qū)域有一個(gè)出現(xiàn)無網(wǎng)絡(luò)覆蓋情形的數(shù)目為

根據(jù)f1～f6的表達(dá)式, 可得在該情形下網(wǎng)絡(luò)損壞的概率為

情形3) 抽掉節(jié)點(diǎn)的比例為10%, 則抽掉的節(jié)點(diǎn)數(shù)目為m3=[152×10%]=15.

② 節(jié)點(diǎn)數(shù)為6的區(qū)域至少有一個(gè)出現(xiàn)無網(wǎng)絡(luò)覆蓋情形的數(shù)目為

③ 節(jié)點(diǎn)數(shù)為5的區(qū)域至少有一個(gè)出現(xiàn)無網(wǎng)絡(luò)覆蓋情形的數(shù)目為

④ 節(jié)點(diǎn)數(shù)為4的區(qū)域至少有一個(gè)出現(xiàn)無網(wǎng)絡(luò)覆蓋情形的數(shù)目為

于是在該情形下的網(wǎng)絡(luò)損壞概率為

情形4) 抽掉節(jié)點(diǎn)的比例為15%, 則抽掉的節(jié)點(diǎn)數(shù)目為m4=[152×15%]=23.

② 節(jié)點(diǎn)數(shù)為6的區(qū)域至少有一個(gè)出現(xiàn)無網(wǎng)絡(luò)覆蓋情形的數(shù)目為

③ 節(jié)點(diǎn)數(shù)為5的區(qū)域至少有一個(gè)出現(xiàn)無網(wǎng)絡(luò)覆蓋情形的數(shù)目為

④ 節(jié)點(diǎn)數(shù)為4的區(qū)域至少有一個(gè)出現(xiàn)無網(wǎng)絡(luò)覆蓋情形的數(shù)目為

于是在該情形下的網(wǎng)絡(luò)損壞概率為

由情形1)～情形4)的計(jì)算結(jié)果可見, 隨著隨機(jī)抽掉節(jié)點(diǎn)數(shù)目的增加, 網(wǎng)絡(luò)抗毀性能逐漸降低, 即網(wǎng)絡(luò)發(fā)生不連通的可能性增大.

綜上所述, 本文通過對(duì)Ad Hoc網(wǎng)絡(luò)實(shí)際問題進(jìn)行數(shù)學(xué)建模, 并結(jié)合圖論的相關(guān)理論, 可得如下結(jié)論：

1) 在正方形的中間區(qū)域?qū)τ趫A覆蓋方案, 正六邊形的利用率最高, 所以應(yīng)盡可能多采用正六邊形對(duì)區(qū)域進(jìn)行覆蓋.

2) 為盡可能減少覆蓋圓的數(shù)量, 正方形區(qū)域的邊界和六邊形的相交位置應(yīng)盡可能出現(xiàn)在六邊形的對(duì)稱位置. 在相交比例為5%的情形下, 運(yùn)用MATLAB編程進(jìn)行計(jì)算, 得到了使用45個(gè)圓便可實(shí)現(xiàn)對(duì)正方形區(qū)域的覆蓋.

3) 運(yùn)用圖的染色理論得出僅需使用3個(gè)信道即可保證有相交公共部分的圓域擁有不同的信道要求.

4) 運(yùn)用概率統(tǒng)計(jì)的思想, 分析討論了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的抗毀性. 計(jì)算結(jié)果表明, 該思想是評(píng)判網(wǎng)絡(luò)抗毀性的一種可行性標(biāo)準(zhǔn). 隨著去掉節(jié)點(diǎn)數(shù)量的增加, 網(wǎng)絡(luò)的毀壞性增大, 與實(shí)際應(yīng)用相吻合.

本文采用的方法可擴(kuò)展到不同網(wǎng)絡(luò)覆蓋面積、 不同相交比例的區(qū)域劃分和信道分配及網(wǎng)絡(luò)穩(wěn)定性的問題中, 仿真和實(shí)驗(yàn)結(jié)果也證明了該數(shù)學(xué)模型的有效性及控制方法的可行性.