在均質(zhì)無(wú)線自組織網(wǎng)絡(luò)中,虛擬骨干(Virtual Backbone,VB)的大小是衡量無(wú)線自組織網(wǎng)絡(luò)質(zhì)量的一個(gè)重要因素,虛擬骨干越小,網(wǎng)絡(luò)路由開(kāi)銷越少。最小虛擬骨干的求取問(wèn)題能夠抽象為最小連通控制集問(wèn)題。針對(duì)二維無(wú)線自組織網(wǎng)絡(luò)上的單位圓盤圖(Unit Disk Graph,UDG)中最小連通控制集問(wèn)題,目前已有很多研究成果,但是在現(xiàn)實(shí)中的某些情況下,單位圓盤圖并不能準(zhǔn)確地抽象網(wǎng)絡(luò)。因此,文中提出了在單位球圖(Unit Ball Graph,UBG)中構(gòu)建高質(zhì)量的連通控制集(Connected Dominating Set,CDS)的算法ST-CDS,給出了單位球圖中獨(dú)立節(jié)點(diǎn)個(gè)數(shù)的一個(gè)優(yōu)化上界,并進(jìn)一步利用該優(yōu)化上界得到連通控制集的性能比。所提算法主要運(yùn)用構(gòu)造最小斯坦納節(jié)點(diǎn)的斯坦納樹(shù)(Steiner Tree with Minimum Number of Steiner Nodes)方法來(lái)優(yōu)化節(jié)點(diǎn)之間的連通部分。理論分析表明,ST-CDS算法的性能比為11.808 0+ln11,是目前已知該方向研究中最好的結(jié)果。仿真結(jié)果也驗(yàn)證了ST-CDS算法的可行性。

【文章頁(yè)數(shù)】：7 頁(yè)

【部分圖文】：

圖1在單位球圖中的菱形十二面體

在文獻(xiàn)[16]的基礎(chǔ)上,Butenko等[17]證明了在任意連通的單位球圖上有α(G)≤11opt+1。隨后,Kim等[13]采用數(shù)學(xué)歸納法優(yōu)化了文獻(xiàn)[18]中的結(jié)論,得到一個(gè)新的關(guān)于MIS的算法近似比,為10.917,這是目前已知最優(yōu)的結(jié)論。本節(jié)提出了用菱形十二面體進(jìn)行單....

圖2半徑為1的單位球

引理3假設(shè)G=(V,E)是一個(gè)連通的單位球圖,Gˉ=(Vˉ,Eˉ)是另一個(gè)連通的球圖,其有著與G相同的中心,但是每個(gè)球的半徑為1.5。令I(lǐng)={e1,e2,…,eopt}是圖G的一個(gè)MCDS,A表示圖Gˉ中被以中心為ei的球所覆蓋的區(qū)域,則有A≤14.1....

圖3半徑為1.5的單位球圖

圖2半徑為1的單位球證明:假設(shè)Di-和Dj-表示兩個(gè)互相連通且中心為ei和ej、半徑為1.5的球,則有d(ei,ej)≤1。本文首先考慮d(ei,ej)=1的情況,令Vi表示Di-的體積,Vji表示Dj--Di-的體積,則

圖4菱形十二面體

α(S)≤14.137?2+6.806?8(opt-1)0.707?1≤9.626?4opt+10.366?8注意到,當(dāng)G的獨(dú)立集中的一個(gè)節(jié)點(diǎn)u位于某個(gè)單位球的表面時(shí),該節(jié)點(diǎn)對(duì)應(yīng)在Gˉ中就是以u(píng)為中心、半徑0.5的球。在這種情況下,以u(píng)為中心、半徑為0.5的球?yàn)閮?nèi)切球....

本文編號(hào)：3935851