[發明專利]一種基于LEACH協議的簇頭選舉改進算法

無效

• 申請號: 201210048921.6
• 申請日: 2012-02-28
• 公開（公告）號: CN102547904A
• 公開（公告）日: 2012-07-04
• 發明（設計）人: 陳曙;李天池
• 申請（專利權）人: 山東大學
• 主分類號: H04W40/02
• 分類號: H04W40/02;H04W84/18
• 代理公司: 濟南金迪知識產權代理有限公司 37219
• 代理人: 王緒銀

1.一種基于Leach協議的簇頭選舉改進算法，其特征在于，將原Leach協議的簇頭選舉算法分為三種簇頭選舉算法：全網簇頭選舉、半網簇頭選舉和簇內簇頭選舉。首先在Leach改進算法中設定一個能量閾值，在每個簇周期開始時，判斷現有各簇中是否存在簇平均能量小于此閾值的情況；如果存在，存在這種情況的簇發起半網簇頭選舉號召，其他簇根據本簇情況，決定是否響應此號召，所有響應此號召的簇，將在下一輪中進行半網簇頭選舉；如果不存在，各個簇頭再判斷自己的剩余能量是否小于本簇的平均能量，如果比平均能量小，則在本簇內啟動簇內簇頭選舉，否則，不進行任何簇頭選舉；由此可避免每輪都進行全網的簇頭選舉；而每隔定值輪數，將會強制進行全網選舉，以平衡半網選舉可能導致的不平衡；

全網簇頭選舉算法

在進行全網簇頭選舉時，使節點剩余能量大、距離Sink節點近的節點優先成為簇頭；節點剩余能量率函數為

Ep(i)=Er(i)Eo---(1)]]>

其中，E_r(i)代表節點的當前剩余能量；E_o代表節點所在簇的平均能量；

網絡在部署階段，Sink節點以較大的功率在網絡內廣播一個消息，每個傳感器節點根據收到信號的強度計算它到Sink節點的近似距離d_i，并將自己的id和d_i發送給Sink節點，使Sink節點掌握一個含有節點id號與距離的對照表；距離因子λ定義如下：

λ=dn-dmindmax-dmin×dn-dmindavg]]>

davg=(d1-dmin)+(d2-dmin)+......+(dn-dmin)n---(2)]]>

其中，d_max、d_avg、d_min分別代表網絡中節點到Sink距離的最大值，平均值和最小值；結合節點能量剩余率和距離因子，給出如下T(n)計算方法：

T(n)=p1-p×(rmod(1/p))+(Ep(n)+∂(1-λ))0---(3)]]>

其中，為加權因子，由于在簇頭的選舉中，能量是首要考慮的因素，因此LEACH改進算法中設置了加權因子其值隨網絡規模和應用場景的不同而不同，此處取0.01；式(3)使剩余能量較高的節點優先于剩余能量較低的節點當選為簇頭，并且在能量消耗大致相同時，由于距離Sink近的節點要承擔數據轉發任務，因此距離Sink節點近的節點優先于距離Sink節點遠的節點成為簇頭，以更好地均衡能量消耗；

半網簇頭選舉算法

在進行第一次全網選舉后，每一輪計算所有簇的簇內平均能量E_avg1、E_avg2、……E_avgK，其中K是簇的數量；平均簇能量E_a為：

Ea=Eavg1+Eavg2+......+EavgKK---(4)]]>

其中任意簇k和E_a的比值θ_k為：

θk=EavgkEa---(5)]]>

當θ_k小于某一閾值時，此簇通過簇首發起半網選舉號召；閾值設置為0.7；當有簇首發起選舉號召時，滿足θ_k在一定區域內的簇，對此進行響應，同意進行半網選舉；響應號召的簇，其θ_k范圍為：θ_k＞1.2或θ_k＜0.8；當完成響應后，進行半網選舉的簇中所有節點將按照全網選舉的規則進行重選，其距離因素和能量因素的規則與全網選舉中距離因子λ和能量因子相同；

簇內簇頭選舉算法

全網每個周期的簇頭選舉完成后，進入穩定的數據傳輸階段；在一個周期內，由于各簇的能量消耗有很大的差別，對于能量消耗較大的簇，如不適時選舉新的簇頭，節點會很快死亡，網絡就會出現路由洞，但是對于能量消耗很少的簇，如果經常進行簇重組，則會浪費能量；在Leach改進算法中，當簇頭節點的能量小于簇內能量的平均值E_avg時，簇頭將通知簇內E_r(i)最大的節點成為簇首并向其他簇內成員廣播此消息，簇內成員根據廣播信息修改相應的簇頭信息；當簇內出現E_r(i)相同的節點時，選取距離因子λ最小的節點成為簇頭，完成簇內簇頭選舉。