本文選題：分布式MIS算法 + 傳感器網(wǎng)絡(luò)�。� 參考：《河南理工大學(xué)》2014年碩士論文

【摘要】：最大獨(dú)立集(Maximum Independent Set,MIS)問題是圖論中的經(jīng)典組合優(yōu)化問題,是NP完備的。分布式環(huán)境(如:傳感器網(wǎng)絡(luò))中的MIS算法的優(yōu)化對(duì)分布式系統(tǒng)的效率和穩(wěn)定性都有重要意義。最近,Afek等人從生物發(fā)育機(jī)制中獲得啟發(fā),提出了一種具有線性時(shí)間復(fù)雜性、空間復(fù)雜性的分布式MIS算法(Science2011)。但是,如何將Afek-MIS算法應(yīng)用到傳感器網(wǎng)絡(luò)中,特別是在物理干擾(Signal-to-Interference-Plus-Noise-Ratio,SINR)模型下對(duì)該算法的分析和改進(jìn)仍是一個(gè)亟待解決的問題。本文在傳感器網(wǎng)絡(luò)SINR模型下對(duì)Afek-MIS算法進(jìn)行分析和改進(jìn)。通過理論分析得出MIS算法節(jié)點(diǎn)度數(shù)受SINR模型下路徑損耗指數(shù)和信噪比值的約束,推導(dǎo)出相應(yīng)的公式。利用NetLogo和Matlab軟件進(jìn)行仿真和分析得出:當(dāng)路徑損耗指數(shù)、信噪比的值越小,節(jié)點(diǎn)度數(shù)越大,MIS算法運(yùn)行時(shí)間越短;當(dāng)路徑損耗指數(shù)、信噪比的值越大,節(jié)點(diǎn)度數(shù)越小,MIS算法運(yùn)行時(shí)間越長。即路徑損耗指數(shù)、信噪比與節(jié)點(diǎn)度數(shù)成反比,與MIS算法運(yùn)行時(shí)間成正比。同時(shí),節(jié)點(diǎn)度數(shù)較小時(shí),網(wǎng)絡(luò)分布較松散,節(jié)點(diǎn)連接不緊密,MIS算法運(yùn)行時(shí)間較長;隨著節(jié)點(diǎn)度數(shù)的增大,節(jié)點(diǎn)彼此之間連接更緊密,MIS算法運(yùn)行時(shí)間就越快。本文研究促進(jìn)了Afek-MIS算法在分布式傳感器網(wǎng)絡(luò)中的應(yīng)用。
[Abstract]:The Maximum Independent Set (MIS) problem is a classic combinatorial optimization problem in graph theory. It is NP complete. The optimization of MIS algorithm in distributed environment (such as sensor network) is of great significance to the efficiency and stability of distributed systems. Recently, Afek and others have obtained inspiration from the mechanism of biological development. The distributed MIS algorithm (Science2011) with linear time complexity and spatial complexity. However, how to apply Afek-MIS algorithm to the sensor network, especially in the Signal-to-Interference-Plus-Noise-Ratio (SINR) model, is still an urgent problem to be solved. In this paper, the sensor network SI The Afek-MIS algorithm is analyzed and improved under the NR model. Through the theoretical analysis, it is concluded that the node degree of the MIS algorithm is constrained by the path loss index and the signal to noise ratio under the SINR model. The corresponding formulas are derived from the NetLogo and Matlab software. The smaller the value of the path loss index, the smaller the signal to noise ratio, the greater the node degree, M The shorter running time of IS algorithm; the greater the path loss index, the greater the value of the signal-to-noise ratio, the smaller the node degree, the longer the running time of the MIS algorithm. That is, the path loss index, the signal to noise ratio is inversely proportional to the node degree, and is proportional to the running time of the MIS algorithm. At the same time, the node degree is smaller, the network distribution is looser, the node connection is not close, MIS algorithm runs when the node is loose. As the node degree increases, the nodes connect more closely to each other, the faster the MIS algorithm runs. This study promotes the application of the Afek-MIS algorithm in the distributed sensor network.
【學(xué)位授予單位】：河南理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：O157.5;TP212.9;TN929.5

【相似文獻(xiàn)】

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

1 楊鈾,段滋明;求解圖的最大獨(dú)立集的一種算法[J];電腦開發(fā)與應(yīng)用;2002年06期

2 朱松年，，朱嬙;最大獨(dú)立集算法[J];西南交通大學(xué)學(xué)報(bào);1995年05期

3 劉靜;殷志祥;;基于DNA自組裝模型解決圖的最大獨(dú)立集問題[J];安徽理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年04期

4 王知人,劉玉峰;圖的最大獨(dú)立集問題的模擬退火算法[J];東北重型機(jī)械學(xué)院學(xué)報(bào);1997年03期

5 丁根宏;李勤豐;李尤豐;;一種求解最大獨(dú)立集的自學(xué)習(xí)進(jìn)化算法[J];河海大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年06期

6 郭廷花;;關(guān)于圓弧圖最大獨(dú)立集的一種最優(yōu)算法[J];山西財(cái)經(jīng)大學(xué)學(xué)報(bào)(高等教育版);2009年S1期

7 吳江;圖的最大獨(dú)立集數(shù)上界[J];西北大學(xué)學(xué)報(bào)(自然科學(xué)版);1987年04期

8 邵春芳;劉忠;;一個(gè)求解簡(jiǎn)單超圖中最大獨(dú)立集的算法[J];中國西部科技;2006年35期

9 朱松年,朱嬙;網(wǎng)絡(luò)分解及最大獨(dú)立集算法研究(Ⅰ)[J];交通運(yùn)輸工程與信息學(xué)報(bào);2003年02期

10 薛圣偉;王淑棟;趙秉清;馬芳芳;;基于改進(jìn)的粘貼模型求解圖最大獨(dú)立集的DNA算法[J];山東科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年04期

相關(guān)碩士學(xué)位論文 前3條

1 皇運(yùn)才;分布式最大獨(dú)立集算法及其在無線傳感網(wǎng)絡(luò)中的應(yīng)用研究[D];河南理工大學(xué);2014年

2 戎文晉;最大獨(dú)立集問題及其成長算法的研究[D];太原理工大學(xué);2004年

3 李勤豐;最大獨(dú)立集問題的一類進(jìn)化算法研究[D];河海大學(xué);2007年

本文編號(hào)：1932980