【正文】 點中到原點距離最小。根據(jù)以上結(jié)論可知，位于該原始節(jié)點x軸正方向相鄰點S(1,0)=（x0+Rc,y0），而位于該原始節(jié)點y軸正方向相鄰行的第一個傳感節(jié)點S(0,1)=(x0+Rc/2,y0+), S(2,2)=( )，同理可計算出該二維坐標(biāo)系內(nèi)按以上布署算法的任意節(jié)點的分布位置（注意：對于奇、偶行有區(qū)別）：S(n′,2n)=（ ）, （）S(n′,2n+1) =（） （）其中n’=(0,1,2…∞), n=(0,1,2…∞)。 當(dāng)然，以上推導(dǎo)出任意點表達(dá)式會隨著設(shè)定不同的原始節(jié)點而改變。而在具體分析特殊區(qū)域時，可靈活圍繞區(qū)域的不同形狀建立二維坐標(biāo)系。另一方面，上文所述的聯(lián)通性僅僅局限于一行中相鄰傳感節(jié)點之間的數(shù)據(jù)交換，后續(xù)部分將針對特殊區(qū)域討論到如何保證整個區(qū)域傳感網(wǎng)絡(luò)的聯(lián)通性。設(shè)帶有邊界障礙的特殊區(qū)域。，會造成一部分區(qū)域無法覆蓋。，但為了保證相鄰節(jié)點的通信不被障礙所阻隔，有多余的節(jié)點被附加在了邊界的轉(zhuǎn)角上，這樣無疑造成了傳感器浪費(fèi)。對于此類區(qū)域的布點可在上文研究基礎(chǔ)上加以改進(jìn)，：當(dāng)未覆蓋區(qū)域?qū)挾龋襌c≤Rs時：可將節(jié)點與邊界距離設(shè)置為，兩相鄰節(jié)點間距為Rc。當(dāng)未覆蓋區(qū)域?qū)挾?，且Rc＞Rs時：可將節(jié)點與邊界距離設(shè)置為，兩相鄰節(jié)點間距為Rs?？蓾M足覆蓋性和聯(lián)通性。當(dāng)未覆蓋區(qū)域?qū)挾龋緯r，無論Rc、Rs關(guān)系如何，按上文中大型區(qū)域方式處理。這樣，即可在要求最少節(jié)點的情況下，同時滿足對該區(qū)域的覆蓋性和相鄰節(jié)點之間的聯(lián)通性。 生成未覆蓋區(qū)域 沿邊界部署產(chǎn)生大量冗余節(jié)點 優(yōu)化部署策略然而，僅滿足每行相鄰節(jié)點間的聯(lián)通性，無法使該區(qū)域當(dāng)中所有節(jié)點形成完整自組織網(wǎng)絡(luò)。本文采用EMST（歐幾里德最小生成樹）[12,13]算法估計最遠(yuǎn)邊界的通信連接，并結(jié)合幾何分析，解決整個網(wǎng)絡(luò)的聯(lián)通問題。設(shè)在區(qū)域T中，有任意節(jié)點S能與該T范圍內(nèi)某一個枝葉節(jié)點進(jìn)行通信。設(shè)C為T內(nèi)所有{S}的集合，記作：C←{S}；設(shè)一變量K=0，K→K+1。設(shè)任意，記作以為圓心，Rc為半徑的理想通信圓周范圍。移動任意以C子集點為圓心的理想圓周。設(shè)為圓周與該區(qū)域T邊界的相交點。而對于任意的，同時，且滿足。則起始點（圓周的圓心點）到（與邊界T的交點）所構(gòu)成的直線路徑將完全被通信范圍所覆蓋。具體路徑的布點可以看作幾何問題進(jìn)行分析，兩行節(jié)點之間直線距離為，根據(jù)平行四邊形原理，兩條對角線dd2分別為：d1= ； （）d2= ； （）根據(jù)特殊區(qū)域形狀，擇優(yōu)選取對角線，得出應(yīng)補(bǔ)充的傳感器點數(shù)或，按對角線上的等分點布署。綜上所述，行與行之間的通信路徑建立，傳感器節(jié)點能保證整個網(wǎng)絡(luò)的聯(lián)通性。 歐幾里德最小生成樹節(jié)點 優(yōu)化部署算法仿真及性能分析針對以上所提出的優(yōu)化部署算法，在Matlab仿真軟件中模擬，評估其性能。為了證明優(yōu)化布點算法的有效性，文中基于MATLAB分別對兩處不同形狀的區(qū)域進(jìn)行布點仿真。，為了模擬礦井下各種復(fù)雜的地形區(qū)域及在開采巷道內(nèi)可能出現(xiàn)的物理障礙，文中所給出的部署環(huán)境，不僅包括簡單典型的方形區(qū)域，而且將囊括了任意圖形作為邊界或障礙的復(fù)雜區(qū)域圖形作為仿真對象，充分證明該優(yōu)化部署算法的有效性。在仿真過程中，分別設(shè)(Rc,Rs)=(4,6)。 (5,5)。 (6,4)。 (8,4)個單位，以滿足上述四種不同關(guān)系RsRc。 Rs=Rc。 RsRcRs。 Rc Rs。并將在該區(qū)域下，采用不同算法確保覆蓋性和聯(lián)通性的具體布點數(shù)量作為比較標(biāo)量，來反映該優(yōu)化算法的有效性?；ハ鄬Ρ鹊乃姆N算法依次有：本文提出的優(yōu)化部署算法；前文提到的以覆蓋為標(biāo)準(zhǔn)的算法、以連通為標(biāo)準(zhǔn)的算法、格點算法。 簡單10085的矩形區(qū)域 復(fù)雜區(qū)域 ，：在Rc,Rs的不同關(guān)系下，采用上述四種不同的部署策略需要使用的具體點數(shù)。因為在格點算法中，所有的相鄰節(jié)點間隔都是以Rc,Rs中的最小值為標(biāo)準(zhǔn)，因此所需要的點數(shù)在任意情況下最多。而當(dāng)RsRc時，由于以連通性為標(biāo)準(zhǔn)的算法要求水平相鄰節(jié)點間的間隔為Rc，使已滿足覆蓋性的區(qū)域重復(fù)布點，造成了節(jié)點的浪費(fèi)。相反，當(dāng)RsRcRs時，以覆蓋為標(biāo)準(zhǔn)的算法補(bǔ)充了大量的多余節(jié)點，以滿足局部區(qū)域（如：轉(zhuǎn)角，弧形區(qū)）的通信連接，消耗的節(jié)點數(shù)僅次于格點算法。而當(dāng)Rc Rs時，由于節(jié)點具有足夠的通信距離，所以以覆蓋為標(biāo)準(zhǔn)的布點算法達(dá)到的效果和本文中的優(yōu)化布點算法相同。綜上所述，本文提出的優(yōu)化布點算法能在任意Rc,Rs關(guān)系下，消耗最少量的節(jié)點，并同時滿足特殊區(qū)域的覆蓋性和連通性。 在10085的矩形區(qū)域消耗的傳感器節(jié)點數(shù) 復(fù)雜區(qū)域消耗的傳感器節(jié)點數(shù) 本章小結(jié)本章首先就無線傳感器網(wǎng)絡(luò)在礦井安全監(jiān)測系統(tǒng)中的應(yīng)用做了初步介紹，并給出了安監(jiān)系統(tǒng)網(wǎng)絡(luò)的體系結(jié)構(gòu)總體設(shè)計。根據(jù)礦井下環(huán)境的特點，給出了優(yōu)化的部署策略，設(shè)計了無線傳感器網(wǎng)絡(luò)的基本拓?fù)浣Y(jié)構(gòu)。第4章 礦井下無線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴ㄑ芯考词股鲜龅膬?yōu)化部署算法可滿足無線傳感器網(wǎng)絡(luò)對礦井監(jiān)測區(qū)域的連通性與覆蓋性要求，然而隨著監(jiān)測時間的推移，傳感器節(jié)點可能產(chǎn)生故障、能量耗盡以及遭到惡意破壞等問題，一些節(jié)點將會失效。失效的傳感器節(jié)點將造成監(jiān)測區(qū)域中的某些監(jiān)測盲區(qū)或通信盲區(qū)。使得網(wǎng)絡(luò)無法滿足礦井安全監(jiān)測系統(tǒng)的要求。當(dāng)節(jié)點按基于位置信息的方式部署后，一旦出現(xiàn)網(wǎng)絡(luò)監(jiān)測盲區(qū)，將通過冗余的生存節(jié)點移動并代替死亡節(jié)點的方式來彌補(bǔ)。一般來說，采取集中式的虛擬力量[14～16]對移動節(jié)點進(jìn)行控制、并結(jié)合分析潛在區(qū)域內(nèi)可用鄰節(jié)點定位的方法來處理盲區(qū)。 SMART掃描算法在基于掃描的SMART[17,18]算法中，傳感器節(jié)點被部署為的二維陣列，算法對行、列分別進(jìn)行掃描，在掃描過程中，下一節(jié)點對各自的上一單跳鄰節(jié)點傳來的掃描數(shù)據(jù)加1，繼續(xù)傳給下一單跳鄰節(jié)點。匯聚節(jié)點統(tǒng)計各行、列掃描數(shù)據(jù)的最終結(jié)果并計算節(jié)點在監(jiān)測區(qū)域的覆蓋密度情況，然后廣播消息通知處于密度高的節(jié)點移動到覆蓋密度低的監(jiān)測區(qū)域。經(jīng)過一輪調(diào)整，繼續(xù)循環(huán)掃描，統(tǒng)計，移動的進(jìn)程。只到陣列中的行列掃描數(shù)據(jù)中各行列差值達(dá)到最小。但這種檢測方式和移動算法在規(guī)模較大的節(jié)點陣列中可靠性不高，而且在掃描輪數(shù)增大的情況下，節(jié)點能量消耗過多也是該算法的缺陷之一。014533125543911754787552532圖 初始部署數(shù)據(jù)2233366665777776766643433圖 經(jīng)過行掃描后的移動數(shù)據(jù)5555555655555555555555554 經(jīng)過列掃描后的移動數(shù)據(jù) Hungarian算法在Hungarian算法中，將每個節(jié)點通信范圍內(nèi)的所有節(jié)點之和定義為該節(jié)點的邊界權(quán)重，其中m為該節(jié)點的單跳鄰節(jié)點數(shù)。在利用Hungarian算法進(jìn)行節(jié)點移動過程中。首先將SMART算法中的二維傳感器陣列圖轉(zhuǎn)換成配對圖表。在進(jìn)行掃描后，確定好該區(qū)域的最終平均節(jié)點分布密度，分別以“給予”和“獲取”的形式將定義格點。格點權(quán)重為超過或低于平均密度的程度，邊界權(quán)重作為判斷與其配對的格點之間的數(shù)量差。，調(diào)整格點內(nèi)的節(jié)點密度。但是，一般情況下，格點內(nèi)的節(jié)點計算數(shù)量最終將比實際量要多。 格點權(quán)重、邊緣權(quán)重配對圖表 二維網(wǎng)孔下的局部Hungarian算法在Hungarian局部算法[19～21]中，每一個格點通過向鄰節(jié)點發(fā)送邀請消息進(jìn)行初始配對，邀請信息中包含當(dāng)前格點內(nèi)節(jié)點數(shù)與監(jiān)測區(qū)域內(nèi)格點中的平均節(jié)點數(shù)差值，以及預(yù)先定義的差值傳輸范圍。如果“給予”型格點獲得的邀請信息不屬于“獲取”型格點，將轉(zhuǎn)發(fā)該數(shù)據(jù)。當(dāng)“獲取”型格點獲得邀請信息時，將回復(fù)該信息或轉(zhuǎn)發(fā)，返回其差值數(shù)據(jù)。得到返回的消息后，“給予”型格點將往“獲取”型格點內(nèi)遣出節(jié)點。當(dāng)“給予”型節(jié)點發(fā)送 邀請信息時，其可發(fā)送范圍是可調(diào)的。首先，將在小范圍內(nèi)向鄰格點發(fā)送該邀請。如無回復(fù)請求，將擴(kuò)大發(fā)送范圍以搜尋“獲取”型格點。這一步驟和自組織網(wǎng)絡(luò)中通過逐步擴(kuò)大搜集圈來獲取單跳節(jié)點類似。如果“獲取”型獲得來自不同格點的邀請信息，將選擇位置最靠近的格點。除非當(dāng)所選擇的格點無法貢獻(xiàn)出足夠多的節(jié)點時，才會同時響應(yīng)多個邀請信息。而當(dāng)“給予”型同時獲得多個回復(fù)消息時，將通過節(jié)點差值來判斷，越小的差值優(yōu)先級越高。 Hungarian局部算法基本流程圖 網(wǎng)絡(luò)節(jié)點自移動的拓?fù)淇刂茀f(xié)議在可移動節(jié)點的無線傳感器網(wǎng)絡(luò)中，鄰居節(jié)點并不是確定的，僅僅依靠當(dāng)前網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)來組網(wǎng)并不可靠，因為拓?fù)浣Y(jié)構(gòu)可能會迅速發(fā)生變化。一般情況下，和自組織網(wǎng)絡(luò)類似，網(wǎng)絡(luò)中的傳感器節(jié)點由上層協(xié)議所提供的無線廣播來發(fā)現(xiàn)鄰節(jié)點，但并不重視發(fā)現(xiàn)的具體是網(wǎng)絡(luò)中的哪個節(jié)點。如在AODV,DSR和ZRP[22～24]路由協(xié)議中，都假設(shè)所有鄰節(jié)點在持續(xù)偵聽信道。這種工作方式能很好的發(fā)現(xiàn)潛在的鄰節(jié)點，但能效利用率偏低。目前在拓?fù)淇刂萍夹g(shù)中的鄰節(jié)點發(fā)現(xiàn)算法也采用了分簇協(xié)議，源路由協(xié)議，和歐幾里德最小生成樹等算法。本文中所采用的Birthday[25～28]協(xié)議基于概率，將節(jié)點分時隙進(jìn)行偵聽、空閑、傳輸，發(fā)現(xiàn)可通信范圍內(nèi)的潛在鄰節(jié)點，不僅能快速發(fā)現(xiàn)節(jié)點并連接網(wǎng)絡(luò)，也大大優(yōu)化了節(jié)點的能量消耗。任意網(wǎng)絡(luò)中的移動節(jié)點在每個時隙中具備三個狀態(tài)。當(dāng)X節(jié)點發(fā)現(xiàn)Y節(jié)點時，Y在傳輸態(tài)，X必須處于偵聽?wèi)B(tài)。在一個時隙中，此種情況概率為。X在整個時隙中發(fā)現(xiàn)Y的概率為。而Y發(fā)現(xiàn)X的概率也相同。若考慮其為獨(dú)立事件，則網(wǎng)絡(luò)中可預(yù)期的連接數(shù)為： （）當(dāng)考慮到越來越多的節(jié)點接入網(wǎng)絡(luò)，每個節(jié)點在部署檢測鄰節(jié)點時，有可調(diào)整的概率處于發(fā)送狀態(tài)，不可避免導(dǎo)致在信道的沖突問題。Birthday協(xié)議提供了解決方案。當(dāng)隨即變量T，L和S在任意時隙分配，假設(shè)在分配時看成是每個節(jié)點的獨(dú)立事件，每個節(jié)點在不同時隙內(nèi)有三個不同結(jié)果： （）只有在其余個鄰節(jié)點處于發(fā)送狀態(tài)，而X節(jié)點處于偵聽狀態(tài)時，X節(jié)點可檢測到其他鄰節(jié)點。其中的每一個節(jié)點間連接概率： （）而對于節(jié)點X可監(jiān)聽到的總概率為： （）轉(zhuǎn)換后，可得： （）如果節(jié)點數(shù)N足夠大，節(jié)點間在雙向偵聽的情況下，大致符合Poisson分布，系數(shù)?。? （）因此，網(wǎng)絡(luò)內(nèi)的雙向節(jié)點連接數(shù)為： （） 網(wǎng)絡(luò)盲區(qū)“自愈”拓?fù)淇刂扑惴ū疚幕谧顑?yōu)部署算法提出了一種具有“自愈”功能的路由協(xié)議來彌補(bǔ)網(wǎng)絡(luò)中出現(xiàn)的盲區(qū)。首先，假設(shè)在監(jiān)測網(wǎng)絡(luò)中每個傳感器節(jié)點都具有移動能力，節(jié)點可通過上述Birthday協(xié)議獲取其相鄰節(jié)點的位置信息。當(dāng)某些節(jié)點失效后，所有相鄰節(jié)點無法收到上述Birthday協(xié)議所反饋的數(shù)據(jù)包，因此認(rèn)為該節(jié)點已死亡。然后，所有該死亡節(jié)點的鄰節(jié)點通過廣播包含自己位置信息的數(shù)據(jù)包給下一跳節(jié)點，其他節(jié)點收到該位置信息后繼續(xù)轉(zhuǎn)發(fā)給下一跳節(jié)點，如此直到所有節(jié)點都能獲取并定位出該死亡節(jié)點的位置信息。通過上述的優(yōu)化部署算法可知，為了能滿足整個網(wǎng)絡(luò)的覆蓋性和連通性，難免會出現(xiàn)一些節(jié)點的實際覆蓋范圍小于其所能覆蓋到的真實范圍，如一些鄰近邊界或障礙物的傳感節(jié)點。在移動策略中，該類節(jié)點將被充分利用來彌補(bǔ)由于失效節(jié)點所導(dǎo)致的網(wǎng)絡(luò)盲區(qū)。因此，根據(jù)Rc與Rs之間不同的數(shù)量關(guān)系，將鄰近監(jiān)測區(qū)域或障礙物邊界的傳感器節(jié)點分成三種情況討論：當(dāng) Rc Rs時：（1）.節(jié)點距監(jiān)測區(qū)域邊界或障礙物垂直距離：,（2）. 節(jié)點距監(jiān)測區(qū)域邊界或障礙物垂直距離：,（3）. 節(jié)點距監(jiān)測區(qū)域邊界或障礙物垂直距離：.并設(shè)置以上三類處于不同距離的節(jié)點各自不同的移動優(yōu)先級。距離為 的節(jié)點獲得最高的移動優(yōu)先級，節(jié)點處于次之，的節(jié)點最小。當(dāng) Rc Rs時：（1）. 節(jié)點距監(jiān)測區(qū)域邊界或障礙物垂直距離：,（2）. 節(jié)點距監(jiān)測區(qū)域邊界或障礙物垂直距離：,（3）. 節(jié)點距監(jiān)測區(qū)域邊界或障礙物垂直距離：.同上，上述節(jié)點也具有不同的移動優(yōu)先級。情況1至3，優(yōu)先級依次降低。下述對“自愈”路由協(xié)議的證明雖是基于Rc Rs的情況，但當(dāng)Rc Rs時，也可按照相同的策略來移動節(jié)點，達(dá)到網(wǎng)絡(luò)“自愈”目的。當(dāng)處于最高移動優(yōu)先級的節(jié)點收到移動信息時，節(jié)點將通過獲取到的死亡節(jié)點位置信息，計算之間的距離（注：、為最高優(yōu)先級節(jié)點與死亡節(jié)點各自的二維坐標(biāo)值），并通過廣播形式通知其他節(jié)點。由無線電通信能量損耗公式（）可知，通信距離的增加與節(jié)點能量損耗成正比[29,30]。 ()因此，移動策略規(guī)定，在所有具有最高移動優(yōu)先級的節(jié)點中，選取距離最小的節(jié)點。為了避免節(jié)點因為過度的移動造成的能量耗盡，將通過計算路由移動距離來平衡節(jié)點能量的損耗。 X節(jié)點死亡，R節(jié)點獲得最高移動優(yōu)先級當(dāng)可用的并附帶最高移動優(yōu)先級的節(jié)點R被選擇代替圖中死亡節(jié)點X時，R將通過廣播形式通知可用節(jié)點W、S、N，W節(jié)點將被控制并移動至X節(jié)點所在位置，同時R節(jié)點被移動至W節(jié)點原有位置。 移動步驟另一方面，考慮到礦井當(dāng)中復(fù)雜的地形環(huán)境，如果在W節(jié)點移動至X節(jié)點的過程中遇到障礙物，W節(jié)點將反饋信息給R節(jié)點，協(xié)議將控制節(jié)點調(diào)整移動的線路。 改變移動路線在“自愈”協(xié)議中，傳