物聯(lián)網(wǎng)論文6593549848

1、考試科目: 物聯(lián)網(wǎng)系統(tǒng)設(shè)計(jì)與集成技術(shù) 姓 名:學(xué) 號(hào): 專 業(yè): 基于無(wú)線網(wǎng)絡(luò)的低能耗骨干網(wǎng)的研究摘要在無(wú)線傳感器和自主網(wǎng)絡(luò)中對(duì)于骨干網(wǎng)的研究有很多方面的應(yīng)用（如：路由，路由維護(hù)，廣播）。以前的算法大多基于構(gòu)造一個(gè)網(wǎng)絡(luò)使其主干網(wǎng)的規(guī)模最小，但是，在許多應(yīng)用中，我們需要建造一個(gè)骨干網(wǎng)在減少骨干網(wǎng)大小的的同時(shí)使得建造這個(gè)骨干網(wǎng)花費(fèi)的代價(jià)最小。在這篇文章之中，我們先介紹幾種以前的方法，他們都是基于使得建造骨干網(wǎng)的規(guī)模較少的，但是，通過(guò)他們的方法，會(huì)使網(wǎng)絡(luò)構(gòu)造產(chǎn)生較大的代價(jià)。于是，我們介紹一種有效地分布算法，構(gòu)造出一個(gè)有較低代價(jià)的骨干網(wǎng)。關(guān)鍵詞：支配集，傳感器網(wǎng)絡(luò)，分布算法，無(wú)線自組網(wǎng) 1 引言近些年

2、來(lái)，無(wú)線網(wǎng)絡(luò)和無(wú)線傳感器有著廣泛的應(yīng)用，并且引起人們極大地關(guān)注。許多路由協(xié)議在最近又有新的發(fā)展。而最簡(jiǎn)單的路由算法就是洪泛，但是，此方法不僅浪費(fèi)無(wú)線網(wǎng)絡(luò)的資源而且減少了網(wǎng)絡(luò)的吞吐量。避免洪泛的辦法就是讓每個(gè)節(jié)點(diǎn)只與自己的一個(gè)鄰節(jié)點(diǎn)子集通信，或者用如因特網(wǎng)的網(wǎng)絡(luò)結(jié)構(gòu)，比如基于支配集的算法。對(duì)于在網(wǎng)絡(luò)中構(gòu)造支配集的有效算法在以前已經(jīng)有研究。大多數(shù)算法都是在減少節(jié)點(diǎn)的個(gè)數(shù)，也就是減少主干網(wǎng)的節(jié)點(diǎn)個(gè)數(shù)，但是，在許多無(wú)線網(wǎng)絡(luò)的應(yīng)用之中，減少骨干網(wǎng)的大小是遠(yuǎn)遠(yuǎn)不夠的。例如，不同的無(wú)線節(jié)點(diǎn)在不同的節(jié)點(diǎn)簇中有著不同的代價(jià)。因此，我們假設(shè)每個(gè)節(jié)點(diǎn)都有一類代價(jià)，而且，作為節(jié)點(diǎn)簇代價(jià)反應(yīng)了一個(gè)節(jié)點(diǎn)的優(yōu)先度與適應(yīng)度。

3、低代價(jià)的意味著高優(yōu)先度。事實(shí)上，假如我們需要主干網(wǎng)能耗最少，那么我們考慮的代價(jià)就是能耗消耗。假如我們需要主干網(wǎng)容錯(cuò)率高，那么我們的代價(jià)就是網(wǎng)絡(luò)的魯棒性，因此，在不同的代價(jià)的定義下，低代價(jià)算法也有不同的應(yīng)用。最近研究中，構(gòu)造的簇算法都是通過(guò)不同代價(jià)作為優(yōu)先度評(píng)判標(biāo)準(zhǔn)來(lái)決定節(jié)點(diǎn)是否能成為節(jié)點(diǎn)簇，但是，他們的最終目的是減少簇的大小，而不是整個(gè)簇的代價(jià)。這里主要是有效地構(gòu)造一個(gè)稀疏骨干網(wǎng)絡(luò)，從而，使得骨干網(wǎng)絡(luò)的代價(jià)最少，并且，在本來(lái)的無(wú)線網(wǎng)絡(luò)之中能有一條有效的路徑連接無(wú)線網(wǎng)絡(luò)的每一個(gè)節(jié)點(diǎn)對(duì)。2 預(yù)備知識(shí)在這部分之中，我們給出一些在下面的敘述中會(huì)用到的定義和假設(shè)，我們假設(shè)所有在V中的傳感器節(jié)點(diǎn)都是在二維

4、空間之中。而且，每一個(gè)節(jié)點(diǎn)都能接收到周圍節(jié)點(diǎn)的信號(hào)。圖是節(jié)點(diǎn)個(gè)數(shù)為V的圖，在節(jié)點(diǎn)與之間有邊，當(dāng)且僅當(dāng)，與能相互的通信。也就是說(shuō)他們都在相互的通信范圍之內(nèi)。今后，我們都稱G為連接圖，讓代表點(diǎn)u的度數(shù)，代表其的最大度，每個(gè)節(jié)點(diǎn)都有它在主干網(wǎng)中的代價(jià)，這里是由電池的電量，節(jié)點(diǎn)的可移動(dòng)性，節(jié)點(diǎn)在網(wǎng)絡(luò)中的度數(shù)所決定的。大體上，越小的說(shuō)明此節(jié)點(diǎn)越適合這個(gè)骨干網(wǎng)絡(luò)。每一個(gè)傳感器節(jié)點(diǎn)可以想象為一個(gè)以它自己為中心的單位圓圖，定義為UDG，當(dāng)且僅當(dāng)假如兩點(diǎn)之間的距離最大為1時(shí)，我們叫此網(wǎng)絡(luò)為同構(gòu)網(wǎng)絡(luò)。我們稱在圖G中能在K跳之內(nèi)能達(dá)到的u的節(jié)點(diǎn)為u的K跳節(jié)點(diǎn)或?yàn)閡的K跳鄰居節(jié)點(diǎn)。并把節(jié)點(diǎn)定義為（包括u本身），而把K

5、跳節(jié)點(diǎn)所構(gòu)成的圖為以點(diǎn)所構(gòu)成的導(dǎo)出圖，記作：。S是V的子集，假如當(dāng)V的每個(gè)節(jié)點(diǎn)在S中，或者在V中的每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)都在S中，那么我們就稱S是V支配集。在S的每個(gè)節(jié)點(diǎn)被稱為支配點(diǎn)，不在S中的點(diǎn)被稱為被支配點(diǎn)。顯然，最大獨(dú)立集是支配集，假如C是一個(gè)支配集，而且C導(dǎo)出一個(gè)連接子圖，那么我們就稱C是V的連接支配集（CDS），顯然，CDS中的每個(gè)節(jié)點(diǎn)都可以互相通信，而不需依靠的節(jié)點(diǎn)。有最少點(diǎn)得支配集稱為最小支配集（MDS），而在MDS中有最少點(diǎn)的集合為最小連接支配集（MCDS），在自組網(wǎng)絡(luò)中，假設(shè)每個(gè)點(diǎn)都有花費(fèi)代價(jià)為，那么，一個(gè)CDS被稱做有權(quán)的連接支配集（WCDS），假如C為WCDS中總代價(jià)最小的子

6、集，那么我們就稱C為最小有權(quán)連接支配集（MWCDS），在這篇文章中我們就構(gòu)造了一個(gè)低代價(jià)的主干網(wǎng)絡(luò)，而問(wèn)題的實(shí)質(zhì)是構(gòu)造一個(gè)最小有權(quán)連接支配集。3 低代價(jià)主干網(wǎng)絡(luò)結(jié)構(gòu)算法在本部分，我們構(gòu)造了一個(gè)分部算法，使其在無(wú)線自組網(wǎng)G中建立了一個(gè)低代價(jià)的主干網(wǎng)絡(luò)（有權(quán)連接支配集），我們假設(shè)每一個(gè)節(jié)點(diǎn)都知道他的ID和所有下一跳鄰居節(jié)點(diǎn)的代價(jià)。而這過(guò)程需要每個(gè)節(jié)點(diǎn)對(duì)他的鄰居節(jié)點(diǎn)發(fā)送他的ID和節(jié)點(diǎn)代價(jià)來(lái)實(shí)現(xiàn)。我們的辦法包括下面的兩步：第一步找到一個(gè)無(wú)線節(jié)點(diǎn)集作為圖的支配節(jié)點(diǎn)集，第二步，找到一個(gè)節(jié)點(diǎn)集，我們叫連接點(diǎn)，然后將連接點(diǎn)連接到支配點(diǎn)集中，得到最后的節(jié)點(diǎn)集和，并把它作為主干網(wǎng)。注意，以上兩個(gè)步驟交錯(cuò)進(jìn)行，我們

7、為了使問(wèn)題更加簡(jiǎn)單，我們把問(wèn)題進(jìn)行分部討論。3.1找支配點(diǎn)我們要得到一個(gè)構(gòu)造支配點(diǎn)辦法，并且使得其總的代價(jià)相對(duì)較小。方法是：第一，建造一個(gè)最大獨(dú)立集（MIS）以節(jié)點(diǎn)的權(quán)重作為選擇標(biāo)準(zhǔn)。然后，對(duì)于每一個(gè)在MIS集節(jié)點(diǎn)v，我們用貪婪集覆蓋的方法，在v的鄰居節(jié)點(diǎn)中找到一些節(jié)點(diǎn)（）使得其覆蓋所有的v的一跳鄰居節(jié)點(diǎn)。如果代價(jià)小于v的代價(jià)，那么我們就用代替v，從而減少了MIS的代價(jià)。我們的方法在算法1中，例子如圖1，MIS有兩個(gè)節(jié)點(diǎn)w和v，他們的代價(jià)都很大，節(jié)點(diǎn)u是，顯然，和，覆蓋點(diǎn)集選擇v覆蓋在節(jié)點(diǎn)。注意到，所以v是u的支配點(diǎn)，另一個(gè)點(diǎn)w，保持他自己為支配點(diǎn)，因?yàn)樗采w點(diǎn)集的代價(jià)比自己的大。所以最后的支

8、配點(diǎn)集為.算法1 構(gòu)造低代價(jià)支配集（1） 假設(shè)我們把所有節(jié)點(diǎn)都染色為白色（WHITE）。（2） 假如它的鄰居節(jié)點(diǎn)中有最小的代價(jià)，那么節(jié)點(diǎn)u發(fā)送信息給所有的下一跳鄰居節(jié)點(diǎn)，而節(jié)點(diǎn)u標(biāo)記為。（3） 當(dāng)節(jié)點(diǎn)v收到由一跳鄰居節(jié)點(diǎn)所發(fā)來(lái)的信息，節(jié)點(diǎn)v就將自己標(biāo)為，節(jié)點(diǎn)v就發(fā)送性信息給v的下一跳鄰居節(jié)點(diǎn)。（4） 當(dāng)節(jié)點(diǎn)w收到的信息的時(shí)候，節(jié)點(diǎn)w會(huì)把v從染為白色（WHITE）的節(jié)點(diǎn)表之中刪掉。（5） 節(jié)點(diǎn)u記上搜集所有與他相關(guān)兩跳節(jié)點(diǎn)的代價(jià)和ID。（6） 用貪婪算法找出最小權(quán)重覆蓋集，節(jié)點(diǎn)u找出所有兩跳節(jié)點(diǎn)鄰居節(jié)點(diǎn)的子集，已包含所有的節(jié)點(diǎn)u的一跳節(jié)點(diǎn)，假如被選節(jié)點(diǎn)的子集代價(jià)定義為，小于u節(jié)點(diǎn)的代價(jià)，那么節(jié)點(diǎn)

9、u發(fā)送信息給下一個(gè)節(jié)點(diǎn)w，不然的話節(jié)點(diǎn)u就把自己標(biāo)記為。（7） 節(jié)點(diǎn)w收到信息后，就標(biāo)記自己為。3.2 找出連接點(diǎn)在第二步中在被支配集中找到一些連接點(diǎn)，并把被支配集連接到支配點(diǎn)上。連接點(diǎn)和支配點(diǎn)組成了CDS（主干網(wǎng)）。給出一個(gè)支配集S，讓代表協(xié)調(diào)器和節(jié)點(diǎn)對(duì)，假如u和v之間最多相隔三跳。然后我們就自然地通過(guò)把其他節(jié)點(diǎn)連接在網(wǎng)絡(luò)中的u和v上，從而形成了一個(gè)CDS網(wǎng)絡(luò)。而我們的方法是第一：我們定義兩個(gè)鄰居協(xié)調(diào)器u和v，滿足的條件是他們兩個(gè)節(jié)點(diǎn)最多三跳。讓定義在圖G中的u和v節(jié)點(diǎn)上為最小代價(jià)路，代表中各個(gè)節(jié)點(diǎn)的總代價(jià)（包括u和v代價(jià)）：，對(duì)于每一對(duì)鄰居協(xié)調(diào)器u和v，我們的方法是：（1）協(xié)調(diào)器表，k表示

10、距離節(jié)點(diǎn)v有k步長(zhǎng)（2）代表從v到u用k步的最小代價(jià)。（3）：代表節(jié)點(diǎn)是距離節(jié)點(diǎn)v一跳的協(xié)調(diào)器。（4）：節(jié)點(diǎn)是距離節(jié)點(diǎn)v兩跳的協(xié)調(diào)器，是它的最小代價(jià)。那么我們把方法細(xì)化得到了算法2，通過(guò)比較所有的協(xié)調(diào)器的節(jié)點(diǎn)，我們得到WCDS（主干網(wǎng)）。算法2, 低代價(jià)連接節(jié)點(diǎn)選擇1 每一個(gè)協(xié)調(diào)器節(jié)點(diǎn)v發(fā)送信息給在表的一跳鄰居節(jié)點(diǎn)，用信息，當(dāng)接受節(jié)點(diǎn)搜到來(lái)自v的信息之后，他讓協(xié)調(diào)器或者假如，更新路，假如他有最小代價(jià)路2 當(dāng)協(xié)調(diào)器節(jié)點(diǎn)w搜到從所有一跳節(jié)點(diǎn)信息之后，節(jié)點(diǎn)w發(fā)出信息，這里是最小代價(jià)路。3. 當(dāng)協(xié)調(diào)器z從鄰居節(jié)點(diǎn)w搜到信息之后，節(jié)點(diǎn)讓假如，更新路為假如有最小代價(jià)。4 每個(gè)協(xié)調(diào)器u都建立與其他鄰居協(xié)調(diào)器

11、v的虛擬邊，而邊的長(zhǎng)度就是路的最小代價(jià)。注意這里的代價(jià)并沒(méi)有包括節(jié)點(diǎn)u和v的代價(jià)，所有的虛邊形成的圖就是在圖中的協(xié)調(diào)器序列的代價(jià)和。5 用分布算法在中構(gòu)建MST，VMST定義為MST（）6 對(duì)于每一個(gè)虛邊，選擇每一個(gè)和協(xié)調(diào)器e相關(guān)聯(lián)的被支配點(diǎn)作為連接點(diǎn)。4 總結(jié)在本篇文章之中，介紹了一個(gè)新的算法，并得到了一個(gè)在無(wú)線自主傳感器骨干網(wǎng)絡(luò)下的網(wǎng)絡(luò)的稀疏結(jié)構(gòu)。而這個(gè)分布算法的核心是在在于找到一個(gè)有權(quán)連接支配集，并且保證在此支配集中，節(jié)點(diǎn)的最大度數(shù)，最小度數(shù)是個(gè)常數(shù)，在算法之中，假設(shè)節(jié)點(diǎn)一段時(shí)間段內(nèi)是靜態(tài)的。而在實(shí)際生活中，網(wǎng)絡(luò)是高度動(dòng)態(tài)的，因此在主干網(wǎng)的權(quán)重得到之后，主干網(wǎng)的動(dòng)態(tài)保持也是很重要的，而下

12、面兩個(gè)問(wèn)題也許會(huì)使骨干網(wǎng)失去意義(1)網(wǎng)絡(luò)的拓補(bǔ)結(jié)構(gòu)不斷的變化，其中包括節(jié)點(diǎn)移動(dòng)，節(jié)點(diǎn)加入，節(jié)點(diǎn)離開(kāi)，節(jié)點(diǎn)丟失。（2）權(quán)重變化：當(dāng)權(quán)重被分配給節(jié)點(diǎn)通過(guò)某種法則的時(shí)候，有可能在實(shí)際之中權(quán)重值變化很頻繁，諸如電池或者鏈接質(zhì)量等等原因，因此動(dòng)態(tài)更新的考慮是很用必要的。而解決那些問(wèn)題，我們需要在以后的研究中去實(shí)現(xiàn)。參考文獻(xiàn)1 J.Wu and H.Li,”A Dominating-Set-Based Routing Scheme in A Hoc Wireless Networks,”Telecomm.SystemsJ., vol.3,pp.63-84,2001.2 Yu Wang and Weizhao W