基于圖論的區(qū)域覆蓋與點(diǎn)集覆蓋問(wèn)題研究
本文關(guān)鍵詞：基于圖論的區(qū)域覆蓋與點(diǎn)集覆蓋問(wèn)題研究
更多相關(guān)文章： 點(diǎn)集覆蓋問(wèn)題 區(qū)域覆蓋問(wèn)題 連通支配集 代數(shù)拓?fù)?/b> 圓packing
【摘要】：區(qū)域覆蓋與點(diǎn)集覆蓋問(wèn)題是兩個(gè)計(jì)算幾何研究的基本問(wèn)題,目前在實(shí)際中主要應(yīng)用場(chǎng)景為無(wú)線傳感器網(wǎng)絡(luò)、生物網(wǎng)絡(luò)等空間中分布的網(wǎng)絡(luò)。最早被研究的區(qū)域覆蓋問(wèn)題是藝術(shù)畫廊問(wèn)題,主要研究如何部署最少數(shù)量的攝像機(jī)來(lái)覆蓋整個(gè)畫廊。高效的覆蓋算法能夠節(jié)約能耗或者延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。而無(wú)線網(wǎng)絡(luò)在許多領(lǐng)域有著良好的應(yīng)用前景,比如,國(guó)家安全、軍事偵察、醫(yī)療衛(wèi)生和環(huán)境監(jiān)測(cè)等,因此研究高效的覆蓋算法有著重要的實(shí)際意義。從分類的角度來(lái)講,目前主要的各種網(wǎng)絡(luò)覆蓋問(wèn)題有點(diǎn)集覆蓋問(wèn)題、區(qū)域覆蓋問(wèn)題、目標(biāo)覆蓋問(wèn)題與路徑覆蓋問(wèn)題。從目標(biāo)來(lái)講,覆蓋問(wèn)題主要研究如何用最少的節(jié)點(diǎn)來(lái)保證整個(gè)區(qū)域的覆蓋,或者在保證整個(gè)區(qū)域被覆蓋的前提下最大化整個(gè)網(wǎng)絡(luò)生存時(shí)間。而研究覆蓋問(wèn)題采用的方法經(jīng)常為一些計(jì)算幾何和圖論的方法,比如、Voronoi圖和Delaunay三角剖分,和經(jīng)典代數(shù)拓?fù)浞椒?連通支配集,整數(shù)規(guī)劃。由于覆蓋問(wèn)題研究通常涉及非常經(jīng)典的數(shù)學(xué)問(wèn)題,比如,區(qū)域覆蓋算法中檢測(cè)是否存在空洞和自動(dòng)控制中的一致性問(wèn)題都可以采用高維拉普拉斯矩陣來(lái)進(jìn)行建模,因此,覆蓋問(wèn)題吸引了不同學(xué)科,不同領(lǐng)域的大量研究人員進(jìn)行理論和應(yīng)用研究。本文的主要貢獻(xiàn)如下：1.給出并證明了2維與3維空間中基于連通信息的區(qū)域覆蓋規(guī)則。2.提出了有著較優(yōu)近似度的DGB和BGB中連通支配集構(gòu)建算法。本文詳細(xì)闡述了區(qū)域覆蓋問(wèn)題、點(diǎn)集覆蓋問(wèn)題、目標(biāo)覆蓋問(wèn)題與路徑覆蓋問(wèn)題的國(guó)內(nèi)外研究現(xiàn)狀。本文分析了各種覆蓋問(wèn)題在算法設(shè)計(jì)目標(biāo)和模型上的聯(lián)系和區(qū)別,給出了一些解決覆蓋問(wèn)題常用的方法,比如線性規(guī)劃、連通支配集問(wèn)題。對(duì)于區(qū)域覆蓋問(wèn)題,本文首先給出了研究該問(wèn)題的代數(shù)拓?fù)浞椒枋�。具體研究方法包括單純復(fù)形、混合拉普拉斯矩陣、環(huán)空間理論。然后針對(duì)空洞的檢測(cè),本文給出了在2維空間和3維空間中的一些具體實(shí)例。本文首次給出了3維空間中僅基于連通信息的區(qū)域覆蓋規(guī)則,該規(guī)則對(duì)于設(shè)計(jì)在3維空間中的區(qū)域覆蓋算法有著重要的理論指導(dǎo)意義。本文證明了當(dāng)傳感比為γ≤(?)其中n為2一單形的數(shù)目,一個(gè)2維閉鏈的內(nèi)部區(qū)域被完全覆蓋。由于高維空間中對(duì)于閉鏈群的研究難以應(yīng)用求最短路等環(huán)空間中常用的圖論方法,高維空間中閉鏈群沒(méi)有環(huán)空間中的一些基本性質(zhì),因此,本文提出了一些和該問(wèn)題相關(guān)的開放性問(wèn)題。對(duì)于點(diǎn)集覆蓋問(wèn)題,本文提出了有著較優(yōu)近似度DGB和BGB中連通支配集構(gòu)建算法。首先,在2維空間中,本文采用經(jīng)典圓packing問(wèn)題方法詳細(xì)的分析了DGB模型下最大獨(dú)立集的上界,在DGB中,當(dāng)最大通信半徑與最小通信半徑的比值為(1,1.152],(1.152,1.307],(1.307,1.407],(1.407,1.462],(1.462,1.515],(1.515,1.618],(1.618,1.932]時(shí),最大獨(dú)立集的上界為6opt+1,7opt+1,8opt+1,9opt+1,10opt+1,11opt+1,16.7778opt+1.2222,其中opt表示連通支配集問(wèn)題的最優(yōu)解。基于此,改進(jìn)了基于最大獨(dú)立集的兩階段連通支配集構(gòu)建算法近似度。最后,本文將相應(yīng)的分析方法拓展到3維空間,通過(guò)經(jīng)典球packing問(wèn)題方法,給出了BGB模型下最大獨(dú)立集的上界。也就是說(shuō),本文給出的方法不僅適用于2維空間,也可推廣至于3維空間中分布的網(wǎng)絡(luò)。
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類號(hào)】：O157.5
【相似文獻(xiàn)】
中國(guó)期刊全文數(shù)據(jù)庫(kù) 前9條
1 陳峰,姚恩瑜;箱覆蓋問(wèn)題的半定松馳算法[J];運(yùn)籌學(xué)學(xué)報(bào);2002年02期
2 王翰;;最大覆蓋問(wèn)題研究[J];科技傳播;2011年22期
3 劉俊權(quán);;移動(dòng)通信信號(hào)隧道覆蓋問(wèn)題及解決方案[J];大眾科技;2012年05期
4 吳志華;;SAT算法解決碼覆蓋問(wèn)題之探討[J];內(nèi)江科技;2007年09期
5 徐高誠(chéng);m×n－1矩形的覆蓋問(wèn)題[J];數(shù)學(xué)通訊;1994年04期
6 張生;何尚錄;;預(yù)算型最大覆蓋問(wèn)題的近似算法[J];河北大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年01期
7 陸正福;洪孫焱;;密鑰覆蓋問(wèn)題的NP完全性證明[J];云南大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年03期
8 康慶德;格盤上的覆蓋問(wèn)題[J];自然雜志;1992年05期
9 ;[J];;年期
中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前2條
1 余立;丁海煜;劉佳;;GSM高速移動(dòng)環(huán)境下的覆蓋問(wèn)題研究[A];2007年中國(guó)通信學(xué)會(huì)“移動(dòng)增值業(yè)務(wù)與應(yīng)用”學(xué)術(shù)年會(huì)論文集[C];2007年
2 黃洋;;“小靈通”技術(shù)創(chuàng)新與網(wǎng)絡(luò)優(yōu)化若干問(wèn)題淺析[A];濟(jì)寧市技術(shù)創(chuàng)新與可持續(xù)發(fā)展論文選編[C];2005年
中國(guó)重要報(bào)紙全文數(shù)據(jù)庫(kù) 前2條
1 記者 于京玄;物料渣土覆蓋問(wèn)題突出[N];西安日?qǐng)?bào);2010年
2 黑龍江 郝高麟;用射頻光纖拉遠(yuǎn)解決高鐵弱覆蓋問(wèn)題(上)[N];電子報(bào);2011年
中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前3條
1 宋志明;星座對(duì)地覆蓋問(wèn)題的形式化體系構(gòu)建與求解算法研究[D];中國(guó)地質(zhì)大學(xué);2015年
2 白森;基于圖論的區(qū)域覆蓋與點(diǎn)集覆蓋問(wèn)題研究[D];吉林大學(xué);2016年
3 張宗祥;基于服務(wù)質(zhì)量的逐漸覆蓋問(wèn)題研究[D];華中科技大學(xué);2013年
中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條
1 唐浩龍;一維捆綁式箱子覆蓋問(wèn)題[D];云南大學(xué);2016年
2 劉闖;無(wú)線傳感器網(wǎng)絡(luò)中掃描覆蓋問(wèn)題研究[D];哈爾濱工業(yè)大學(xué);2016年
3 王利民;最小權(quán)和的連通頂點(diǎn)P_3覆蓋問(wèn)題[D];南京師范大學(xué);2015年
4 李文軍;覆蓋問(wèn)題的參數(shù)算法研究[D];中南大學(xué);2010年
5 李，
本文編號(hào)：1268405
本文鏈接：http://sikaile.net/shoufeilunwen/jckxbs/1268405.html
