基于電量均衡的無線傳感器網絡分簇算法

2.2 四色法

為了增大簇之間的間隔，減少重疊區域，TopDisc算法還提出了四色法。節點可以處于四種不同的狀態，分別用白色、黑色、灰色和深灰色表示。前三種顏色代表的含義與三色法相同，增加的深灰色表示節點收到過拓撲發現請求，但不被任何標記為黑色的節點覆蓋。

在初始階段，所有節點被標記為白色，算法由一個初始節點發起，算法結束后所有節點都將被標記為黑色或灰色(假設整個網絡拓撲是連通的，注意最終沒有標記為深灰色的節點)。詳細過程描述如下：

(1)初始節點被標記為黑色，并向網絡廣播拓撲發現請求;

(2)當白色節點收到來自黑色節點的拓撲發現請求時，將標記為灰色，并在延時時間tWB后繼續廣播拓撲發現請求。tWB反比于它與黑色節點之間的距離;

(3)當白色節點收到來自灰色節點的拓撲發現請求時，將標記為深灰色并繼續廣播拓撲發現請求，然后等待一段時間tWG(同樣與距離成反比)。如果在等待期間收到來自黑色節點的拓撲發現請求時，則改變為灰色，否則它自己成為黑色;

(4)當白色節點收到來自深灰色節點的拓撲發現請求時，等待一段時間(同樣與距離成反比)。如果在等待期間，收到來自黑色節點的拓撲發現請求時，則改變為灰色，否則它自己變為黑色，并廣播拓撲發現請求;

(5)所有已經被標記為黑色或者灰色的節點，都將忽略其他節點的拓撲發現請求。

與三色法相比，四色法形成的簇數目更少，簇與簇之間的重疊區域也更小。但是可能形成一些孤立的標記為黑色的節點不覆蓋任何灰色節點。雖然三色法和四色法形成的黑色節點數目相當，但四色法中傳輸的數據量要少一些。

TopDisc算法利用圖論中的經典算法，提出了一種有效方法來構建網絡的近似拓撲，是分簇算法中的經典算法。它是一種只需要利用局部信息，且完全分布時可擴展的網絡拓撲控制算法。但也存在需要改進的地方，如算法開銷偏大;沒有考慮節點剩余電量的信息。

3 Power-balanced TopDisc算法

WSN中節點轉發數據的耗能模型如下所述。

傳感器節點發射r比特數據包所消耗的能量為：

Pt(r，d)=r(a1+a2dn) (1)

式中：d為兩節點之間的距離;a1是與距離無關的量，包括發射電路所耗能量等;a2是與距離有關的量;n為路徑損耗指數，通常取2～4之間。

傳感器節點接收r比特數據包所消耗的能量為：

Pr(r)=rβ (2)

式中：β盧為接收能量系數。

傳感器節點將2個數據流r1和r2融合成一個數據包r的耗能為：

Pa(r1+r2，r)=r(r1+r2-r) (3)

式中：r為數據融合系數。

從式(1)～式(3)可以看出，若剩余能量較少的節點仍然承擔著較重的轉發任務，那么就很可能導致該節點過早死亡，從而影響網絡生命時間的延續。所以，在構建無線傳感器網絡拓撲時，節點應選擇剩余能量多的節點作為數據轉發的主要節點，而剩余能量較少的節點作為數據源節點，這樣將有效解決由于負載過大而過早死亡的問題。

為便于描述和分析，作如下假設：

(1)每個節點都具有相同的最大發射功率，其覆蓋范圍是半徑為R的圓形區域，且可通過調節發射功率以適應其覆蓋范圍內不同距離節點的通信;

(2)每個節點都能夠獲得自身的剩余能量，有一定的存儲空間來存放鄰居節點信息;

(3)忽略真實環境中存在障礙物等影響通信質量的因素，確保所有的數據包都能夠可靠傳輸。

考慮節點電量均衡因素，在TopDisc四色法的步驟(3)中，對tWG進行修正，公式為：

twG=a1/d+a2/p (4)

式中：d為節點之間的距離;p為當前節點剩余的電量;a1和a2為預設參數。對tWG進行修正后得到Power-balanced TopDise算法。

Power-balanced TopDise算法的合理性可以由圖1說明。圖1(a)為TopDisc算法的分簇結果;圖1(b)為Power-balanced TopDise算法的分簇結果。其中，電量為80的節點為初始節點。初始節點發出拓撲發現請求到電量為20的節點變為灰色，并繼續廣播拓撲發現請求。電量為30和90的節點同時收到拓撲發現請求。在Power-balanced TopDisc算法中，電量為90的節點先于電量為30的節點變為黑色，即成為骨干節點(簇頭節點)。

經過上述基于電量均衡的Power-balanced TopDisc算法處理后，剩余能量較少的節點將不再擔當骨干節點，有利于延長網絡的生命周期，從而實現均衡耗能。