混合網(wǎng)絡(luò)中基于約束的信宿計算方法

張 潔

(福建農(nóng)業(yè)職業(yè)技術(shù)學(xué)院，福建福州 350007)

傳感網(wǎng)作為集計算機技術(shù)與通信技術(shù)于一體的混合型網(wǎng)絡(luò)[1]，在檢測服務(wù)質(zhì)量(QoS)方面發(fā)揮了不可比擬的優(yōu)勢，深受業(yè)界的歡迎，同時也在學(xué)術(shù)界引起了眾多關(guān)于在混合型網(wǎng)絡(luò)中實施異常服務(wù)計算的思考。常見的計算策略基于非測距計算機制。該機制借助通信節(jié)點彼此的關(guān)聯(lián)度[2]來傳遞節(jié)點間的數(shù)據(jù)包，然后運用分布式計算方法近似地計算出異常信宿所在的坐標(biāo)信息。但是該方案對節(jié)點類型的規(guī)模以及混合網(wǎng)絡(luò)的拓?fù)渚哂休^高的依賴性。比如，計算待測目標(biāo)坐標(biāo)時要求目標(biāo)必須處于已知節(jié)點的廣播半徑內(nèi)。這樣的研究應(yīng)用實際上是在對已知節(jié)點的規(guī)模提出要求。然而實際應(yīng)用中的混合網(wǎng)絡(luò)出于成本和布局因素考慮，往往存在已知節(jié)點較為稀疏的現(xiàn)象。這種現(xiàn)狀顯然無法為傳統(tǒng)算法的實施提供特定環(huán)境。基于上述傳統(tǒng)算法的適用性，本文提出一種基于約束的信宿計算方法。

1 傳統(tǒng)算法的局限性

傳統(tǒng)研究在計算QoS異常的信宿時，多數(shù)依賴于大規(guī)模已知節(jié)點所布局的幾何網(wǎng)絡(luò)區(qū)域。運用數(shù)學(xué)方法為所圍建的幾何區(qū)域進(jìn)行建模[3]，然后展開幾何中心的計算。首先，由足夠數(shù)量的已知節(jié)點包圍住一個QoS異常的目標(biāo)信宿節(jié)點，建立一個封閉式網(wǎng)絡(luò)。然后由這些已知節(jié)點廣播自身信息域給目標(biāo)信宿，接著計算出封閉式幾何網(wǎng)絡(luò)的中心坐標(biāo)，作為目標(biāo)信宿的測量值。

但在目標(biāo)信宿通信半徑范圍內(nèi)分布有大量已知節(jié)點的情形下，可知該目標(biāo)信宿完全有可能位于這些已知節(jié)點廣播通信的重合區(qū)域。傳統(tǒng)的算法在對這樣情形下的目標(biāo)信宿展開計算時，往往是以附近已知節(jié)點所構(gòu)建的封閉式幾何網(wǎng)絡(luò)為框架計算幾何網(wǎng)絡(luò)的中心坐標(biāo)。而事實上并非全部的幾何中心坐標(biāo)都會剛好處在這個重合的區(qū)域。

2 基于約束的計算思想

為了改進(jìn)傳統(tǒng)算法在計算精度上的不足，基于約束的計算方法實施于應(yīng)用型融合網(wǎng)絡(luò)中必須要將目標(biāo)信宿通信半徑范圍之外的已知節(jié)點相關(guān)數(shù)據(jù)納入算法計算的范圍。令目標(biāo)信宿的實際坐標(biāo)為G(XGS,YGS)、測算坐標(biāo)為G(XGE,YGE)，目標(biāo)信宿通信范圍R里面的已知節(jié)點i實際坐標(biāo)為(Xi,Yi)，目標(biāo)信宿通信范圍里面的已知節(jié)點O實際坐標(biāo)為(XO,YO)。則目標(biāo)信宿滿足下列條件：

(2.1)

同時可根據(jù)式(2.2)求得測算坐標(biāo)：

(2.2)

將目標(biāo)信宿通信范圍之外的已知節(jié)點到某個節(jié)點的間距超過R時的數(shù)量規(guī)模，與那些目標(biāo)信宿通信范圍以內(nèi)的已知節(jié)點到某個節(jié)點的間距小于R時的數(shù)量規(guī)模，進(jìn)行相加后再除以全局已知節(jié)點的數(shù)量規(guī)模，如果達(dá)到了預(yù)置門限值，則基于約束的計算方法認(rèn)為該方位的附近有一個值得考慮的目標(biāo)信宿測量值。

在開展約束計算時，首先要選取出距離目標(biāo)信宿最近的已知節(jié)點，再分布式計算出該已知節(jié)點周圍存在的多個值得考慮的目標(biāo)信宿測量值，然后確定一個最優(yōu)測量值[4]。每一次對不同的待測面積展開計算時均設(shè)置不同的門限條件值。按照待測網(wǎng)絡(luò)面積從小到大依次設(shè)置門限為0.9、0.8和0.7。首次計算時，與目標(biāo)信宿間距最短的已知節(jié)點作為幾何中心，構(gòu)建出一個正方形待測區(qū)域，區(qū)域邊緣的周長均為半徑的兩倍。然后將該正方形四等分，估算每個正方形的幾何中心值附近是否存在一個值得考慮的目標(biāo)信宿測量值。如果存在，對該小正方形進(jìn)行二次計算。計算前仍然進(jìn)行四等分，然后估算每個小小正方形的幾何中心是否存在一個值得考慮的目標(biāo)信宿測量值。如果存在，則繼續(xù)進(jìn)行類似的計算[5]。最終將所分析出來的值得考慮的測量值的數(shù)量S，通過函數(shù)(2.3)計算出所有測量方位值形成的封閉式網(wǎng)絡(luò)的幾何中心，作為目標(biāo)信宿最優(yōu)方位測量值G(XGE,YGE)。

(2.3)

3 基于約束的計算實施

結(jié)合基于約束的計算思想，按照如下步驟分布式實施目標(biāo)信宿計算：首先，在待測混合網(wǎng)絡(luò)區(qū)域內(nèi)由已知節(jié)點向全局發(fā)起廣播[6]，所廣播的信息域包含已知節(jié)點方位數(shù)據(jù)，以及已知節(jié)點與目標(biāo)信宿之間的間距數(shù)據(jù)。其次，遍歷出與目標(biāo)信宿間距最短的那個已知節(jié)點，并以該已知節(jié)點方位為中心，規(guī)劃出兩倍半徑的邊緣作為正方形其中的一條邊長，構(gòu)建出八位半徑周長的正方形區(qū)域。然后，將該正方形四條區(qū)域邊緣的中點連線，刮分出四個小正方形。再估算出每個小正方形幾何中心處附近的那個相對可信的目標(biāo)信宿測量值。以此類推，連續(xù)展開三次計算，得到多個相對可信的目標(biāo)信宿測量值。最后，對這多個相對可信的目標(biāo)信宿測量值做加權(quán)處理[7]，進(jìn)而求出目標(biāo)信宿最優(yōu)方位解。

4 實驗分析

4.1 實驗?zāi)Ｐ?/h3>

在實施約束計算之前，先構(gòu)建如下測試模型[8]：(1)創(chuàng)建一個如圖1所示的100 m×100 m的監(jiān)測區(qū)域作為模擬混合網(wǎng)絡(luò)的環(huán)境，并在該模擬環(huán)境中隨機部署30個方位信息明確的已知節(jié)點和70個普通節(jié)點；(2)通過數(shù)次變化總節(jié)點規(guī)模、已知節(jié)點規(guī)模和通信范圍來考察約束計算對目標(biāo)計算誤差的影響；(3)為了防止部署節(jié)點的偶然性對實驗結(jié)果造成影響，每一次實驗后均重新部署已知節(jié)點和普通節(jié)點的密度；(4)節(jié)點廣播半徑范圍初始化為20 m；(5)為客觀地反映約束算法的性能，實驗在300次仿真后才開始收集數(shù)據(jù)。并根據(jù)數(shù)據(jù)繪制出幾何曲線圖與傳統(tǒng)非測距算法進(jìn)行比較。

圖1 混合網(wǎng)絡(luò)部署示意圖

圖2 總節(jié)點規(guī)模對目標(biāo)計算的影響度

4.2 實驗分析

由于混合網(wǎng)絡(luò)中節(jié)點可為目標(biāo)計算提供有參考價值的信息域[9]，故全局中總節(jié)點規(guī)模數(shù)量的增加勢必使每個正方形檢測區(qū)域內(nèi)節(jié)點的密度也同比增加，這在一定程度上為計算目標(biāo)信宿方位提供了足夠數(shù)量和足夠準(zhǔn)確的參考數(shù)據(jù)。正如圖2所描述的總結(jié)點規(guī)模對目標(biāo)計算的影響度，兩種算法曲線所對應(yīng)的歸一化計算偏差均與總節(jié)點規(guī)模成反比。但相對于傳統(tǒng)算法而言，約束計算方法由于對節(jié)點類型的依賴性相對較輕，因此在本項實驗中表現(xiàn)出了相對優(yōu)勢。

根據(jù)目標(biāo)計算思想可知，計算精度和已知節(jié)點規(guī)模呈正比。因此，任何情形下目標(biāo)計算誤差都將伴隨著已知節(jié)點規(guī)模的增加而線性遞減。這樣的計算特征在圖3所示的曲線走勢圖中得到了驗證。圖3描述了已知節(jié)點規(guī)模對計算目標(biāo)的影響度。由于傳統(tǒng)算法對已知節(jié)點規(guī)模具有較高的偏好度，因此已知節(jié)點規(guī)模較小時傳統(tǒng)算法在計算精度上的劣勢表現(xiàn)較為明顯，即歸一化計算偏差值較高。隨著已知節(jié)點規(guī)模逐漸增加，兩種算法的精度均得到了明顯提升。但約束計算機制下的歸一化計算偏差相對于傳統(tǒng)算法仍占據(jù)絕對優(yōu)勢。

圖3 已知節(jié)點規(guī)模對目標(biāo)計算的影響度

圖4 節(jié)點廣播范圍對目標(biāo)計算的影響度

圖4描述了節(jié)點廣播范圍和目標(biāo)計算精度之間的關(guān)系。隨著廣播半徑范圍從20 m擴(kuò)大至30 m，可用已知節(jié)點數(shù)量相應(yīng)的增加，目標(biāo)信宿獲得的信息域可靠性[10]也相應(yīng)增高。因此兩種算法曲線對應(yīng)的歸一化計算偏差呈現(xiàn)下降趨勢。隨著廣播范圍進(jìn)一步加大，由于約束算法的計算函數(shù)能夠利用廣播半徑擴(kuò)大后新增的已知節(jié)點，使得約束算法在本項考察中體現(xiàn)出優(yōu)勢。

5 結(jié)語

本文通過對傳統(tǒng)計算機制運用在融合網(wǎng)絡(luò)中計算異常目標(biāo)的可行性進(jìn)行分析，提出了一種適應(yīng)性較好的異常信宿計算方法。該方法通過充分利用全局范圍內(nèi)的已知節(jié)點來為異常信宿的計算過程提供可靠信息域，進(jìn)而實施對傳統(tǒng)算法的改善。經(jīng)過測試表明，該算法應(yīng)用在融合網(wǎng)絡(luò)實施計算具備可行性。