針對無線感測器網路中的網路能耗問題，提出了改進leach簇首與簇內節點擊取的leach-tr演算法，該演算法不僅利用了原leach模型形成簇的演算法,也運用了數學思想中的剩餘能量均值演算法選取簇形成節點。首先，根據根據簇首節點的閾值公式選取最優的簇首節點；其次，根據簇內節點剩餘能量與節點剩餘能量的門限值進行比較，選擇最適合作為簇首的功能節點出無效的簇內節點；最後，再次根據簇內節點剩餘能量與節點剩餘能量的門限值進行比較，選出無效的簇內節點。**實驗結果證明，該演算法可顯著的減少節點能耗，進而有效降低整個無線感測器網路整體結構的網路能耗。
關鍵字：無線感測器網路；leach；簇首；簇內節點
0.引言
無線感測器網路(wsn)是一種高密度、微小型、自組織的無線監控網路。網路中的節點能夠根據外界環境因素的變化自主完成指定的測量任務和監測任務。但無線感測器網路資源能量受限對感測器節點的組網、網路拓撲發現技術帶來了難點。
因此研究降低網路能耗、延長網路生命週期成為重點。
無線感測器網路具有網路規模大、節點數目多，同時具有很強的擴充套件性等特點。因此，多跳通訊方式比對等通訊方式在無線感測器中的應用更為廣泛。為了能夠方便管理節點，本文通過多跳通訊方式獲取網路的拓撲資訊，即對感測器網路節點進行分簇處理。
leach演算法是一種比較成熟的分簇處理演算法，但leach演算法忽視了簇首節點的覆蓋範圍、能量不均等問題。故文中對於降低節點能量消耗，延長網路的生命週期，主要通過設定簇首節點的選取閾值和簇內節點的剩餘能量要求進行了改進，並通過matlab環境進行了改進演算法的**。
1.演算法的實現
1.1改進演算法的思想
基於leach演算法的思想，改進演算法主要包含兩個部分。首先是根據簇首節點的閾值公式選取最優的簇首節點。第二步是根據簇內節點剩餘能量與節點剩餘能量的門限值進行比較，選擇出無效的簇內節點。
1.2演算法改進初始條件
(1)路由協議採用分層和分簇的leach演算法；
(2)每個節點已知自身的剩餘能量值；
(3)每個節點已知到達簇首節點的距離；
(4)節點資訊包在傳輸的過程中沒有誤位元速率；
1.3簇首節點的選取
簇首的建立是基於leach演算法，leach演算法中簇首節點的選擇由網路覆蓋範圍的大小以及所有節點已經成為過簇首節點的次數決定。具體的做法是隨機產生乙個在(0,1)範圍內的隨機數字，根據公式(2)設定門限值t(n),若這個隨機數小於設定的門限值t(n),則將該節點定為簇首節點。改進門限值，加入簇首剩餘能量的取值範圍。
(2)其中，p為期望的簇首節點個數，r為當前節點回合數量。
對於簇首節點的選取，在滿足小於門限值t(n)條件之後，再度衡量節點的剩餘能量和能量權值因子，選取剩餘能量相對而言較大的節點作為之後優先考慮的簇首節點，並在已被選定的簇首節點圓周通訊半徑r內，即使存在同時滿足門限值和剩餘能量值的其他節點，均不考慮作為簇首節點，避免簇首節點的選取集中於某乙個區域，導致一些節點因為周圍沒有簇首無法加入網路或加入遠距離簇首節點致使能量消耗過快。如圖1，能量權值函式如公式(3)所示。
其中，w(n)為能量權值函式，p(i,c)為第c「輪」中節點i能量的權值因子，權值越大越適合做簇首，為所有節點的剩餘能量平均值，m為選取簇頭節點的最佳個數，為大於平均剩餘能量值的節點集合。剩餘能量的門限值與節點的剩餘能量平均值成線性關係，且對不同的剩餘能量平均值有不同的門限限制，在每次leach演算法進行選簇首時只有滿足上式關係(3)後才能有成為簇首節點的可能。即改進後的簇首節點選取需要滿足公式(4)要求，此方法降低了選取簇節點的隨機性，能夠有效降低網路節點能量的消耗。
(4)1.4簇內節點的選取
對於簇內節點是否能加入網路，也具有一定的要求，通過設定最低簇節點剩餘能量門限值，將小於能量門限值的節點主動放棄加入網路，減少網路負荷量，延長網路的生命週期。如圖3，當節點剩餘能量不足以支撐與距離處簇首的資訊互動，則主動放棄加入。簇內節點傳送訊息能量需求與距離之間的關係如公式(6)所示。
（5）6）其中，為剩餘能量參量，表示節點i剩餘能量佔簇內節點剩餘能量總值的參量。是簇內節點傳送位元資料需要的能量值，為一次上報傳輸的首席資訊官度，為上報節點與接收節點間的傳輸距離。簇內節點的選取，根據公式(5)中所佔參量的數值，選取其中所佔參量份額最小的節點i，將節點i的剩餘能量值與比較，若剩餘能量小於即可表示節點沒有足夠的能量傳輸資料，主動放棄加入網路。
具體節點擊取實現演算法如下：
(1)組網開始，每個感測器節點隨機選擇自身概率p，節點根據概率與閾值的關係決定是否能夠成為簇首，並將有可能成為簇首的節點組成預簇首集合；
(2)在可能成為簇首節點組成的集合中，將節點的剩餘能量值與剩餘能量門限值比較，若能夠大於剩餘能量門限值，再次組成預簇首集合；
(3)在預簇首集合中，按照剩餘能量的大小先後選取總節點個數的5%作為簇首節點。其他預簇首節點皆降為普通節點；
(4)節點被選定為簇首節點之後，傳送廣播(adv)通告整個網路，網路中的其他節點根據接收的訊號強度自主的選擇要加入的簇首，並回覆相應的簇首節點，基礎簇的建立部分完成。
(5)根據節點所佔總簇內節點能量的參量，計算出簇內節點占有份額最小的點。
(6)根據節點的剩餘能量門限判斷份額較小點的有效性。當被測節點的剩餘能量不小於節點剩餘能量門限值，則為有效節點。否則為無效節點，自主放棄加入網路的節點；
(7)整體簇的建立完成；
(8)簇首節點採用tdma方法為簇內每個節點分配各自的傳輸資料的時間片；
圖1 簇首節點的選取
圖2 自組織網路
圖3 簇內部節點的選取
2. 軟體實現流程圖
改進後簇的形成階段，節點成為簇首或者是簇內節點的流程以及資料傳輸流程如下圖4所示。
圖4 軟體流程圖
3.軟體**
3.1 **環境
文中在matlab r2009a軟體環境下進行**實驗，查閱相關文獻資料，對演算法**場景主要引數作如表1設定。
圖5為感測器節點隨機部署分布圖。圖中所圍正方形區域表示乙個100m*100m的監測子區域。符號「」表示通過飛機空投等方式隨機拋撒在監測區域的普通感測器節點，「」表示子區域的匯聚(sink)節點。
橫縱座標均表示長度，單位為公尺。
表1 **實驗引數
圖5 節點初始分布圖
參照表1**引數設定，感測器節點被隨機拋撒至監測區域之初，節點的初始能量均相同，隨著演算法的執行，感測器節點的能量被不同程度的消耗，leach演算法仍按照隨機的方式選取簇頭，而改進演算法leach-tr由於引進了能量權值因子，使得兩種演算法的簇頭分布狀況出現差異，且差異會隨著演算法執行輪數的增加而增大。
3.2 簇首節點分布情況
圖6和7表示向100m*100m範圍大小的監測區域內拋撒100個普通感測器節點時，leach演算法和改進演算法leach-tr執行至第300輪時簇頭節點的分布狀況。圖中符號「*」表示簇頭節點，「」表示普通簇內成員節點，「」表示sink節點，「」表示當前輪數已死亡的節點。實線連線的是簇頭節點與簇內成員節點間的資料傳輸路徑，虛線連線的是簇頭節點與sink節點間的資料傳輸路徑，「+」號線連線的是超級簇頭節點與簇頭節點間的資料傳輸路徑。
圖中橫縱座標均表示長度，單位為公尺。
圖6 leach第300輪分簇
圖7 leach-tr演算法的第300輪分簇
leach演算法和改進演算法的分簇狀況差異變得明顯。改進演算法使得剩餘能量少的節點在下一輪被選作簇頭的概率降低，相比leach演算法等概率選舉簇頭，其可延緩節點的能量消耗。隨著網路的不間斷的執行，leach演算法分簇不均衡問題會越發明顯，越能體現出改進演算法的分簇優勢。
3.3 節點剩餘能量
網路剩餘能量的多少，是直接關係到網路是否能夠繼續工作的關鍵指標。為了使網路在各個階段的能量消耗情況被更清楚的知曉，下面隨著時間的推移，對分別應用leach和改進演算法的網路執行至不同輪數時整個網路剩餘能量的變化趨勢進行統計分析。
圖8表示隨時間推進，在網路採用不同演算法時，剩餘能量的變化趨勢。圖中橫座標表示演算法執行的輪數，單位為輪；縱座標表示網路剩餘能量，單位為焦。
圖8 剩餘能量對比圖
由圖8中可知，兩種演算法隨著執行輪數的逐漸增多，採用leach-tr演算法網路的剩餘能量衰減要慢於leach演算法，同時leach演算法剩餘能量大幅度衰減出現的輪數也比leach-tr出現的輪數早。
4.結論
針對leach演算法中忽視節點剩餘能量及閾值概率的不確定性，提出的一種基於節點覆蓋範圍、剩餘能量改進leach-tr演算法，該演算法改進了簇首節點選擇的閾值和簇內節點有效的閾值。解決了「低頻簇首」節點，簇首覆蓋範圍不均衡等現象。**結果表明，改進閾值的leach演算法不僅能夠有效降低節點能量消耗，而且節點的存活時間延長，網路生命週期增加，使網路具有更好的通訊效率。
[1] 欒偉平.基於移動**的無線感測器網路拓撲發現及節點分簇演算法[d].西安電子科技大學碩士**.2012.
[2] 凡高娟,王汝傳.基於移動agent的無線感測器網路拓撲發現機制[j].計算機技術與發展.2012.09.
[3] 申軍,齊望東.一種新的無線感測器網路拓撲發現演算法[j].計算機應用研究，2009.05.
[4] 王德,李學千.zigbee協議棧的分析與設計[j].廈門大學，2005.
改進的LEACH演算法 物聯網作業
3.3 leach 演算法侷限性的理論分析 leach 協議的成簇思想貫穿於其後發展出的很多分簇路由協議中，該協議改進了 dd 等平面路由協議的不足，節省了節點傳輸資料所耗費的能量，從一定程度上延長了整個網路 的生存週期 但由於 leach協議每輪固定簇首之後再建立簇，故簇首開銷較大 並且要求感測器...
五子棋AI演算法的改進方法
又是本人乙份人工智慧作業 首先道歉，從word貼到livewrter，好多格式沒了，也沒做 高亮 大家湊活著看 想做個好的人機對弈的五子棋，可以說需要考慮的問題還是很多的，我們將製作擁有強大ai五子棋的過程分為十四步，讓我來步步介紹。第一步，了解禁手規則 做乙個五子棋的程式，自然對五子棋需要有足夠的...
改進Harris特徵點的機械人定位演算法
年第 卷第 期感測器與微系統 李永佳 周文暉 沈敏一 徐 進 林 穎 劉濟林 浙江大學資訊與電子工程學系，浙江杭州 杭州電子科技大學計算機學院，浙江杭州 摘要 提出一種改進 特徵點的機械人精確定位方法，通過改進特徵點提取 匹配 跟蹤策略，為運 動估計提供更加可靠的輸入，提高運動估計結果的準確性。具體...