基于無線網橋特定模型下的二次覆蓋問題

李奕航

摘 要 目前，海事通信信息中心為了實現網絡的全面覆蓋，也在全轄區范圍內采取建立無線網橋的方式，但目前由于定位問題，在轄區內還存在盲區信號無法覆蓋。無線網橋實現無線傳感網絡的二次覆蓋的優化，對二次覆蓋通信節點的部署確定了一個部署范圍。用幾何證明的方法證明該區域是一個無線網橋二次覆蓋的完備區域，該區域不僅分散了多次覆蓋區域，而且整個網絡的連通度大于等于2，使連通性達到最優。從而使用該方法有效的減少了無線網橋的定位、信息采集的盲區。

關鍵詞 無線網橋 二次覆蓋 通信節點

0引言

無線網橋的應用是實現網路覆蓋的一種基礎應用。為了使無線網橋能夠完成目標監測和信息獲取的任務，必須保證無線網橋節點的部署能有效地覆蓋被監測的區域。因此，我們需要研究無線網橋網絡的覆蓋問題，即根據被監測的區域的分布情況，對傳感器節點的部署進行規劃，保證無線網橋網絡完全覆蓋或以較大概率覆蓋被監測區域。

本文采用的模型中，節點的通信區域是一個以錨節點為圓心，半徑為其通信距離（由節點硬件特性決定）的圓形區域。只有落在該圓形區域內的點，才能被該節點覆蓋。要解決的問題是在滿足覆蓋性要求的前提下，盡可能減少所需節點數，使網絡造價最低。

1特定基本模型

在滿足二次覆蓋要求的前提下，如圖1所示，假設邊長為2a的一個正方形區域APKN需要實現二次覆蓋。在正方形四角上各放置一個錨節點，節點的通信半徑均為a。此時形成四個一次覆蓋區域Ⅰ，Ⅱ，Ⅲ，Ⅳ。在特定模型中，所有節點結構性能均相同，且節點的感知模型為圓形區域感知模型，文獻[1]已證明當通信半徑大于或者等于2倍的節點的通信半徑時，完全覆蓋目標區域的節點集構成的網橋網絡一定是連通網絡，且使得目標區域實現比較完備的二次覆蓋。然而，當通信半徑小于2倍的通信半徑時，不能保證網絡的連通性。

2實現整個模型的二次覆蓋

2.1確定所用節點數

若再用三個節點實現二次覆蓋，則必用一個節點來覆蓋到正方形的兩個頂點，此處設此二頂點為A 、N，由于節點覆蓋半徑為a，可推得節點放置于點C處。同理可設，需另外一節點同時覆蓋A 、P兩個頂點。假設剩余一個節點的擺放位置未知。則三個節點所能覆蓋到的最大面積為S1=€%ia2+€%ia2+€%ia2=2€%ia2，而對正方形實現二次覆蓋的面積為S2=8a2。顯然S1

因此，最少再用四個節點實現二次覆蓋。

2.2確定節點的位置

四個節點在對應的區域內是相互對稱的。因其對稱性，以下只討論一個節點，其余同理可得。設移動節點為X。

2.2.1 確定點F，G

節點在弧BC上移動。

X在弧BC上移動。F，G點為BC弧的三等分點，則△ABG，△ACF為等邊三角形。當節點在弧BF上移動時，因CX>a，所以無法覆蓋到C點。而此節點在Ⅱ區域相對稱的節點也無法覆蓋到點C。X點覆蓋區域的邊界與其在Ⅱ區域的對稱點的覆蓋區域的邊界與一次覆蓋區域Ⅰ、Ⅱ的邊界所形成的區域為一次覆蓋，即未實現二次覆蓋。因此，節點在弧BF上移動是不能實現二次覆蓋。

節點繼續移動。當X移動到點F時，x恰能覆蓋點C。繼續移動到點G時，X恰能覆蓋點B。繼續移動到弧CG上時，因BX>a，所以無法覆蓋到點B。而此節點在Ⅱ區域相對稱的節點也無法覆蓋到點B。綜上，在BC弧上，FG弧是極限邊界弧，在此范圍內的節點能夠實現二次覆蓋。

2.2.2 確定點H

節點在對角線AK上移動。

D為弧BM的中點，E為弧CQ的中點。

H點即為分別以D、E點為圓心的圓的交點。即X若在H點，則D、E在其覆蓋范圍內。

當節點在AH上移動時，因XD>a，所以X在AK上移動不能覆蓋到D點。其在Ⅳ區域的對稱節點所覆蓋的范圍也不能經過點D。X點覆蓋區域的邊界與其在Ⅱ區域的對稱點的覆蓋區域的邊界與BM弧所圍成的區域沒有實現二次覆蓋。因此，節點在弧AH上移動時不能實現二次覆蓋。

H 點繼續沿對角線移動直到FG弧的中點。此點肯定滿足（前面證FG弧時已證）。

再繼續移動因XA>a，則無法覆蓋到頂點A。顯然不符合要求。

2.2.3 確定點I、J

I點是分別以C、E為圓心的圓的交點。

J點是分別以B、D為圓心的圓的交點。

I、J是關于AK的對稱點。所以以下只討論點I。

（1）節點沿以E為圓心的圓上移動

當節點在HI弧間移動時，節點覆蓋范圍必經過點E。與邊AN的交點在CN間。與DM弧的交點在DM弧間。則節點在HI弧間移動時可以覆蓋C、D兩點。

節點繼續從H點向順時針方向移動時，節點覆蓋范圍與BM弧的交點在BD弧內。無法覆蓋到點D。

節點繼續從I點向逆時針方向移動時，節點覆蓋范圍與AN邊的交點在AC邊上。無法覆蓋到點C。其在Ⅱ區域內對稱的節點也無法覆蓋到點C。無法實現二次覆蓋的區域在證點H 時已經說明。

綜上，HI弧為極限弧，弧上的點符合。

（2） 節點沿以C為圓心的圓上移動

節點在IF弧內移動時，能同時覆蓋A、C、E。

節點繼續從I點向順時針方向移動時，節點覆蓋范圍與弧CQ的交點在CE內，無法覆蓋到點E。其在區域Ⅱ內所對應的節點也無法覆蓋到點D。則此時，兩節點的覆蓋范圍相交部分的邊界弧與CQ弧所圍成的區域沒有實現二次覆蓋。

綜上所述，HIFGJ弧所圍成的范圍即為節點能實現二次覆蓋的范圍。在此范圍內的任取一個節點，且在Ⅱ，Ⅲ，Ⅳ區域所對應的范圍內分別取其對應節點，所取的四個節點同時作用，即能實現二次覆蓋。

3二次覆蓋的應用

本文研究的是在一個特定的正方形區域內的二次覆蓋問題。當研究區域延伸到正方形的周圍空間時，實現二次覆蓋所需最少節點數也將會隨之變化。

如圖2，是一個3的正方形區域，中心區域Ⅰ是文中研究的特定區域。區域Ⅱ、Ⅲ，Ⅳ，Ⅴ分別關于區域Ⅰ對稱，故以下只研究區域Ⅱ，剩余的三個區域同理可得。

由圖1的結論，易推得圖2中，區域Ⅰ與區域Ⅱ有一條公共邊AN，其上有兩個公共節點A、N，容易推出，對于區域Ⅱ，只需6個節點，便可實現二次覆蓋。區域Ⅲ，Ⅳ，Ⅴ同理。

對于區域Ⅵ，Ⅶ，Ⅷ，Ⅸ，也分別關于區域Ⅰ對稱，同理，此處我們討論區域Ⅵ，易知區域Ⅵ與區域Ⅱ、Ⅲ分別各有一條公共邊，也就是共有三個公共點，所以，對于區域Ⅵ，實現二次覆蓋只需5個節點，區域Ⅶ、Ⅷ、Ⅸ同理。

當向更大區域擴展時，可將一個區域視為中心，除去公共節點的個數，然后可推斷出所需最小節點的個數。

當區域范圍為n€譶時，可得出結論，如圖3當在以區域Ⅰ為中心的十字區域時，即與區域Ⅰ同在一條橫軸和豎軸上的區域，所需節點數為6個，剩下的區域所需節點數均為5個。

以實現更大空間區域的二次覆蓋為基礎，從而擴展到用最少的節點數實現空間范圍的三次覆蓋問題將是我們研究的前景。

4總結

無線網橋網絡的覆蓋是無線網絡應用的基礎表現。作為一種全新的信息獲取和處理技術，它可在很多應用在海事通信領域領域實現復雜的大規模監測和跟蹤服務。尤其是在，其應用環境通常是由價格便宜的網橋節點組成的，每個節點都能夠采集、存儲和處理環境信息，并且能和鄰居節點通過無線鏈路保持通信。本文闡述了在確保節點連通性要求條件下，利用最少節點數實現特定區域的二次覆蓋，并詳細計算和證明出節點的布置區域。理論和算法的結合是實現二次覆蓋的必要條件。

參考文獻

[1] WANG Bang，WANG Wei，SRINIVANSAN V，et al.Information coverage for woreless sensor networks[J].IEEE Communications Letters，2005，9（11）：967-969.

[2] ZOU Yi，CHAKRABARTY K.A distributed coverage and connectivity-centric technique for selecting active nodes in wireless sensor networks[J].IEEE Trans on Computers，2005，54（8）：978-991.

[3] MIHAELA C，WU Jie.Energy-efficient coverage problems in wireless Ad hoc sensor networks[J].Computer Communications，2006，29（4）：413-420.