基于節(jié)點(diǎn)功率控制的無線傳感網(wǎng)絡(luò)拓?fù)渌惴ǚ治霭咐夸汿OC\o"1-3"\h\u15870基于節(jié)點(diǎn)功率控制的無線傳感網(wǎng)絡(luò)拓?fù)渌惴ǚ治霭咐?126621.1CONNECT/BICONN算法 1162151.2AP算法 2功率控制拓?fù)渌惴ǖ乃悸肥峭ㄟ^調(diào)整節(jié)點(diǎn)的發(fā)射功率來動(dòng)態(tài)地調(diào)整整個(gè)網(wǎng)絡(luò)。在節(jié)點(diǎn)發(fā)射功率變化時(shí)，整個(gè)網(wǎng)絡(luò)的覆蓋范圍、拓?fù)浣Y(jié)構(gòu)都會(huì)相應(yīng)地產(chǎn)生變化。而覆蓋范圍和拓?fù)浣Y(jié)構(gòu)的變化可以引發(fā)節(jié)點(diǎn)能耗的變化，同時(shí)避免節(jié)點(diǎn)間的通信干擾。1.1CONNECT/BICONN算法CONNECT算法與BICONN算法都是功率控制型拓?fù)淇刂扑惴?。它們的目的是降低每一個(gè)節(jié)點(diǎn)的最大發(fā)射功率。即把降低最大發(fā)射功率作為網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是否被優(yōu)化的衡量標(biāo)準(zhǔn)。[7]CONNECT算法的描述如下：第一步：網(wǎng)絡(luò)當(dāng)中只包含了節(jié)點(diǎn)而沒有包含節(jié)點(diǎn)間的連線。這樣一來，節(jié)點(diǎn)本身就是連通分量。第二步：把節(jié)點(diǎn)間距進(jìn)行非遞減排序，根據(jù)這個(gè)排序來選擇網(wǎng)絡(luò)當(dāng)中的每一條邊，這個(gè)順序也意味著節(jié)點(diǎn)的發(fā)射功率是在慢慢變大的。在連接被選擇的邊的時(shí)候若是這條邊可以連接幾個(gè)不同的節(jié)點(diǎn)也就是連接分量那么這幾個(gè)連接分量可以合并成為一個(gè)連接分量；若是在連接時(shí)這條邊連接了相同的連通分量，那么這條邊可以被舍棄。隨著邊一條條的加入，回路逐漸產(chǎn)生了。隨著回路的增多，網(wǎng)絡(luò)當(dāng)中的連通分量的個(gè)數(shù)在逐漸減小，直到連通分量上連著所有的節(jié)點(diǎn)。第三步：把沒加入網(wǎng)絡(luò)的節(jié)點(diǎn)對(duì)間的邊定義為副作用邊。通過調(diào)整副作用邊可以減少節(jié)點(diǎn)的發(fā)送功率。BICONN算法通過使用貪婪技術(shù)把1連通的網(wǎng)絡(luò)修改成2連通的網(wǎng)絡(luò)，這與CONNECT算法相似。BICONN算法的數(shù)學(xué)表述如下：當(dāng)要求的連通度是的時(shí)候,無線網(wǎng)絡(luò)用來表示；傳感器節(jié)點(diǎn)的集合用來表示；代表了到水平面的映射。在通信距離為時(shí),所需要的最小的功率用來表示。每個(gè)節(jié)點(diǎn)達(dá)到最小的發(fā)射功率的范圍為，最后導(dǎo)出的圖就是圖，它是一個(gè)連通圖,并且的值最小，也就是最大發(fā)射功率的最小化操作。當(dāng)要求的連通度是的時(shí)候,最小的功率函數(shù)用來表示，發(fā)射一個(gè)功率為的節(jié)點(diǎn)要求，這樣導(dǎo)出來的圖就是一個(gè)連通圖，而增加一個(gè)，使使得導(dǎo)出的圖形是2連通的圖形，并且的值也是最小的。分析：CONNECT算法與BICONN算法這兩個(gè)算法都是集中式的算法。集中式算法看重的是最小化最大發(fā)射功率。這就需要許許多多的信息例如網(wǎng)絡(luò)拓?fù)涞慕Y(jié)構(gòu)、每一條鏈路的狀態(tài)變化以及每一個(gè)節(jié)點(diǎn)所在的位置。因?yàn)樾枰绱硕嗟男畔⒑陀?jì)算，CONNECT算法和BICONN算法是不適合大規(guī)模的無線傳感器網(wǎng)絡(luò)。1.2AP算法AP算法（AffinityPropagationalgorithm）是一種并不需要有人監(jiān)督就可以運(yùn)作的效率較高且規(guī)模較大的數(shù)據(jù)聚類算法。AP算法適用于處理龐大的數(shù)據(jù)量。AP算法當(dāng)中應(yīng)用了近鄰信息傳播的思想，能夠找到最好的聚類中心的集合，這使所有的節(jié)點(diǎn)到聚類中心的相似程度的和是最大的。算法通過把所有節(jié)點(diǎn)都擬定成為聚類中心，再通過這些節(jié)點(diǎn)的相似度矩陣來計(jì)算這些節(jié)點(diǎn)的責(zé)任性與可用性。在經(jīng)歷了一次次的迭代過程之后，有一組節(jié)點(diǎn)成為了聚類中心。在AP算法之中，樣本和樣本之間的相似度用來表示。它代表了樣本適合成為樣本的聚類中心的程度。通過公式3-3我們可以計(jì)算相似度矩陣。（3-3）如果，意味著樣本成為樣本聚類中心的概率大小，的值越大，樣本成為樣本聚類中心的機(jī)會(huì)也就越大；如果，相似度矩陣被稱為偏向參數(shù)。在AP算法中我們通常把樣本偏向參數(shù)設(shè)置為相同的數(shù)值。設(shè)定的偏向參數(shù)越大，那么樣本當(dāng)選聚類中心的可能也就越大，最后經(jīng)過算法而生成的聚類中心的數(shù)目也就越多。反之，設(shè)定的偏向參數(shù)越小，樣本當(dāng)選聚類中心的可能也就越小，經(jīng)過算法計(jì)算之后當(dāng)選的聚類中心的數(shù)量也就越少。所以，偏向參數(shù)是可以決定經(jīng)過算法產(chǎn)生的聚類中心數(shù)目的多少的。通過改變的大小，聚類中心的數(shù)目也就隨之變化，以此來滿足不同的任務(wù)所提出的需求。AP算法中傳播的是樣本之間的責(zé)任性與可用性。其中：是樣本與樣本的責(zé)任性，它代表了樣本擔(dān)任樣本的聚類中心是否合適以及合適程度的深淺。代表了樣本與樣本之間的可用性，可用性意味著樣本把樣本當(dāng)作聚類中心的合適度。AP算法一步步聚類的過程實(shí)際上也是責(zé)任性與可用性一次次迭代更新的過程，AP算法責(zé)任性與可用性的公式如下所示：（3-4）（3-5）根據(jù)公式3-6我們可以計(jì)算樣本本身的可用性大小。（3-6）AP算法判斷樣本擔(dān)任聚類中心的可能的依據(jù)是通過計(jì)算的責(zé)任性與可用性的和。若是和越大那么樣本也就越可能成為聚類中心；反之則樣本越不可能成為聚類中心。在經(jīng)過一次次的更新迭代之后，AP算法的責(zé)任性與可用性逐漸穩(wěn)定。在更新結(jié)束以后，樣本與所有其它樣本中使得值最大的那個(gè)樣本進(jìn)行比較。若是，那么樣本就是聚類中心；而若，那么樣本就是聚類中心。AP算法的步驟如下所示：（1）初始化根據(jù)各個(gè)樣本點(diǎn)的位置，我們通過公式3-3來計(jì)算樣本間的相似度，定義AP算法的偏向參數(shù)的數(shù)值，要求小于0。將責(zé)任性與可用性初始化。把責(zé)任性矩陣與可用性矩陣都置0。（2）迭代通過公式3-4與公式3-5來更新責(zé)任性矩陣和可用性矩陣；通過責(zé)任性與可用性，找到聚類中心。（3）確定聚類中心通過計(jì)算，來確定樣本聚類中心的位置。再判斷得到的這些聚類中心的數(shù)量是不是滿足設(shè)定的要求，如果聚類中心的數(shù)量滿足要求，那么聚類中心就可以確認(rèn)下來，算法也就到此為止；若聚類中心的數(shù)量并沒有達(dá)到要求，那么就修改，讓責(zé)任性與可用性再進(jìn)行迭代，一直到聚類中心的數(shù)目滿足了要求為止。AP算法的流程圖如圖3-1所示。圖3-1AP算法流程AP算法有如下幾個(gè)優(yōu)點(diǎn)：（1）AP算法并沒有對(duì)相似度矩陣產(chǎn)生太高的要求。并沒有要求相似度矩陣要具有某些特定的矩陣的特點(diǎn)。（2）一開始擬定的聚類中心并不是經(jīng)過不斷迭代更新后AP算法產(chǎn)生的那個(gè)聚類中心。在剛開始執(zhí)行算法的時(shí)候，所有樣本點(diǎn)都會(huì)被選成為聚類中心，而在經(jīng)過算法對(duì)于責(zé)任性與可用性的不斷迭代之后，最終的那些聚類中心才是真正的聚類中心的集合。（3）AP算法的誤差平方和與其它算法相比的比較低的。（4）AP算法運(yùn)行的時(shí)間復(fù)雜度比其它算法要低。雖然運(yùn)行AP算法的時(shí)間比較長，但是與其它能夠達(dá)到同樣效果的聚類算法相比，其它算法需要的運(yùn)行次數(shù)則明顯比AP算法要高。這樣看來，在時(shí)間復(fù)雜度這一方面，AP算法是比較優(yōu)秀的。（5）AP算法的穩(wěn)定性更加優(yōu)秀。若偏