【摘要】：本學(xué)位論文的研究課題來源于國(guó)家自然科學(xué)基金“基于同調(diào)理論的無線傳感器網(wǎng)絡(luò)k重覆蓋若干算法研究”(批準(zhǔn)號(hào):61601122)。主要針對(duì)節(jié)點(diǎn)位置和節(jié)點(diǎn)間距離信息未知的場(chǎng)景,對(duì)無線傳感器網(wǎng)絡(luò)(WSN,Wireless Sensor Network)的覆蓋空洞檢測(cè)算法進(jìn)行了深入研究。論文利用同調(diào)理論中的Rips復(fù)形對(duì)WSN的拓?fù)溥M(jìn)行建模,在保證覆蓋拓?fù)涮匦圆蛔兊那疤嵯?休眠冗余節(jié)點(diǎn),簡(jiǎn)化Rips復(fù)形,再根據(jù)簡(jiǎn)化后的Rips復(fù)形提出空洞檢測(cè)算法。論文的主要貢獻(xiàn)如下:(1)根據(jù)WSN的特點(diǎn),提出了一種基于相對(duì)方位角(RDA,Relative Direction Angle)信息的覆蓋空洞檢測(cè)算法。首先,在節(jié)點(diǎn)位置和距離信息未知的情況下,根據(jù)同調(diào)理論,利用節(jié)點(diǎn)之間的連通信息構(gòu)建網(wǎng)絡(luò)拓?fù)涞腞ips復(fù)形。其次,計(jì)算節(jié)點(diǎn)的權(quán)重大小,利用節(jié)點(diǎn)之間的RDA信息,休眠部分節(jié)點(diǎn),并且斷開冗余節(jié)點(diǎn)之間的連接,從而達(dá)到簡(jiǎn)化Rips復(fù)形的目的。進(jìn)而,提出了基于RDA信息的覆蓋空洞檢測(cè)算法,根據(jù)RDA信息找出所有的空洞邊界(BE,Boundary Edge),以檢測(cè)出所有的覆蓋空洞。仿真分析表明,所提算法能夠在保持原有WSN拓?fù)涮匦缘耐瑫r(shí),減少網(wǎng)絡(luò)中部署節(jié)點(diǎn)的個(gè)數(shù),整個(gè)算法的復(fù)雜度為O(nm2),覆蓋空洞檢測(cè)的正確率能達(dá)到99%,,n為節(jié)點(diǎn)的個(gè)數(shù),m為節(jié)點(diǎn)的平均鄰節(jié)點(diǎn)個(gè)數(shù)。(2)在RDA信息未知的情況下,通過在Rips復(fù)形中引入聯(lián)合Laplacian算子(JLO,Joint Laplacian Operator),提出了一種基于 Laplacian 矩陣(LM,Laplacian Matrix)的覆蓋空洞檢測(cè)算法。算法首先通過計(jì)算節(jié)點(diǎn)的權(quán)重大小,選擇合適的候選休眠節(jié)點(diǎn)。其次,構(gòu)建休眠節(jié)點(diǎn)的鄰節(jié)點(diǎn)形成的子單純復(fù)形,計(jì)算其LM零空間矩陣的維數(shù),根據(jù)維數(shù)對(duì)節(jié)點(diǎn)進(jìn)行休眠控制。由此,判斷所有的候選節(jié)點(diǎn),直到不再存在可以被休眠的節(jié)點(diǎn),以達(dá)到簡(jiǎn)化拓?fù)涞哪康�。然�?基于簡(jiǎn)化的Rips復(fù)形,先根據(jù)拓?fù)涮匦哉页鲂纬筛采w空洞的邊界,再將空洞邊界順次連接即可檢測(cè)出WSN中存在的覆蓋空洞。仿真結(jié)果表明,所提算法能有效減少網(wǎng)絡(luò)資源,復(fù)雜度為O(n2m4),覆蓋空洞檢測(cè)的正確率為99%,n為節(jié)點(diǎn)的個(gè)數(shù),m為平均鄰節(jié)點(diǎn)的個(gè)數(shù)。
【圖文】：

逡逑類似的對(duì)于定向２－單形ｓ２邋＝邋［ｖ0，１＾，２＾］，如圖２．６邋（ｂ）所示，它可以表示一逡逑個(gè)由構(gòu)成的三角形區(qū)域，假設(shè)預(yù)定知方向?yàn)�，這個(gè)方向和Ｖｏｈｈ、逡逑１＾１；。�。蕖⒌姆较蛳喾�，但是方向是一樣的，且它們之逡逑間存在如下的關(guān)系逡逑［ｖ０＞ｖｌ＞＾２ｌ邋￣邋［ｖｌｉｖ２＞Ｖ0ｌ邋￣邋［ｖ２＞ｖ０＞ｖｌｌ邋＝邋￣［ｖ０＞ｖ２＞ｖｌｌ邋＝邐（２邋８）逡逑－［Ｖｉ，Ｖ0，Ｖ２］邋＝邋－＾Ｖ＾Ｖｑ］逡逑Ｖ］逡逑Ｖ＼逡逑＾逡逑（ａ）定向１－單形邐（ｂ）定向２－單形逡逑圖２．６定向１－，，邋２－單形逡逑定向１－單形［ｖ，ｗ］的邊緣定義為逡逑ｄ［ｖ，ｗ］邋＝邋ｗ邋—邋ｖ邐（２．９）逡逑定向２－單形［ｗ，邋Ｖ，邋ｗ］的邊緣定義為逡逑ｄ［ｕ

逡逑如圖２．７邋（ｂ）的邊界映射，如２－單形［２，３，４］可以映射為三個(gè)１－單形［２，３］，邋［３，４］，逡逑［４，２］之和。經(jīng)過圖２．７邋（ｃ）的映射之后，所有１－單形最終都將映射為０，整個(gè)過逡逑程很好地解釋了（２．１３）體現(xiàn)的復(fù)形鏈過程。逡逑Ｖ２逡逑（ａ．）邋ｋ＝邋２逡逑ｖ｛邐Ｖｉ逡逑么邋一邋Ａ．二。逡逑（ｂ）邐ｈ＝邋１逡逑ｒ0？邐＾＾．邋0逡逑（ｃ）邐Ａ＝邋０逡逑圖２．７不同維度的邊界映射操作逡逑定義２．３邋（閉鏈群）單純復(fù)形Ｘ的Ａ維閉鏈群為Ｚｆｃ（；0二ｋｅｒ４。逡逑定義２．４邋（邊緣鏈群）單純復(fù)形Ｚ的Ａ：維邊緣鏈群為Ｓｆｃ（；0邋＝邋ｉｍ３ｋ＋１。逡逑由定義２．３和２．４可以推出：Ａ：維閉鏈群Ｚｆｃ（；0的元素均是不包含邊界的ｈ鏈，逡逑左維邊緣鏈群則是所有屬于認(rèn)＋邋１）－鏈群邊界的ｋ鏈集合。而且從式逡逑３ｆｃ°３ｆｃ＋１邋＝邋０可以看出，一個(gè)邊界不屬于也不包含任何邊界，因此Ｓｆｃ（；0邋Ｇ邋＆（；0。逡逑定義２．５邋（同調(diào)群）單純復(fù)形Ｚ的維同調(diào)群定義為如下商空間逡逑Ｈｋ00＝Ｚｋ00／Ｂｋ00邐（２．１５）逡逑定義２．６邋（貝蒂數(shù)）同調(diào)群／４（；0的維度即為單純復(fù)形Ｚ的＆階貝蒂數(shù)，即逡逑—邋ｄｉｍＨｆｃ（＾）邋－邋ｄｉｍＺｋ（Ｘ）邋—邋ｄｉｍ５ｆｅ（Ｘ）邐（２．１６）逡逑定義２．５表明，＆維同調(diào)群／４（；0是一組ｙＨ隹閉鏈群的等價(jià)類集合，而且兩個(gè)逡逑免維邊緣鏈群的差值是一個(gè)０＋邋１）鏈群的邊界。計(jì)算貝蒂數(shù)時(shí)需要通過邊界映射逡逑的矩陣求得，一般地構(gòu)建了單純復(fù)形便能得到相應(yīng)的矩陣，不需要利用增量逡逑計(jì)算的算法。在單純復(fù)形中
【學(xué)位授予單位】：東南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：TN929.5;TP212.9

【參考文獻(xiàn)】

相關(guān)期刊論文 前6條

1 溫濤;張冬青;郭權(quán);宋曉瑩;;無線傳感器網(wǎng)絡(luò)冗余節(jié)點(diǎn)休眠調(diào)度算法[J];通信學(xué)報(bào);2014年10期

2 張希偉;戴海鵬;徐力杰;陳貴海;;無線傳感器網(wǎng)絡(luò)中移動(dòng)協(xié)助的數(shù)據(jù)收集策略[J];軟件學(xué)報(bào);2013年02期

3 曾志文;陳志剛;劉安豐;;無線傳感器網(wǎng)絡(luò)中基于可調(diào)發(fā)射功率的能量空洞避免[J];計(jì)算機(jī)學(xué)報(bào);2010年01期

4 任彥;張思東;張宏科;;無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法[J];軟件學(xué)報(bào);2006年03期

5 馬祖長(zhǎng),孫怡寧,梅濤;無線傳感器網(wǎng)絡(luò)綜述[J];通信學(xué)報(bào);2004年04期

6 任豐原,黃海寧,林闖;無線傳感器網(wǎng)絡(luò)[J];軟件學(xué)報(bào);2003年07期

本文編號(hào)：2589114