计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2014年
2期
457-469
,共13页
无线传感器网络%连通恢复%四边形斯坦纳树%启发式算法%拓扑结构
無線傳感器網絡%連通恢複%四邊形斯坦納樹%啟髮式算法%拓撲結構
무선전감기망락%련통회복%사변형사탄납수%계발식산법%탁복결구
wireless sensor network%connectivity recovery%quadrilateral Steiner tree%heuristics algorithm%topology
在恶劣环境下无线传感器网络的节点和通信链路常常会失效,致使网络被分割为很多分离的分区,因此通过布置尽量少的中继节点实现高健壮性的连通恢复对于维持网络的正常运作必不可少.对于一个被分割的无线传感器网络,找到相应的位置布置最少中继节点恢复连通是一个NP难题,在实际应用中只能采用启发式算法.文中提出了一种新的基于四边形斯坦纳树的算法来恢复网络连通.此算法首先探测出各分区并确定各分区的代表节点及其位置,然后寻找合适的四边形连接分割的网络分区,确定这些四边形的斯坦纳点;对无法用四边形连接的各连接部分用三角形斯坦纳树或最小生成树的方法连接;最后沿着斯坦纳树的边在相应位置布置中继节点,实现网络连通的恢复.大量的仿真实验表明文中提出的方法能够减少所需中继节点的数量,恢复后的拓扑结构中节点的连通度更高,容错性更好.
在噁劣環境下無線傳感器網絡的節點和通信鏈路常常會失效,緻使網絡被分割為很多分離的分區,因此通過佈置儘量少的中繼節點實現高健壯性的連通恢複對于維持網絡的正常運作必不可少.對于一箇被分割的無線傳感器網絡,找到相應的位置佈置最少中繼節點恢複連通是一箇NP難題,在實際應用中隻能採用啟髮式算法.文中提齣瞭一種新的基于四邊形斯坦納樹的算法來恢複網絡連通.此算法首先探測齣各分區併確定各分區的代錶節點及其位置,然後尋找閤適的四邊形連接分割的網絡分區,確定這些四邊形的斯坦納點;對無法用四邊形連接的各連接部分用三角形斯坦納樹或最小生成樹的方法連接;最後沿著斯坦納樹的邊在相應位置佈置中繼節點,實現網絡連通的恢複.大量的倣真實驗錶明文中提齣的方法能夠減少所需中繼節點的數量,恢複後的拓撲結構中節點的連通度更高,容錯性更好.
재악렬배경하무선전감기망락적절점화통신련로상상회실효,치사망락피분할위흔다분리적분구,인차통과포치진량소적중계절점실현고건장성적련통회복대우유지망락적정상운작필불가소.대우일개피분할적무선전감기망락,조도상응적위치포치최소중계절점회복련통시일개NP난제,재실제응용중지능채용계발식산법.문중제출료일충신적기우사변형사탄납수적산법래회복망락련통.차산법수선탐측출각분구병학정각분구적대표절점급기위치,연후심조합괄적사변형련접분할적망락분구,학정저사사변형적사탄납점;대무법용사변형련접적각련접부분용삼각형사탄납수혹최소생성수적방법련접;최후연착사탄납수적변재상응위치포치중계절점,실현망락련통적회복.대량적방진실험표명문중제출적방법능구감소소수중계절점적수량,회복후적탁복결구중절점적련통도경고,용착성경호.
