無(wú)線Mesh網(wǎng)絡(luò)結(jié)構(gòu)的拓?fù)淇刂撇呗?/h1>
2011-05-11 07:29:50鄧建良胡松華郭建丁
無(wú)線電通信技術(shù) 2011年4期
鄧建良，王 景，胡松華，郭建丁
（重慶大學(xué)通信工程學(xué)院，重慶400044）
0 引言
拓?fù)淇刂茩C(jī)制從研究方向可歸納為節(jié)點(diǎn)功率控制和層次型拓?fù)浣Y(jié)構(gòu)組織兩類(lèi)。無(wú)線網(wǎng)絡(luò)中的層次型拓?fù)浣Y(jié)構(gòu)由于具有通信量少、可擴(kuò)展性強(qiáng)、能量利用效率高及適合大規(guī)模部署等特點(diǎn)，成為當(dāng)前拓?fù)淇刂蒲芯康闹攸c(diǎn)。
提出一種新的網(wǎng)絡(luò)架構(gòu)并在此基礎(chǔ)上研究一種虛擬的層次化拓?fù)淇刂撇呗?，主要考慮相鄰簇間的自身負(fù)載和相互轉(zhuǎn)發(fā)負(fù)載的平衡，提高網(wǎng)絡(luò)的公平性、提升鏈路可靠性以及提高路由算法的有效性。
1 問(wèn)題說(shuō)明
該文研究的前提是，無(wú)線Mesh網(wǎng)絡(luò)的簇都分配了足夠等量的信道資源，從而保障通信的公平性和鏈路的可靠性。在一定節(jié)點(diǎn)分布的情況下，節(jié)點(diǎn)不但自身通信產(chǎn)生負(fù)載，而且節(jié)點(diǎn)同時(shí)要轉(zhuǎn)發(fā)產(chǎn)生負(fù)載。圖1中，簇1和簇4僅僅只是簇內(nèi)節(jié)點(diǎn)間通信和與內(nèi)外簇間的通信。而簇2和簇3不僅要承擔(dān)自身通信與簇間通信，還要轉(zhuǎn)發(fā)簇間的通信。簇2和簇3的通信負(fù)載相對(duì)大很多，網(wǎng)絡(luò)中處于中間轉(zhuǎn)發(fā)位置的節(jié)點(diǎn)承擔(dān)相對(duì)較多的負(fù)載，缺乏公平性。同時(shí)網(wǎng)絡(luò)的容量和可靠性依賴(lài)于中間位置的簇。
圖1 簇的通信狀況
新的劃分簇的方法主要從2個(gè)方面來(lái)分析:覆蓋范圍和容量。其次簇大小的劃分也必須考慮信道資源的分配，盡量使其每個(gè)虛擬簇內(nèi)的節(jié)點(diǎn)都滿(mǎn)足信道匹配。必須要強(qiáng)調(diào)的是網(wǎng)絡(luò)考慮覆蓋范圍，同時(shí)要達(dá)到公平性的網(wǎng)絡(luò)基本要求。
根據(jù)新的網(wǎng)絡(luò)架構(gòu)—虛擬層次無(wú)線Mesh網(wǎng)絡(luò)結(jié)構(gòu)，提出一種拓?fù)淇刂撇呗?，拓?fù)淇刂撇呗灾饕獞?yīng)用于簇間的控制。在極值情況下，其拓?fù)淇刂颇芰坑驗(yàn)椤Ｔ趫D2中，一個(gè)點(diǎn)代表一個(gè)簇。這是一個(gè)由7個(gè)簇組成的鏈型拓?fù)?。在這種情形下，每個(gè)簇僅僅為相鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)報(bào)和發(fā)送自身與其他節(jié)點(diǎn)的通信數(shù)據(jù)。簇1和簇7與其他簇的通信都經(jīng)過(guò)其相鄰簇轉(zhuǎn)發(fā)，而其本身僅僅承擔(dān)簇內(nèi)部通信和與相鄰簇的通信。n為網(wǎng)絡(luò)某一側(cè)中虛擬簇的數(shù)量;H（d）為虛擬節(jié)點(diǎn)ci與ci-1之間的鏈路容量;li為節(jié)點(diǎn)虛擬簇半徑;R（li）為li內(nèi)部流量負(fù)載其中RD是指每個(gè)用戶(hù)內(nèi)部平均流量，DM指節(jié)點(diǎn)密度虛擬簇2個(gè)簇間流量負(fù)載其中RZ是指每個(gè)用戶(hù)內(nèi)部平均流量，DM指節(jié)點(diǎn)密度;虛擬簇中所有的流量負(fù)載應(yīng)該受到蜂窩飽和吞吐率的限制，即:R（li）≤Rb（k），其中，Rb（k）表示飽和吞吐率。根據(jù)文獻(xiàn)[4]中的方法，對(duì)于用戶(hù)數(shù)量k，IEEE 802.11 b WLAN的單元飽和吞吐量可以使用曲線擬合的方法獲得，即則簇2轉(zhuǎn)發(fā)的流量是簇3轉(zhuǎn)發(fā)流量是簇4轉(zhuǎn)發(fā)流量是在等半徑的情況下，內(nèi)部流量負(fù)載和虛擬簇間流量負(fù)載是相等的。所以簇2的轉(zhuǎn)發(fā)流量為5R（lin），簇3轉(zhuǎn)發(fā)流量為8R（lin），簇4的轉(zhuǎn)發(fā)流量為9R（lin）.
圖2 簇?cái)?shù)目為7的鏈型拓?fù)浜娃D(zhuǎn)發(fā)流量圖
可以很明顯看出簇的流量負(fù)載是不均衡的，網(wǎng)絡(luò)的性能將受到中間簇的限制。所以該文提出一種新的簇劃分方法，根據(jù)其總的流量來(lái)改變簇的覆蓋范圍，達(dá)到簇間流量和轉(zhuǎn)發(fā)流量之和在每個(gè)簇中都是相等的。由此其簇的劃分為圖3所示。
圖3 負(fù)載均衡簇的分配方式
將轉(zhuǎn)發(fā)流量大簇縮小其覆蓋范圍，保障簇內(nèi)部節(jié)點(diǎn)能夠正常通信，從而保障通信的可靠性和公平性。它們覆蓋半徑之間關(guān)系是:
以2種簇拓?fù)溥M(jìn)行研究，圖4和圖5分別是虛擬簇半徑相等和虛擬簇半徑逐漸增大的拓?fù)?，為便于分析，用位于小區(qū)中心的虛擬節(jié)點(diǎn)表示每個(gè)小區(qū)，實(shí)際上節(jié)點(diǎn)可位于小區(qū)內(nèi)任何位置。為了用連接圖來(lái)表示這種虛擬層次網(wǎng)絡(luò)結(jié)構(gòu)的拓?fù)?，鄰居虛擬節(jié)點(diǎn)用一條邊連接，均給出了對(duì)應(yīng)的Mesh網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。
圖4 虛擬簇半徑相等的拓?fù)湫问?/p>
圖5 虛擬簇逐漸增大的拓?fù)湫问?/p>
從組合圖論的角度，可以知道簇半徑相等和簇半徑逐漸增大拓?fù)湓诘确謳捝鲜窍嗤?，所考慮的是鏈路的等分帶寬，但是，如果考慮信道資源分配，虛擬簇中節(jié)點(diǎn)有些鏈路不是活躍的;如果考慮鏈路的活躍性，則可以知道簇半徑逐漸增大的拓?fù)湓诘确謳捫阅苌蟽?yōu)于等半徑拓?fù)?，因?yàn)樵诶硐肭闆r下，簇半徑逐漸增大的拓?fù)淇梢允切诺蕾Y源分配和簇節(jié)點(diǎn)完全匹配。
2 算法規(guī)則
在圖3中，由于簇的劃分是對(duì)稱(chēng)的，考慮其中的上半部分，定義一些參數(shù):n為網(wǎng)絡(luò)某一側(cè)中虛擬簇的數(shù)量;di為小區(qū)中心的虛擬節(jié)點(diǎn)ci于ci-1之間的距離;H（di）是虛擬節(jié)點(diǎn)ci與ci-1之間在間距為di情況下的鏈路容量;li為節(jié)點(diǎn)ci的蜂窩半徑;R（li）為到達(dá)ci的流量負(fù)載，其中RD是指每個(gè)用戶(hù)平均流量，DM指節(jié)點(diǎn)密度;δ（n）為代價(jià)函數(shù)，指部署一個(gè)虛擬簇所需代價(jià);R（s）是指從其他虛擬簇接收到的流量與本簇轉(zhuǎn)發(fā)出流量差值。
接下來(lái)，介紹2種虛擬簇劃分策略:等半徑虛擬簇的劃分和半徑逐漸增大的劃分策略。2個(gè)虛擬中心節(jié)點(diǎn)的間距可以描述如下:di=li+li+1，i=1，2，…，n。虛擬簇中所有的流量負(fù)載應(yīng)該受到蜂窩飽和吞吐率的限制，即:R（li）≤Rb（k），其中，Rb（k）表示飽和吞吐率。根據(jù)文獻(xiàn)[3]中的方法，對(duì)于用戶(hù)數(shù)量k，IEEE 802.11b WLAN的單元飽和吞吐量可以使用曲線擬合的方法獲得，即:Rb（k）=b1eb3k+b2eb4k。故虛擬簇的總流量為
等半徑情況下:
半徑逐漸增大情況下:
在該網(wǎng)絡(luò)中，虛擬簇的劃分問(wèn)題可以描述成一個(gè)混合整數(shù)非線性編程（MINLP）問(wèn)題，其中決策變量包括n和l0，l1，…，ln。MINLP問(wèn)題的目標(biāo)是使虛擬簇的總體負(fù)載流量與劃分簇的代價(jià)函數(shù)比值達(dá)到最大化。于是有目標(biāo)函數(shù):
對(duì)于等半徑情況下有目標(biāo)函數(shù):
半徑逐漸增大情況下有目標(biāo)函數(shù):
算法流程如圖6所示。
定理1:任何滿(mǎn)足簇的域內(nèi)連通性和互通性的模型，必定具有拓?fù)溥B通性。
證明:?u，u′∈V，假定u∈Vi，u′∈Vj，因拓?fù)渚哂写氐挠騼?nèi)連通性和互通性，則u和u′之間一定存在一條路徑（u，ci，…，ck，cm，…，cj，u′）。
定理2:當(dāng)d滿(mǎn)足時(shí)，拓?fù)鋬?nèi)簇群必定滿(mǎn)足域內(nèi)連通性和簇間鄰接可達(dá)性。
圖6 算法流程
證明:由簇滿(mǎn)足域內(nèi)連通性則必有d≤dmax。假定簇Cj具有最大規(guī)模d，且d（k，m）=d，其中k，m∈Vj，因此可知簇Cj內(nèi)其他節(jié)點(diǎn)必位于圖所示區(qū)域akcm內(nèi)，為滿(mǎn)足簇間鄰接可達(dá)性，若節(jié)點(diǎn)a與b可直接通信，必能保證相鄰簇區(qū)域內(nèi)任意2節(jié)點(diǎn)可直接通信，由圖易得簇群必定滿(mǎn)足域內(nèi)連通性和簇間鄰接可達(dá)性，證畢。
圖7 簇規(guī)模與簇區(qū)域關(guān)系圖
3 結(jié)束語(yǔ)
從拓?fù)淇刂瞥霭l(fā)，探討一種能夠增大網(wǎng)絡(luò)容量且保證網(wǎng)絡(luò)可靠性的拓?fù)浣Y(jié)構(gòu)。通過(guò)對(duì)隨機(jī)拓?fù)浜?種規(guī)則拓?fù)涞木W(wǎng)絡(luò)容量和拓?fù)涮卣鞣治?，表明了?guī)則拓?fù)湓跓o(wú)線Mesh網(wǎng)絡(luò)應(yīng)有的優(yōu)良性能。該文提出的方案對(duì)現(xiàn)有無(wú)線Mesh網(wǎng)絡(luò)結(jié)構(gòu)改動(dòng)較小，主要工作是在網(wǎng)絡(luò)幀結(jié)構(gòu)中添加虛擬分簇標(biāo)志和組網(wǎng)拓?fù)浞绞降日{(diào)整，易于工程實(shí)現(xiàn)。
[1]SANTI P.Silence is golden with high probability:Maintaining a connected backbone in wireless sensor networks[C]//1st European Workshopon WirelessSensor Network，2004，2（9）:9-20.
[2]XIONG Shu-ming，WANG Liang-Min，WU Ji-Ying.Energyefficient hierarchical topology control in wireless sensor networks using time slots[C]//Proceedings of the Seventh International Conference on Machine Learning and Cybernetics，Kunming，12-15 July 2008:33-39.
[3]徐俊明.組合網(wǎng)絡(luò)理論[M].北京:科學(xué)技術(shù)出版社，2005.
[4]PERILLO M，ZHAO C，HEINZELMAN W.On the problem of unbalanced load distribution in wireless sensor networks[C]//Proceedings of the IEEE Global Telecommunications Conference Workshops.Piscataway，NJ，USA:IEEE，2004:74-79.
[5]CHEN J C.Measured performance of 5GHz 802.11a wireless LAN systems[S].White Paper of Atheros Communications，2001.8.
[6]GUPTA P，KUMAR P R.Thecapacityofwireless networks[J].IEEE Trans.Inform.Theory，2000，46（2）:388-404.
[7]TOUMPIS S，GOLDSMITH A J.Capacity regions for wireless ad hocnetworks[J].IEEE Transactions on Wireless Communications，2003，2（4）:736-748.
[8]SILVESTER J，KLEINROCK L.On the capacity of multichip slotted ALOHA networks with regular structure[J].IEEE Trans.Commun.，1983，31（8）:974-982.
猜你喜歡
偏序集及其相關(guān)拓?fù)涞倪B通性?湖南文理學(xué)院學(xué)報(bào)(自然科學(xué)版)(2022年4期)2022-10-13 14:03:54 擬莫比烏斯映射與擬度量空間的連通性數(shù)學(xué)物理學(xué)報(bào)(2019年5期)2019-11-29 07:46:26 一種提高TCP與UDP數(shù)據(jù)流公平性的擁塞控制機(jī)制電腦與電信(2018年12期)2018-03-23 02:37:36 河道-灘區(qū)系統(tǒng)連通性評(píng)價(jià)研究水利規(guī)劃與設(shè)計(jì)(2017年6期)2017-07-18 10:56:27 公平性問(wèn)題例談高中生學(xué)習(xí)·高二版(2016年11期)2016-12-01 20:00:48 高穩(wěn)定被動(dòng)群集車(chē)聯(lián)網(wǎng)連通性研究通信學(xué)報(bào)(2016年11期)2016-08-16 03:20:04 基于互信息的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)北京信息科技大學(xué)學(xué)報(bào)(自然科學(xué)版)(2016年6期)2016-02-27 06:31:53 知識(shí)網(wǎng)絡(luò)結(jié)構(gòu)維對(duì)于創(chuàng)新績(jī)效的作用機(jī)制——遠(yuǎn)程創(chuàng)新搜尋的中介作用管理現(xiàn)代化(2016年3期)2016-02-06 02:04:41 滬港通下A+ H股票網(wǎng)絡(luò)結(jié)構(gòu)演化的實(shí)證分析管理現(xiàn)代化(2016年3期)2016-02-06 02:04:13 復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)比對(duì)算法研究進(jìn)展智能系統(tǒng)學(xué)報(bào)(2015年4期)2015-12-27 09:37:52
鄧建良，王 景，胡松華，郭建丁
（重慶大學(xué)通信工程學(xué)院，重慶400044）
0 引言
拓?fù)淇刂茩C(jī)制從研究方向可歸納為節(jié)點(diǎn)功率控制和層次型拓?fù)浣Y(jié)構(gòu)組織兩類(lèi)。無(wú)線網(wǎng)絡(luò)中的層次型拓?fù)浣Y(jié)構(gòu)由于具有通信量少、可擴(kuò)展性強(qiáng)、能量利用效率高及適合大規(guī)模部署等特點(diǎn)，成為當(dāng)前拓?fù)淇刂蒲芯康闹攸c(diǎn)。
提出一種新的網(wǎng)絡(luò)架構(gòu)并在此基礎(chǔ)上研究一種虛擬的層次化拓?fù)淇刂撇呗?，主要考慮相鄰簇間的自身負(fù)載和相互轉(zhuǎn)發(fā)負(fù)載的平衡，提高網(wǎng)絡(luò)的公平性、提升鏈路可靠性以及提高路由算法的有效性。
1 問(wèn)題說(shuō)明
該文研究的前提是，無(wú)線Mesh網(wǎng)絡(luò)的簇都分配了足夠等量的信道資源，從而保障通信的公平性和鏈路的可靠性。在一定節(jié)點(diǎn)分布的情況下，節(jié)點(diǎn)不但自身通信產(chǎn)生負(fù)載，而且節(jié)點(diǎn)同時(shí)要轉(zhuǎn)發(fā)產(chǎn)生負(fù)載。圖1中，簇1和簇4僅僅只是簇內(nèi)節(jié)點(diǎn)間通信和與內(nèi)外簇間的通信。而簇2和簇3不僅要承擔(dān)自身通信與簇間通信，還要轉(zhuǎn)發(fā)簇間的通信。簇2和簇3的通信負(fù)載相對(duì)大很多，網(wǎng)絡(luò)中處于中間轉(zhuǎn)發(fā)位置的節(jié)點(diǎn)承擔(dān)相對(duì)較多的負(fù)載，缺乏公平性。同時(shí)網(wǎng)絡(luò)的容量和可靠性依賴(lài)于中間位置的簇。
圖1 簇的通信狀況
新的劃分簇的方法主要從2個(gè)方面來(lái)分析:覆蓋范圍和容量。其次簇大小的劃分也必須考慮信道資源的分配，盡量使其每個(gè)虛擬簇內(nèi)的節(jié)點(diǎn)都滿(mǎn)足信道匹配。必須要強(qiáng)調(diào)的是網(wǎng)絡(luò)考慮覆蓋范圍，同時(shí)要達(dá)到公平性的網(wǎng)絡(luò)基本要求。
根據(jù)新的網(wǎng)絡(luò)架構(gòu)—虛擬層次無(wú)線Mesh網(wǎng)絡(luò)結(jié)構(gòu)，提出一種拓?fù)淇刂撇呗?，拓?fù)淇刂撇呗灾饕獞?yīng)用于簇間的控制。在極值情況下，其拓?fù)淇刂颇芰坑驗(yàn)椤Ｔ趫D2中，一個(gè)點(diǎn)代表一個(gè)簇。這是一個(gè)由7個(gè)簇組成的鏈型拓?fù)?。在這種情形下，每個(gè)簇僅僅為相鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)報(bào)和發(fā)送自身與其他節(jié)點(diǎn)的通信數(shù)據(jù)。簇1和簇7與其他簇的通信都經(jīng)過(guò)其相鄰簇轉(zhuǎn)發(fā)，而其本身僅僅承擔(dān)簇內(nèi)部通信和與相鄰簇的通信。n為網(wǎng)絡(luò)某一側(cè)中虛擬簇的數(shù)量;H（d）為虛擬節(jié)點(diǎn)ci與ci-1之間的鏈路容量;li為節(jié)點(diǎn)虛擬簇半徑;R（li）為li內(nèi)部流量負(fù)載其中RD是指每個(gè)用戶(hù)內(nèi)部平均流量，DM指節(jié)點(diǎn)密度虛擬簇2個(gè)簇間流量負(fù)載其中RZ是指每個(gè)用戶(hù)內(nèi)部平均流量，DM指節(jié)點(diǎn)密度;虛擬簇中所有的流量負(fù)載應(yīng)該受到蜂窩飽和吞吐率的限制，即:R（li）≤Rb（k），其中，Rb（k）表示飽和吞吐率。根據(jù)文獻(xiàn)[4]中的方法，對(duì)于用戶(hù)數(shù)量k，IEEE 802.11 b WLAN的單元飽和吞吐量可以使用曲線擬合的方法獲得，即則簇2轉(zhuǎn)發(fā)的流量是簇3轉(zhuǎn)發(fā)流量是簇4轉(zhuǎn)發(fā)流量是在等半徑的情況下，內(nèi)部流量負(fù)載和虛擬簇間流量負(fù)載是相等的。所以簇2的轉(zhuǎn)發(fā)流量為5R（lin），簇3轉(zhuǎn)發(fā)流量為8R（lin），簇4的轉(zhuǎn)發(fā)流量為9R（lin）.
圖2 簇?cái)?shù)目為7的鏈型拓?fù)浜娃D(zhuǎn)發(fā)流量圖
可以很明顯看出簇的流量負(fù)載是不均衡的，網(wǎng)絡(luò)的性能將受到中間簇的限制。所以該文提出一種新的簇劃分方法，根據(jù)其總的流量來(lái)改變簇的覆蓋范圍，達(dá)到簇間流量和轉(zhuǎn)發(fā)流量之和在每個(gè)簇中都是相等的。由此其簇的劃分為圖3所示。
圖3 負(fù)載均衡簇的分配方式
將轉(zhuǎn)發(fā)流量大簇縮小其覆蓋范圍，保障簇內(nèi)部節(jié)點(diǎn)能夠正常通信，從而保障通信的可靠性和公平性。它們覆蓋半徑之間關(guān)系是:
以2種簇拓?fù)溥M(jìn)行研究，圖4和圖5分別是虛擬簇半徑相等和虛擬簇半徑逐漸增大的拓?fù)?，為便于分析，用位于小區(qū)中心的虛擬節(jié)點(diǎn)表示每個(gè)小區(qū)，實(shí)際上節(jié)點(diǎn)可位于小區(qū)內(nèi)任何位置。為了用連接圖來(lái)表示這種虛擬層次網(wǎng)絡(luò)結(jié)構(gòu)的拓?fù)?，鄰居虛擬節(jié)點(diǎn)用一條邊連接，均給出了對(duì)應(yīng)的Mesh網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。
圖4 虛擬簇半徑相等的拓?fù)湫问?/p>
圖5 虛擬簇逐漸增大的拓?fù)湫问?/p>
從組合圖論的角度，可以知道簇半徑相等和簇半徑逐漸增大拓?fù)湓诘确謳捝鲜窍嗤?，所考慮的是鏈路的等分帶寬，但是，如果考慮信道資源分配，虛擬簇中節(jié)點(diǎn)有些鏈路不是活躍的;如果考慮鏈路的活躍性，則可以知道簇半徑逐漸增大的拓?fù)湓诘确謳捫阅苌蟽?yōu)于等半徑拓?fù)?，因?yàn)樵诶硐肭闆r下，簇半徑逐漸增大的拓?fù)淇梢允切诺蕾Y源分配和簇節(jié)點(diǎn)完全匹配。
2 算法規(guī)則
在圖3中，由于簇的劃分是對(duì)稱(chēng)的，考慮其中的上半部分，定義一些參數(shù):n為網(wǎng)絡(luò)某一側(cè)中虛擬簇的數(shù)量;di為小區(qū)中心的虛擬節(jié)點(diǎn)ci于ci-1之間的距離;H（di）是虛擬節(jié)點(diǎn)ci與ci-1之間在間距為di情況下的鏈路容量;li為節(jié)點(diǎn)ci的蜂窩半徑;R（li）為到達(dá)ci的流量負(fù)載，其中RD是指每個(gè)用戶(hù)平均流量，DM指節(jié)點(diǎn)密度;δ（n）為代價(jià)函數(shù)，指部署一個(gè)虛擬簇所需代價(jià);R（s）是指從其他虛擬簇接收到的流量與本簇轉(zhuǎn)發(fā)出流量差值。
接下來(lái)，介紹2種虛擬簇劃分策略:等半徑虛擬簇的劃分和半徑逐漸增大的劃分策略。2個(gè)虛擬中心節(jié)點(diǎn)的間距可以描述如下:di=li+li+1，i=1，2，…，n。虛擬簇中所有的流量負(fù)載應(yīng)該受到蜂窩飽和吞吐率的限制，即:R（li）≤Rb（k），其中，Rb（k）表示飽和吞吐率。根據(jù)文獻(xiàn)[3]中的方法，對(duì)于用戶(hù)數(shù)量k，IEEE 802.11b WLAN的單元飽和吞吐量可以使用曲線擬合的方法獲得，即:Rb（k）=b1eb3k+b2eb4k。故虛擬簇的總流量為
等半徑情況下:
半徑逐漸增大情況下:
在該網(wǎng)絡(luò)中，虛擬簇的劃分問(wèn)題可以描述成一個(gè)混合整數(shù)非線性編程（MINLP）問(wèn)題，其中決策變量包括n和l0，l1，…，ln。MINLP問(wèn)題的目標(biāo)是使虛擬簇的總體負(fù)載流量與劃分簇的代價(jià)函數(shù)比值達(dá)到最大化。于是有目標(biāo)函數(shù):
對(duì)于等半徑情況下有目標(biāo)函數(shù):
半徑逐漸增大情況下有目標(biāo)函數(shù):
算法流程如圖6所示。
定理1:任何滿(mǎn)足簇的域內(nèi)連通性和互通性的模型，必定具有拓?fù)溥B通性。
證明:?u，u′∈V，假定u∈Vi，u′∈Vj，因拓?fù)渚哂写氐挠騼?nèi)連通性和互通性，則u和u′之間一定存在一條路徑（u，ci，…，ck，cm，…，cj，u′）。
定理2:當(dāng)d滿(mǎn)足時(shí)，拓?fù)鋬?nèi)簇群必定滿(mǎn)足域內(nèi)連通性和簇間鄰接可達(dá)性。
圖6 算法流程
證明:由簇滿(mǎn)足域內(nèi)連通性則必有d≤dmax。假定簇Cj具有最大規(guī)模d，且d（k，m）=d，其中k，m∈Vj，因此可知簇Cj內(nèi)其他節(jié)點(diǎn)必位于圖所示區(qū)域akcm內(nèi)，為滿(mǎn)足簇間鄰接可達(dá)性，若節(jié)點(diǎn)a與b可直接通信，必能保證相鄰簇區(qū)域內(nèi)任意2節(jié)點(diǎn)可直接通信，由圖易得簇群必定滿(mǎn)足域內(nèi)連通性和簇間鄰接可達(dá)性，證畢。
圖7 簇規(guī)模與簇區(qū)域關(guān)系圖
3 結(jié)束語(yǔ)
從拓?fù)淇刂瞥霭l(fā)，探討一種能夠增大網(wǎng)絡(luò)容量且保證網(wǎng)絡(luò)可靠性的拓?fù)浣Y(jié)構(gòu)。通過(guò)對(duì)隨機(jī)拓?fù)浜?種規(guī)則拓?fù)涞木W(wǎng)絡(luò)容量和拓?fù)涮卣鞣治?，表明了?guī)則拓?fù)湓跓o(wú)線Mesh網(wǎng)絡(luò)應(yīng)有的優(yōu)良性能。該文提出的方案對(duì)現(xiàn)有無(wú)線Mesh網(wǎng)絡(luò)結(jié)構(gòu)改動(dòng)較小，主要工作是在網(wǎng)絡(luò)幀結(jié)構(gòu)中添加虛擬分簇標(biāo)志和組網(wǎng)拓?fù)浞绞降日{(diào)整，易于工程實(shí)現(xiàn)。
[1]SANTI P.Silence is golden with high probability:Maintaining a connected backbone in wireless sensor networks[C]//1st European Workshopon WirelessSensor Network，2004，2（9）:9-20.
[2]XIONG Shu-ming，WANG Liang-Min，WU Ji-Ying.Energyefficient hierarchical topology control in wireless sensor networks using time slots[C]//Proceedings of the Seventh International Conference on Machine Learning and Cybernetics，Kunming，12-15 July 2008:33-39.
[3]徐俊明.組合網(wǎng)絡(luò)理論[M].北京:科學(xué)技術(shù)出版社，2005.
[4]PERILLO M，ZHAO C，HEINZELMAN W.On the problem of unbalanced load distribution in wireless sensor networks[C]//Proceedings of the IEEE Global Telecommunications Conference Workshops.Piscataway，NJ，USA:IEEE，2004:74-79.
[5]CHEN J C.Measured performance of 5GHz 802.11a wireless LAN systems[S].White Paper of Atheros Communications，2001.8.
[6]GUPTA P，KUMAR P R.Thecapacityofwireless networks[J].IEEE Trans.Inform.Theory，2000，46（2）:388-404.
[7]TOUMPIS S，GOLDSMITH A J.Capacity regions for wireless ad hocnetworks[J].IEEE Transactions on Wireless Communications，2003，2（4）:736-748.
[8]SILVESTER J，KLEINROCK L.On the capacity of multichip slotted ALOHA networks with regular structure[J].IEEE Trans.Commun.，1983，31（8）:974-982.
猜你喜歡
湖南文理學(xué)院學(xué)報(bào)(自然科學(xué)版)(2022年4期)2022-10-13 14:03:54
數(shù)學(xué)物理學(xué)報(bào)(2019年5期)2019-11-29 07:46:26
電腦與電信(2018年12期)2018-03-23 02:37:36
水利規(guī)劃與設(shè)計(jì)(2017年6期)2017-07-18 10:56:27
高中生學(xué)習(xí)·高二版(2016年11期)2016-12-01 20:00:48
通信學(xué)報(bào)(2016年11期)2016-08-16 03:20:04
北京信息科技大學(xué)學(xué)報(bào)(自然科學(xué)版)(2016年6期)2016-02-27 06:31:53
管理現(xiàn)代化(2016年3期)2016-02-06 02:04:41
管理現(xiàn)代化(2016年3期)2016-02-06 02:04:13
智能系統(tǒng)學(xué)報(bào)(2015年4期)2015-12-27 09:37:52
