一種基于反向CDS樹的異構WSNs拓撲構建方法*

楊明霞，王萬良，馬晨明

（1.浙江工業大學計算機學院，杭州310023；2.衢州學院電氣與信息工程學院，浙江衢州324000）

?

一種基于反向CDS樹的異構WSNs拓撲構建方法*

楊明霞1，2，王萬良1*，馬晨明1

（1.浙江工業大學計算機學院，杭州310023；2.衢州學院電氣與信息工程學院，浙江衢州324000）

摘要：在無線傳感器網絡中，拓撲控制是節約能源、延長生命周期的一項關鍵技術。現有拓撲控制方法的研究主要集中在同構網絡，對此，面向異構網絡提出了一種低信息復雜度的基于反向連通支配集樹的分布式拓撲構建算法。基于最小連通支配集構建虛擬骨干樹，改進了A3G算法中節點的適應度函數和算法流程，優化了產生的連通支配集的規模和通信開銷，進一步降低信息復雜度，在保證連通性的同時關閉網絡冗余節點以降低能耗。理論分析和仿真實驗證明，算法能夠以較小的時間和通信代價構建拓撲，延長網絡生命周期。

關鍵詞：異構無線傳感器網絡；拓撲控制；拓撲構建；A3G算法；最小連通支配集

無線傳感器網絡WSNs（Wireless Sensor Net?works）是由能量受限的傳感器節點通過自組織形成［1］，節點往往需要部署在人類不易接近或無人值守的區域，依靠攜帶的電池維持工作，如何節省能量已經成為研究無線傳感器網絡的重要問題之一。作為無線傳感器網絡中的基礎性課題，拓撲控制［2］是節約能量、增加運行時間的一項關鍵技術。通過優化網絡拓撲結構，可以降低節點之間的通信干擾，均衡網絡的能耗，對路由優化、資源分配等具有重要意義。

拓撲構建是拓撲控制中的首要過程，將一個全連通的稠密網絡拓撲圖轉化為相對簡單、清晰的拓撲結構圖。拓撲構建算法一般可以分為中心算法和分布式算法。中心算法采用Client/Server的通信模式，先由網絡中的Sink節點來對其他節點的信息進行搜集，然后從全局拓撲中選出支配節點。該類算法通常能夠得到較小的支配集規模，但是算法的時間復雜度和空間復雜度過大；同時這種方式不能算是嚴格的物物相連，因為傳感器節點與基站之間通過主從式的方式進行數據通信。分布式算法以P2P的模式實現物與物之間的多跳連接，不需要對網絡中的所有節點信息進行搜集，而只是搜集k跳范圍內的節點信息，然后由各個節點根據本地信息自組織建立一個網絡虛擬骨干。分布式算法能夠以較小的時間和通信代價構建連通支配集，具有較強的擴展性，必然是物聯網下一階段的發展方向。其缺點是求解的支配集規模較大。

當前使用最廣泛的拓撲構建方法是基于最小連通支配集MCDS（Minimum Connected Dominating Set）構建虛擬骨干樹［2］。它的基本思想是采用節點休眠的方式，關閉網絡中的非必要節點，以減少節點之間的通信干擾；而工作的節點組成的虛擬骨干仍然保持網絡連通性和網絡覆蓋率等重要特性。網絡節點分為支配節點和普通節點，支配節點負責監聽并轉發數據，而普通節點則進入休眠狀態，在保持網絡連通的前提下關閉網絡拓撲中大部分不必要的節點，減少了數據通信量，降低了擁塞發生的概率。所謂支配集是指網絡中除支配集中節點以外的其他節點的鄰居節點中都至少存在一個支配節點，如果該支配集中所有節點之間都可以單跳或者多跳到達，那么該支配集是連通的，即為連通支配集。因此，選擇哪些節點位于虛擬骨干上，哪些節點屬于冗余節點，則是拓撲控制算法研究的主要內容。

1　相關工作

最小連通支配集中存在著大量可供研究的問題，一直以來都是學者們研究的熱點。例如由于在很多情況下MCDS問題存在多個解，各個解可能在某一情況下是最優的，而在另外的情況下就不是最優的，所以要求解規模最小的連通支配集并不容易。文獻［3］和文獻［4］已經證明MCDS問題是典型的NP-hard問題，在實際應用中需要采用近似或啟發式算法進行求解。

MIP-MCDS［5］以某個節點作為中心，利用令牌流技術對MCDS問題進行數學建模，將最小化網絡分發的令牌數作為目標函數。NMIP-MCDS［6］在文獻［5］的基礎上進行了改進，將節點的剩余能量作為約束條件引入目標函數，利用全局拓撲，算法能獲得較小的MCDS，但是求解過程需要節點之間的大量通信。以上兩種算法均采用令牌流對MCDS問題進行中心數學建模，以最小化網絡分發的令牌作為目標函數，求解完畢后各個持有令牌的節點組成最小連通支配集。算法計算復雜度較高，因而適用于節點規模較為稀疏的網絡。

PSCASTS［7］采用最大獨立集技術構建網絡拓撲。首先，鄰域內擁有最大節點度的節點優先成為支配節點，得到一個支配節點之間互不相連的最大獨立集；在第二階段中連通最大獨立集中的節點，生成一個未經優化的連通支配集；最后使用修剪規則去掉冗余的支配節點。算法雖然能夠產生較小規模的連通支配集，但是需要通過信息交換獲得兩跳鄰域內的節點信息，因此時間和信息復雜度較大，而且也沒有考慮節點剩余能量對構建連通支配集的影響。EB-MCDS［8］將節點度和剩余能量作為節點的權值，優先選擇權值較大的節點成為支配節點，但算法在構造最小連通支配集的過程中同樣需要利用兩跳的鄰域信息，這樣就使得信息的復雜度達到了O（nΔ），因而同樣只能應用在規模較小的網絡中。

A3［9］采用生成樹構造連通支配集，活動節點首先廣播Hello消息搜集一跳鄰居節點的信息，鄰居節點收到消息后計算剩余能量和信號強度，并回復認知消息給上層的活動節點；父節點收到回復后通過子節點給出的權值大小進行排序，然后根據權值排序的列表生成節點等待時間列表，并發送給鄰域中的子節點；鄰居子節點在等待列表時間結束后，嘗試競爭成為活躍節點，如果成為活躍節點就在下一跳節點中繼續以上過程，最終得到一個能夠覆蓋全網的活躍節點集。A3能夠得到較小的連通支配集規模，但是通信的開銷較大。A3G［10］對這方面進行了改進，采用了逆向構建CDS樹的過程，減少了部分通信開銷，但是算法在支配節點規模和通信開銷上還是存在進一步優化的地方。在最壞情況下，A3G將最終發送4n個消息，考慮到密集部署的網絡中，鄰居節點將會接收到數量巨大的信息，這將會對網絡的能耗產生巨大影響。

在對A3G產生的支配節點情況進行仔細分析后，發現算法產生的支配節點規模可以進一步優化。本文中，基于最小連通支配集構建虛擬骨干樹，改進了A3G算法中節點的適應度函數和算法流程，優化了產生的連通支配集的規模和通信開銷，在保證連通性的同時關閉網絡冗余節點以降低能耗，進一步降低信息復雜度。

2　系統模型

2.1網絡模型

用單位圓盤圖G（V，E）表示無線傳感器網絡的基本模型，其中V表示傳感器節點集合，E是由V中節點組成的通信鏈路集合，首先給出如下假設：①N個傳感器節點隨機部署在M×M的正方形區域內，部署后不再移動；②Sink節點位于區域的中心位置（M/2，M/2），且計算、存儲和能量均不受限制；③初始網絡拓撲圖為全連通圖；④節點通過ID進行唯一標識，且計算、存儲和能量受限，但是節點不需要配備GPS等昂貴設備獲得其他節點的位置信息；⑤節點可以通過接收信息的信號強度RSSI獲得與鄰居節點之間的距離d；⑥節點具有通信半徑Rc和感知半徑Rs，其中通信半徑用來確保節點的連通性，而感知半徑用來感知監控區域的數據；⑦如果任一節點vi的通信半徑Rc（i）范圍內存在任一其他節點vj，則說明節點vi和vj之間的距離d小于等于Rc（i），如果繼續有d≤Rc（j），那么節點vi和vj被稱為是直接鄰居節點，兩個節點之間存在通信鏈路（vi，vj）?E，否則兩個節點之間不存在任何直接通信。

圖1　網絡拓撲圖

以圖1為例表達滿足上述條件的網絡拓撲。帶有同心圓的節點是Sink節點，部署在正方形區域的中心位置，其它黑色表示的傳感器節點隨機部署在區域中；圖中節點與節點之間的連線表示通信鏈路，即節點之間的距離d小于等于通信半徑Rc。初始網絡是一個連通圖，即圖1中不存在任何孤立的節點。以Sink節點為中心包括兩個圓，其中大圓表示的是通信半徑Rc，而小圓表示的是感知半徑Rs。

2.2無線通信能量模型

在無線通信過程中，本文采用的能量模型是由文獻［11］提出的無線通信能量模型，當發送方與接收方的距離為d時，發送與接收k比特數據能耗的計算公式如式（1）和式（2）所示，式（3）表示的是鏈路中發送與接收k比特數據消耗的總能量。其中，Eelec為節點發送或接收單位比特數據消耗的能量，參數ξfs為功率放大器消耗的能量系數。

3　基于反向生成CDS樹的拓撲構建算法

3.1數據結構

本節對A3G拓撲構建算法進行優化，提出了最優MCDS和信息開銷的拓撲構建算法A3GLM（Low Message），算法以減少活躍節點數和信息開銷為目標，將過程分為鄰居節點發現、鄰居信息交換以及虛擬骨干反向構建三個過程。在同構網絡中，當節點u收到鄰域內節點v的消息后，即可以確定節點v同樣可以接收到節點u廣播的消息，u，v處于同一通信半徑內。本文考慮網絡中節點的通信半徑存在異構的情況，因此需要比較節點之間距離和節點的通信半徑用來確定節點之間是否可以連通。通過比較節點之間的距離與通信半徑的方法，只需要一次信息交換就能判斷節點之間是否可以進行通信。假設節點u收到了節點v發送的Hello消息，節點通過RSSI信號強度可以獲得節點u，v之間的距離d（u，v），然后將自己的通信半徑Ru和該距離進行比較，如果發現Ru≥d（u，v），那么就可以確定節點之間可以進行通信，這樣就確定了異構網絡中的節點的鄰居節點集合。初始時，網絡中節點的狀態都為Initial；算法結束后，節點狀態將變成Active或Sleep。算法中主要包括四種消息類型，分別為Hello、Recognition、Confirm以及Notify消息，其中Hello消息用來進行鄰居節點發現，而Recog?nition消息用于在鄰居信息交換中上層節點向下層節點發送鄰居節點的權值列表信息，Confirm和Notify消息分別用于虛擬骨干反向構建中向上確認和通知骨干節點，相關消息的數據結構如表1～表6所示。

表1　Hello消息的表頭格式

表4　Notify消息的表頭格式

表5　列表List1、List2和List3的數據格式

表6　列表List4的數據格式

支配節點的個數是衡量拓撲控制算法優劣的重要指標，支配集節點的個數越少，處于休眠狀態的節點數就越多，從而可以有效節省節點能耗。為了更好地對節點的優劣進行排序，定義了兩種不同形式的適應度函數，第一種適應度函數在缺乏鄰域內節點的拓撲信息時，將節點的剩余能量、節點之間的距離作為適應度函數的參數，具體公式如下：

其中，ω1，ω2，ω3表示對應的權值，在初期進行設定，分別表示剩余能量、節點之間的距離以及節點的通信半徑大小對當前適應度函數的影響程度。假設用戶希望確保選擇能量更多的節點，那么權值ω1通常大于其他兩個參數，這樣能量更高的節點將會被加入到連通支配集中。Eu和Emax分別表示節點u的剩余能量和最大初始能量；Ru和Rmax分別表示當前節點的最大通信半徑；d表示當前節點與上層活躍節點之間的距離，可以通過接收到信號強度RSSI獲得。相比A3G算法定義的適應度函數，本文考慮節點存在異構的情況下，節點的通信半徑越大，那么它可以覆蓋的節點數就越多，成為活躍節點的可能性也就越大。隨著算法的深入，節點在不損失通信代價的基礎上通過節點之間的信息交換可以獲得更多節點的其他信息，所以第二種適應度函數fitness2增加了鄰域可覆蓋節點的個數作為適應度函數的參數，具體公式如（5）所示：

其中，ω1，ω2，ω3，ω4表示對應的權值，分別表示剩余能量、鄰居節點的個數、節點之間的距離以及節點的通信半徑大小對當前適應度函數的影響程度。假設用戶希望獲得數量更少的連通支配集節點，那么權值ω2通常大于其他參數，這樣單位覆蓋能力更強的節點將會被加入到連通支配集中，從而可以減少連通支配集中節點的個數，其他參數同理。其中，Num（u）表示當前節點可覆蓋的下層節點數，List4（u）是一個存儲當前節點的上層節點列表，列表的詳細說明在后面的算法闡述中進行描述。可見，如果單位節點的可覆蓋節點數量越多，那么所需要的活躍節點數就越少，從而可以得到較少的支配集數量。式（5）的其他部分與式（4）相同。下面對A3GLM算法過程進行描述。

3.2算法描述

3.2.1鄰居節點發現過程

節點之間在鄰域范圍內通過廣播Hello消息發現鄰居節點。

Step 1假設節點u收到了節點v發送的Hello消息，考慮網絡中存在異構節點的情況，比較當前節點u的最大通信半徑Ru和發送節點v和接收節點u之間的距離d（u，v）；

Step 2如果Ru≥d（u，v），則確定是鄰居節點，接著檢查當前節點u的hop屬性。如果發現hop屬性還沒有進行初始化或者當hop大于v.hop+1，需要對u.hop進行更新u.hop=v.hop+1；

Step 3根據節點的剩余能量Ecur和節點之間的距離d（u，v）按照式（4）計算節點的適應度函數fitness1，并將節點信息保存在列表List1中。以上步驟從Sink節點開始，廣播Hello消息并將節點狀態改變為state1，每個節點收到消息后，按照上述方法進行更新，然后自己廣播一個Hello消息。如果是狀態為state1的節點u收到Hello消息，并且滿足u.hop==hop-1，那么節點將發送節點的ID和參數進行存儲，記為列表List2，而如果是u.hop==hop的節點，將其存儲到List3；如果當前收到消息的節點的狀態為Initial，那么該節點在存儲信息后廣播一個Hello消息。算法以Sink節點為中心由內向外，層層進行擴展，直到所有節點的狀態都變成state1，將在發送Hello信息之后，不再收到來自下一層節點的Hello信息的節點稱為葉節點。

3.2.2鄰居信息交換過程

第一階段完成后，算法開始啟動鄰居信息交換過程。

Step 1 Sink節點為初始執行者，節點對列表下層節點列表List2中的節點信息按照適應度函數fitness1的大小進行排序。如果具有相同的適應度函數fitness1大小，則將ID較小的排在前面，這樣就不存在兩個權值完全相同的節點。

Step 2排序過程完成后，節點將自己的狀態改變為state2，并且廣播一個Recognition消息。

Step 3鄰居節點收到消息后，如果當前的狀態為state1，則需要將發送節點的ID和排序后的列表存儲到列表List4中。

除了葉子結點外，待所有節點廣播完畢后，該過程結束。在具體實現中，可以使用兩個定時器T1和T2分別完成這兩個過程，節點在將狀態改變為state1時啟動定時器T1，當T1結束后開始鄰居信息交換過程，然后在將狀態改變為state2時啟動定時器T2，定時器T2結束后鄰居信息交換過程就結束了。

3.2.3虛擬骨干反向構建過程

該過程從葉子節點開始，各個葉子節點首先會根據節點的hop屬性啟動一個與之成反比的定時器T3等待超時結束，該值通常可以設得較大以保證超時結束時前一層的葉子節點都已經完成了選擇。這一步驟是對A3G算法的優化，能防止產生過多的支配節點。

超時結束后，列表List2中的權值最大的葉子節點根據式（5）計算各個上層節點的適應度函數fit?ness2。選擇fitness2最大的節點作為骨干節點，廣播一個Confirm消息，在消息包中將參數Best設置為骨干節點的ID號，這樣就可以對A3G中的通信開銷進行優化。下面舉例說明。

假設時刻t1，節點u廣播一個Confirm消息，鄰居節點v收到該消息后，如果發現BestID等于當前節點的ID，則成為骨干節點；否則，在列表List1-List3中確認當前節點是否可以被BestID節點覆蓋，如果可以則進入休眠模式，否則需要繼續等待直到它可以發送Confirm消息。當等待時間結束后，如果發現節點可以被BestID節點覆蓋，但是當前節點是葉子節點，那么它首先檢查自己鄰居中權值最大的ID是否等于BestID，如果不相等還需要廣播一個Notify消息通知它的上一跳權值最大的節點成為“偽葉子節點”，此時“偽葉子節點”就需要繼續向上確認骨干節點，直到當前“偽葉子節點”節點已經成為骨干節點或到達Sink節點，這一操作在保證和A3G相同的通信開銷下可以縮小產生的活躍節點規模并確保網絡節點被完全覆蓋。

4　仿真

4.1實驗環境及參數設置

仿真實驗采用Atarraya［12］作為平臺對算法進行評估。首先對網絡部署區域大小和傳感器節點的數量N進行設置，然后選擇節點的部署方式（隨機部署、均勻部署或按照指定規則進行部署），將N個節點分布到網絡區域中，這一過程中同樣可以對節點的能量模型、節點能量、節點的通信半徑和中心節點Sink的位置等參數進行設置。上述過程完成后，選擇合適的拓撲構建算法作為仿真目標，并同時對算法和協議中的適應度函數的權重參數、數據采集頻率等涉及具體算法的參數進行設置。所有參數設置完成后，開始運行算法并等待最終結果的顯示。實驗數據包括拓撲生成的時間、生成的連通支配集中的節點個數、信息的發送數量、網絡能量消耗比率（將能耗比率定義為網絡中節點消耗的能量與初始能量的比值）。拓撲生成的時間用于說明本文提出的分布式算法相比集中式算法的優越性，而生成的活躍節點個數則是對連通支配集中的節點個數進行衡量。產生的活躍節點個數越少，說明處于工作狀態的節點數量越少，減少活躍節點的數量是檢驗算法性能的重要指標之一。信息的發送數量和能量消耗比率則是對算法的通信開銷情況進行衡量，因為網絡拓撲的通信開銷關系到網絡的生命時間，拓撲構建的開銷越小，算法的可擴展性就越強。

表7　仿真實驗參數設置

實驗結果取自隨機生成的20個拓撲實例分別運行20次后的平均值，考慮到算法中需要傳輸所有鄰居節點排序后的列表數據，將這類消息包的大小設為100 byte，其他消息包的大小設為40 byte，其他相關的實驗參數如表7所示，這里具體的實驗參數設置都是在總結歸納文獻［13-14］等有關Atarraya仿真實驗的參數設置的基礎上做出的，節點的數量設置為50～250表示網絡規模從稀疏逐漸變成密集，而通信半徑設置為30 m～90 m則是表述不同的節點的單位可覆蓋能力。

4.2具體實驗設計

下面設計兩組實驗對本章提出的算法進行驗證。

實驗1

假設節點被部署在居民小區、街道、辦公寫字樓、博物館等環境中，這類傳感器節點通常采用規則的方式進行部署，每個節點的鄰居節點數量，節點之間的距離都是具有一定規律的。如圖2考慮了兩種理想的網格部署環境，一類是基于水平—垂直方向的網絡拓撲（H-V Grid），每個節點的鄰域內具有水平、垂直方向的4個鄰居節點可以進行通信；第二類是基于水平—垂直—對角方向的網絡拓撲（H-V-D Grid），每個節點的鄰域內具有水平、垂直和對角三個方向上的8個鄰居節點可以進行通信。

圖2　兩種理想環境下的網絡拓撲結構

首先觀察理想的網格部署環境中的拓撲情況，將A3GLM算法分別與兩個分布式算法A3［9］、A3G［10］和兩個中心算法MIP-MCDS［5］、NMIP-MCDS［6］進行比較。表8給出了5個算法生成拓撲的時間情況，發現兩個中心算法需要消耗很多的時間來構建優化的拓撲結構，這主要是算法采用數學建模，計算復雜度很大，隨著節點密度的增加，這一情況在H-V-D Grid的拓撲結構中更加明顯，這也是分布式算法相比中心算法較好的一個主要原因。

表8　實驗1理想網絡環境中拓撲構建需要的時間

A3GLM和A3G算法因為需要采用三個階段來構建網絡拓撲，所以它的時間大于A3算法，但是相差的時間并不多。而從圖3中的拓撲節點生成的活躍節點數情況來看，A3GLM算法均相比A3和A3G算法有了很大的提高，A3GLM在H-V和H-V-D的理想環境中分別需要大約28.1和24.2個網絡節點，較A3G算法分別減少了5.7%、7.3%的活躍節點，而MIP-MCDS、NMIP-MCDS兩個中心算法由于對全局拓撲信息進行搜集，因而可以求解出更好的活躍節點規模，在兩種情況下NMIP-MCDS分別只需要21.2和19.9個活躍節點。

圖3　實驗1理想網絡拓撲產生的活躍節點數

實驗2

實驗2在保持節點數量不變的基礎上，觀察通過調整節點的傳輸半徑來改變節點度對產生的拓撲結構的影響。傳輸半徑主要取決于臨界傳輸距離的大小CTR［15］（Critical Transmission Range），根據網絡區域的稀疏與密集程度采用不同的計算方法。如果當前拓撲圖比較稠密，那么就需要根據式（6）進行計算：

其中，n表示網絡中為節點的個數，f（n）表示遞增函數，在文獻［15］中采用的是式（7）進行計算。

如果網絡中的節點比較少，那么可以采用式（8）進行計算，其中k為常數，且滿足l為部署區域的邊長。

實驗2將200個節點部署在網絡中，在保持節點數量不變的基礎上通過調整節點的傳輸半徑觀察分布式算法A3、A3G、A3GLM的性能。如圖4所示，A3GLM產生的活躍節點數要少于其他兩個算法的結果，這說明改進后的算法執行后能夠獲得更接近最優值的解，當傳輸半徑為30 m時，A3GLM只需要76.8個支配節點，而A3和A3G算法平均需要82.9個和80.2個支配節點。同時，從圖中還發現傳輸半徑可以根據支配節點下降的速率分為三個區間段，傳輸半徑在30 m～50 m變化時，支配節點數量的下降幅度最快，而傳輸半徑在50 m～80 m變化時，支配節點數量的下降速率已經明顯減少，當傳輸半徑從80變化到90時，A3GLM算法只需要減少2.7個支配節點，這是因為傳輸半徑的增加造成任意節點可通信范圍的增加，即節點度的增加使得單位活躍節點可支配的節點增多，最終需要的活躍節點數相比原來有所減少，而隨著支配節點達到一定的范圍，繼續增加網絡節點數并不需要再大量增加支配節點數量，而所有算法所需要的活躍節點數也越來越接近。

圖4　實驗2改變節點度時的活躍節點數

圖5顯示了各個算法在拓撲構建過程中發送的消息數量情況。在各種最大通信半徑下，A3GLM所需要發送的消息數量都是最少的，這與理論分析中得到的算法在最壞情況下僅僅需要發送3n的消息數量是一致的。當最大通信半徑較小時，A3GLM算法的性能較優，例如在傳輸半徑為30 m時，A3G和A3分別需要發送628.6和718.5個消息數，而算法A3GLM只需要發送大約547.2個消息，相比A3G和A3，分別減少了12.9%和23.8%的通信開銷。

圖5　實驗2改變節點度時的發送消息數

隨著通信半徑的增加，各類算法需要發送的消息數都逐漸減少，這是因為節點的通信半徑增加會一次覆蓋更多的節點，在部署區域一定的條件下，網絡的層次減少，所以需要發送的消息數也就減少了。此外，還發現A3G算法逐漸逼近A3GLM算法，這是因為相比A3G，A3GLM在骨干確認中不再需要發送Sleep消息，這部分的通信開銷等于最終的活躍節點數量，隨著通信半徑的增長，活躍節點數變少了，所能節省的消息數也就少了，也就是說A3GLM算法在通信半徑較小時的性能更優。

圖6顯示了算法的能耗比率情況，A3GLM在拓撲構建中消耗的能量最少，這是因為從能耗公式（1）～（3）中可知，節點的能量消耗與節點發送和接收消息的數據比特成正比，因此交互的消息數量越多所需要傳輸的比特就越多，這樣所產生的能耗自然也就增加了，而從圖4得知A3GLM算法需要發送的消息數量最少，所以它產生的能耗也最低。

圖6　實驗2改變節點度時的能耗比率

與圖5的不同之處在于，隨著通信半徑的增加，各個算法消耗的能量都不斷增加。此外，A3GLM和A3G的差距逐漸減少，這一結果也和圖4中兩者發送的消息數逐漸接近一致。當通信半徑為30 m時，A3GLM算法的能耗相比A3G算法減少了13.5%，這一數據在通信半徑為90 m時僅為2.8%。

6　結論及展望

本文提出了一種可以自適應于異構無線傳感器網絡的分布式拓撲控制方法。在拓撲構建過程中，基于反向生成CDS樹的方法在算法A3G的基礎上進行擴展，將應用范圍擴展到異構無線傳感器網絡，同時減少活躍節點的數量，并降低了網絡的通信開銷。仿真實驗進一步證實，A3GLM拓撲構建算法相比A3G，A3算法，無論在理想還是隨機的網絡環境下，生成的活躍節點數和通信開銷性能上均有了提高，特別是當節點的最大通信半徑較小或網絡中節點數量較多時A3GLM算法性能更優。但是，在數據轉發過程中，算法沒有考慮到支配節點的能耗平衡，只是簡單地將數據向上層節點發送，而網絡的生命時間通常由最先死亡的節點所決定，因此下一步將研究如何在拓撲構建時平衡網絡節點的能量消耗，最終使網絡生命周期最大化。

參考文獻：

［1］Yick J，Mukherjee B，Ghosal D.Wireless Sensor Network Survey ［J］.Computer Networks，2008，52（12）：2292-2330.

［2］Liu Z，Wang B W，Guo L J.A Survey on Connected Dominating Set Construction Algorithm for Wireless Sensor Networks［J］.In?formation Technology，2010，9（6）：1081-1092.

［3］Garey M R，Johnson D S.Computers and Intractability：A Guide to the Theory of NP-Completeness［M］.New York：W H Freeman &Co.，1979.

［4］Johnson D S.The NP-completeness column：the many limits on ap?proximation［J］.ACM Transactions on Algorithms，2006，2（3）：473-489.

［5］Wightman P M，Fabregas A，Labrador M A.An optimal solution to the MCDS problem for topology construction in wireless sensor networks［C］.IEEE Latin-American Conference on Communica?tions（LATINCOM），Bogota，Columbia，2010：1-6.

［6］洪榛，俞立，張貴軍，等.基于最小連通支配集的無線傳感網拓撲構建研究［J］.電子與信息學報，2012，34（8）：2000-2006.

［7］黃行波，程紅舉.無線傳感器網絡中使用連通支配集的最小能耗廣播算法［J］.小型微型計算機系統，2014，35（1）：74-79.

［8］凌飛，吳振華.能量均衡的最小連通支配集分布式算法［J］.傳感技術學報，2012，25（9）：1316 -1321.

［9］Wightman P M，Labrador M A.A3：a topology control algorithm for wireless sensor networks［C］.//IEEE Global Telecommunica? tions Conference，New Orleans，USA，2008：1-6.

［10］仇昌琪，肖明波.基于反向生成CDS樹的無線傳感器網絡拓撲控制算法研究［J］.傳感技術學報，2012，25（12）：1737-1742.

［11］Heinzelman W，Chandrakasan A，and Balakrishnan H.An appli?cation-specific protocol architecture for wireless microsensor net?works［J］.IEEE Transaction on Wireless Communications，2002，1（4）：660-670.

［12］Wightman P M，Labrador M A.Atarraya：a simulation tool to teach and research topology control algorithms for wireless sensor networks［C］.Proc.of 2nd International Conference on Simulation Tools and Techniques，Rome，Italy，2009：26-35.

［13］Wightman P M，Labrador M A.Topology maintenance：extending the lifetime of wireless sensor networks［J］.IEEE Latin America Transactions，2010，8（4）：469-475.

［14］馬晨明，王萬良，洪榛.異構無線傳感器網絡中基于CDS樹的拓撲控制方法［J］.傳感技術學報，2014，27（6）：814-820.

［15］Santi P.Topology Control in Wireless Ad hoc and Sensor Networks ［M］.England，John Wiley and Sons，2005：39-52.

楊明霞（1979-），女，浙江衢州人，衢州學院講師。浙江工業大學在讀博士，研究方向為計算機自動化、無線傳感器網絡；

王萬良（1957-），男，江蘇高郵人，博士生導師。國家級教學名師、享受國務院特殊政府津貼、浙江工業大學計算機科學與技術學院院長，研究方向為計算機網絡化控制、無線網絡。

A Topology Construction Method Based on CDS Tree in Heterogeneous Wireless Sensor Network*

YANG Mingxia1，2，WANG Wanliang1*，MA Chenming1
（1.College of Computer Science，Zhejiang University of Technology，Hangzhou 310023，China；2.College of Electrical and Information Engineering，Quzhou University，Quzhou Zhejiang 324000，China）

Abstract：As a fundamental issue in wireless sensor networks，topology control is a useful way for energy saving.Ex?isting topology control methods are mainly focus on homogeneous network，so a distributed topology construction al?gorithm in the heterogeneous network is presented.The algorithm mainly focused on improving the fitness function and algorithm process of A3G，further reducing the size of set and message complexity，prolong the lifetime and bal?ance energy consumption.Theoretical analysis and simulation experiments confirm that our algorithm can further re?duce the energy consumption of topology construction and extend the network lifetime with low time and message complexity.

Key words：heterogeneous wireless sensor network；topology control；A3G algorithm；topology construction；mini?mum connected dominating set

doi：EEACC：723010.3969/j.issn.1004-1699.2016.02.017

收稿日期：2015-08-14修改日期：2015-10-20

中圖分類號：TP311

文獻標識碼：A

文章編號：1004-1699（2016）02-0248-08

項目來源：國家自然科學基金項目（61379123，61402415）；浙江省自然科學基金項目（LQ12F03011，LQ14F020005，LY13F030011）；寧波市社會發展基金項目（2014C50006）；衢州學院師資隊伍建設基金項目（XNZQN201308）