计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2012年
8期
1632-1640
,共9页
陆克中%江钊%毛睿%刘刚%明仲
陸剋中%江釗%毛睿%劉剛%明仲
륙극중%강쇠%모예%류강%명중
无线传感器网络%网络生存时间%覆盖集%NP难问题%蜂窝结构
無線傳感器網絡%網絡生存時間%覆蓋集%NP難問題%蜂窩結構
무선전감기망락%망락생존시간%복개집%NP난문제%봉와결구
在无线传感器网络中,求解能够完全覆盖目标区域的最小覆盖集是个NP难问题.在传感器节点数目较多时,目前只能通过近似算法求解.蜂窝结构是覆盖二维平面的最佳拓扑结构,但不能直接用于求解无线传感器网络的覆盖问题.提出了一种基于蜂窝结构的覆盖问题求解算法,在该算法迭代求解过程的每一阶段,选出一个节点加入到初始为空的节点集合中,并使得该节点集合的拓扑结构接近于蜂窝结构,直至该节点集合成为覆盖集.该算法在最坏情况下的时间复杂度为O(n3),这里n为传感器节点总数.实验结果表明该算法可在很短的时间内执行完,在所得覆盖集的大小方面要优于现有的覆盖问题求解算法.
在無線傳感器網絡中,求解能夠完全覆蓋目標區域的最小覆蓋集是箇NP難問題.在傳感器節點數目較多時,目前隻能通過近似算法求解.蜂窩結構是覆蓋二維平麵的最佳拓撲結構,但不能直接用于求解無線傳感器網絡的覆蓋問題.提齣瞭一種基于蜂窩結構的覆蓋問題求解算法,在該算法迭代求解過程的每一階段,選齣一箇節點加入到初始為空的節點集閤中,併使得該節點集閤的拓撲結構接近于蜂窩結構,直至該節點集閤成為覆蓋集.該算法在最壞情況下的時間複雜度為O(n3),這裏n為傳感器節點總數.實驗結果錶明該算法可在很短的時間內執行完,在所得覆蓋集的大小方麵要優于現有的覆蓋問題求解算法.
재무선전감기망락중,구해능구완전복개목표구역적최소복개집시개NP난문제.재전감기절점수목교다시,목전지능통과근사산법구해.봉와결구시복개이유평면적최가탁복결구,단불능직접용우구해무선전감기망락적복개문제.제출료일충기우봉와결구적복개문제구해산법,재해산법질대구해과정적매일계단,선출일개절점가입도초시위공적절점집합중,병사득해절점집합적탁복결구접근우봉와결구,직지해절점집합성위복개집.해산법재최배정황하적시간복잡도위O(n3),저리n위전감기절점총수.실험결과표명해산법가재흔단적시간내집행완,재소득복개집적대소방면요우우현유적복개문제구해산법.
