【文章內容簡介】 的調度算法。 一般點覆蓋算法大多假設覆蓋與連通是一致的，并沒有考慮被監(jiān)測的目標分布情況對網絡連通性的影響。為此本文討論了點覆蓋與連通性的關系，提出了一種基于 Steiner 樹集中式連通算法 CCAST算法。該算法首先將所有連通簇看成一個虛擬節(jié)點，然后構建加權通信圖并調用已有構造 Steiner 樹的算法挑選出 Steiner 點，使得所有的覆蓋節(jié)點保持連通。接著，本文又進一步提出了一種分布式連通算法 DCAVIS。該算法首先構造虛擬獨立集，然后尋找使覆蓋集成為連通集的中繼節(jié)點。 DCAVIS 算法為解決點覆蓋連通問題可提供了一種分布式近似求解算法，同時可以有效延長無線傳感器網絡的生存時間。 綜上所述，本文以無線傳感器網絡點覆蓋問題為主要目標，從分布式、集中式以及集中式算法的局部化三方面研究了點覆蓋算法，其中， 集中式算法的局部化還可做為以后的工作進一步研究。 無線傳感器網絡是由具備感知、數據處理、存儲和數據傳輸的傳感器節(jié)點自組織而形成的無線網絡，在軍用和民用領域有著廣泛的應用前景。覆蓋問題是無線傳感器網絡的重要問題之一，它是反映無線傳感器網絡服務質量的一項重要性能指標。由于受到能量的約束，覆蓋問題的主要任務是找出較小的覆蓋集，并使這些集合能獨立完成所需要的任務，而其它節(jié)點則處于低功耗的休眠狀態(tài)。 目前，點覆蓋問題研究一般著重于設計集中式優(yōu)化算法，這些算法對無線傳感器網絡的實際應用存在一定的局限性。本文以布爾感 知模型為基礎，通過發(fā)掘點覆蓋問題中應用場景，研究分布式、集中式以及集中式算法的局部化處理算法。針對點覆蓋問題中目標點分布對覆蓋集連通性的制約，本文也系統地研究了覆蓋連通問題，并提出了相應的連通算法。 本文首先討論了無線傳感器網絡節(jié)點冗余覆蓋調度機制，進而提出了一種分布式算法 SRCA。該算法通過檢測網絡中的覆蓋冗余節(jié)點，讓部分冗余節(jié)點休眠，從而降低網絡的冗余覆蓋程度。 SRCA 算法在保證網絡初始覆蓋的同時，能夠有效地降低系統能量消耗，延長網絡的生存時間。 面向無線傳感器網絡的一種應用場景，本文提出了一種 基于遺傳算法的傳感器節(jié)點調度的一種集中式近似算法 NSAGA 算法。該算法期望利用遺傳算法的種群特性，求解無線傳感器網絡覆蓋子集。該算法每次迭代可以同時產生多個滿足條件的覆蓋子集，還可以根據覆蓋要求改變約束條件，滿足不同的應用場景。 針對目前點覆蓋調度的算法一般都將覆蓋問題轉化為數學規(guī)劃模型，然后采用集中式算法近似算法求解。雖然這種求解方式比分布式算法的精度高，但不適合大規(guī)模無線傳感器網絡。為此，本文提出了一種將集中式算法進行局部化的思想，并提出了一種分布式 LCACA 算法。該算法首先選舉局部中心節(jié)點將整個 網絡劃分成多個規(guī)模較小的網絡。然后在每個劃分的網絡中再運行集中式算法，完成傳感器節(jié)點的調度。而且，該算法還可以根據不同子區(qū)域的目標的覆蓋要求，通過劃分網絡后，在每個劃分的網絡上運行不同的調度算法。 一般點覆蓋算法大多假設覆蓋與連通是一致的，并沒有考慮被監(jiān)測的目標分布情況對網絡連通性的影響。為此本文討論了點覆蓋與連通性的關系，提出了一種基于 Steiner 樹集中式連通算法 CCAST 算法。該算法首先將所有連通簇看成一個虛擬節(jié)點，然后構建加權通信圖并調用已有構造 Steiner 樹的算法挑選出 Steiner 點，使 得所有的覆蓋節(jié)點保持連通。接著，本文又進一步提出了一種分布式連通算法 DCAVIS。該算法首先構造虛擬獨立集，然后尋找使覆蓋集成為連通集的中繼節(jié)點。 DCAVIS 算法為解決點覆蓋連通問題可提供了一種分布式近似求解算法，同時可以有效延長無線傳感器網絡的生存時間。 綜上所述，本文以無線傳感器網絡點覆蓋問題為主要目標，從分布式、集中式以及集中式算法的局部化三方面研究了點覆蓋算法，其中，集中式算法的局部化還可做為以后的工作進一步研究。 無線傳感器網絡是由具備感知、數據處理、存儲和數據傳輸的傳感器節(jié)點自組織而形成的無 線網絡，在軍用和民用領域有著廣泛的應用前景。覆蓋問題是無線傳感器網絡的重要問題之一，它是反映無線傳感器網絡服務質量的一項重要性能指標。由于受到能量的約束，覆蓋問題的主要任務是找出較小的覆蓋集，并使這些集合能獨立完成所需要的任務，而其它節(jié)點則處于低功耗的休眠狀態(tài)。 目前，點覆蓋問題研究一般著重于設計集中式優(yōu)化算法，這些算法對無線傳感器網絡的實際應用存在一定的局限性。本文以布爾感知模型為基礎，通過發(fā)掘點覆蓋問題中應用場景，研究分布式、集中式以及集中式算法的局部化處理算法。針對點覆蓋問題中目標點分布對覆蓋集連 通性的制約，本文也系統地研究了覆蓋連通問題，并提出了相應的連通算法。 本文首先討論了無線傳感器網絡節(jié)點冗余覆蓋調度機制，進而提出了一種分布式算法 SRCA。該算法通過檢測網絡中的覆蓋冗余節(jié)點，讓部分冗余節(jié)點休眠，從而降低網絡的冗余覆蓋程度。 SRCA 算法在保證網絡初始覆蓋的同時，能夠有效地降低系統能量消耗，延長網絡的生存時間。 面向無線傳感器網絡的一種應用場景，本文提出了一種基于遺傳算法的傳感器節(jié)點調度的一種集中式近似算法 NSAGA 算法。該算法期望利用遺傳算法的種群特性，求解無線傳感器網絡覆蓋子集。該 算法每次迭代可以同時產生多個滿足條件的覆蓋子集，還可以根據覆蓋要求改變約束條件，滿足不同的應用場景。 針對目前點覆蓋調度的算法一般都將覆蓋問題轉化為數學規(guī)劃模型，然后采用集中式算法近似算法求解。雖然這種求解方式比分布式算法的精度高，但不適合大規(guī)模無線傳感器網絡。為此，本文提出了一種將集中式算法進行局部化的思想，并提出了一種分布式 LCACA 算法。該算法首先選舉局部中心節(jié)點將整個網絡劃分成多個規(guī)模較小的網絡。然后在每個劃分的網絡中再運行集中式算法，完成傳感器節(jié)點的調度。而且，該算法還可以根據不同子區(qū)域的目標 的覆蓋要求，通過劃分網絡后，在每個劃分的網絡上運行不同的調度算法。 一般點覆蓋算法大多假設覆蓋與連通是一致的，并沒有考慮被監(jiān)測的目標分布情況對網絡連通性的影響。為此本文討論了點覆蓋與連通性的關系，提出了一種基于 Steiner 樹集中式連通算法 CCAST 算法。該算法首先將所有連通簇看成一個虛擬節(jié)點，然后構建加權通信圖并調用已有構造 Steiner 樹的算法挑選出 Steiner 點，使得所有的覆蓋節(jié)點保持連通。接著，本文又進一步提出了一種分布式連通算法 DCAVIS。該算法首先構造虛擬獨立集，然后尋找使覆蓋集成為連 通集的中繼節(jié)點。 DCAVIS 算法為解決點覆蓋連通問題可提供了一種分布式近似求解算法，同時可以有效延長無線傳感器網絡的生存時間。 綜上所述，本文以無線傳感器網絡點覆蓋問題為主要目標，從分布式、集中式以及集中式算法的局部化三方面研究了點覆蓋算法，其中，集中式算法的局部化還可做為以后的工作進一步研究。 無線傳感器網絡是由具備感知、數據處理、存儲和數據傳輸的傳感器節(jié)點自組織而形成的無線網絡，在軍用和民用領域有著廣泛的應用前景。覆蓋問題是無線傳感器網絡的重要問題