一種有向傳感器網絡強柵欄覆蓋判定方法
2023-09-21 00:00:10
專利名稱：一種有向傳感器網絡強柵欄覆蓋判定方法
技術領域：
本發明屬於無線通信技術領域，尤其涉及一種有向傳感器網絡強柵欄覆蓋判定方法。
背景技術：
傳感器網絡的覆蓋控制旨在通過各個傳感器節點協作而達到對監視區域的不同管理或感應的效果，它是整個環境監測任務得以有效開展的前提和基礎。作為傳感器網絡覆蓋控制理論的研究熱點之一，柵欄覆蓋(Barrier Coverage)主要研究如何分配網絡時空資源來保證當任意移動目標沿任意路徑穿越監控區域時都能被監測到。這類覆蓋控制問題的目標是找出連接左右邊界的一條或多條路徑，使得這樣的路徑能夠在不同模型定義下提供對移動目標的不同傳感/監視質量。柵欄覆蓋算法研究引起了國內外學者的廣泛關注，並基於傳統的全向感知模型積累了一些理論和算法，廣泛應用於邊界保護、移動目標監控等任務。近幾年來，一些學者開展了有向傳感器網絡柵欄覆蓋控制方面的探索性研究，並陸續在IEEE系列會議發表了數篇前沿的研究成果。具體來講，有向傳感器網絡中節點的感知範圍是以節點為圓心、半徑為其感知距離的扇形區域(例如圖像/視頻、麥克風、紅外、超聲波等傳感器節點)。鑑於視角受限節點的感知特點，即使是分布在同一地理位置上的兩個傳感器節點，也會因其傳感方向的不同而導致對同一目標覆蓋能力上存在很大差異；另外，傳感器網絡通常工作在未知的、複雜的環境下，難以通過人為幹預將眾多傳感器節點放置在適合的位置，導致了網絡節點初始分布的不均勻性，這些都給有向傳感器網絡中柵欄覆蓋控制理論及算法研究帶來了不小的挑戰。根據目標運動軌跡特點，可將柵欄覆蓋分為兩類強柵欄覆蓋(Strong BarrierCoverage)和弱柵欄覆蓋(Weak Barrier Coverage)。強柵欄覆蓋滿足目標以任意軌跡從出發位置運動至目的位置，總能被網絡中至少一個傳感器節點監測到，如圖1(a)所示；而弱柵欄覆蓋則限定目標僅沿直線軌跡從出發位置運動至目的位置，確保每條直線軌跡總能被網絡中至少一個傳感器節點監測到，如圖1(b)所示。在文獻《利用有向傳感器實現強柵欄覆蓋》(「Strong Barrier Coverage withDirectional Sensors」，發表於IEEE GL0BEC0M 2009)中，文中假定每個節點的傳感方向只有q個有限取值，當節點總數為η時，構造有向覆蓋圖G包含O(nq)個頂點，0(q2n2) 條邊，即用頂點表示每個節點所有可能的感知扇形。一旦計算發現兩個扇形之間存在重疊， 就將有向覆蓋圖G中相應兩個頂點之間建立連線。然而，隨著每個節點傳感方向取值q的不斷增加，算法複雜度增長速度會很大。在文獻《旋轉有向傳感器部署及感知方向配置問題〉〉("Placement and Orientationof Rotating Directional Sensors，，發表於國際會議 IEEE SECON 2010)，作者基於動態的持續旋轉感知模型，探索有向傳感網絡中弱柵欄覆蓋問題。基本解決思路在於採用有限離散的方法去解決一個無限連續的NP問題，設計貪心優化算法確定視角受限節點的初始傳感方向以獲得對所有入侵者的最大監測概率，以及部署最少數目的有向節點並確定其初始傳感方向，以使得所有入侵者都被監測到。通過上述文獻可以看出，目前對有向傳感器網絡強柵欄覆蓋的研究還十分有限。 首先，文獻1設定每個有向節點的傳感方向為有限個，這與實際應用相差很遠，實際網絡中的有向節點的傳感方向可能會很多；而且，當文獻1設定的有向節點的傳感方向過多時，其算法複雜度會很大。其次，文獻2中的有向節點感知模型並非動態持續旋轉的，這也不符合傳感器網絡的實際情況；同時，文獻2應用意義在於弱柵欄覆蓋，而不是強柵欄覆蓋
發明內容
本發明的目的在於，提供一種有向傳感器網絡強柵欄覆蓋判定方法，用以解決目前有向傳感器網絡強柵欄覆蓋的研究存在的問題。為實現上述目的，本發明提供的技術方案是，一種有向傳感器網絡強柵欄覆蓋判定方法，有向傳感器網絡由有向傳感器節點、匯聚節點和兩個虛擬邊界節點組成；其中，有向傳感器節點的感知區域是以R為傳感半徑，2 α為感知視角，感知視角的角平分線為中軸線的扇形感知區域，兩個虛擬邊界節點分別用於描述有向傳感器網絡的左邊界和右邊界， 其特徵是所述方法包括步驟1 隨機部署有向傳感器節點，有向傳感器節點通過廣播方式自組織構成有向傳感器網絡；步驟2 匯聚節點為每個有向傳感器節點生成虛擬節點；所述虛擬節點的感知區域是以2 α為感知視角，以R為傳感半徑的扇形區域；步驟3 匯聚節點根據生成的虛擬節點和兩個虛擬邊界節點，構建有向覆蓋連通圖；步驟4:匯聚節點遍歷有向覆蓋連通圖，如果找到一條從一個虛擬邊界節點到另一個虛擬邊界節點的連通路徑，則判定有向傳感器網絡滿足強柵欄覆蓋；否則，判定有向傳感器網絡不滿足強柵欄覆蓋。所述匯聚節點為每個有向傳感器節點生成虛擬節點具體包括步驟21 匯聚節點分別根據左邊界和右邊界與有向傳感器節點的位置關係，建立左邊界節點集Π ！和右邊界節點集Π r ；步驟22 匯聚節點判斷左邊界節點集Π ！和右邊界節點集Π r是否都不為空集，如果是，則執行步驟23 ；否則，結束該過程；步驟23 將每個有向傳感器節點的扇形感知區域擴展為圓形感知區域；步驟24 有向傳感器節點的圓形感知區域與邊界相交形成邊界交點；有向傳感器節點的圓形感知區域與有向傳感器節點的鄰居節點的圓形感知區域相交形成鄰居交點；步驟25 每個有向傳感器節點的扇形傳感區域繞自身旋轉掃視一周，當遇到邊界交點、鄰居交點或者其他有向傳感器節點時，就生成一個虛擬節點。所述步驟21具體是匯聚節點找到距離左邊界不超過傳感半徑R的有向傳感器節點，並將其加入到左邊界節點集Π ！中；並找到距離右邊界不超過傳感半徑R的有向傳感器節點，並將其加入到右邊界節點集Π r中。所述有向傳感器節點的鄰居節點是指與所述有向傳感器節點的距離小於等於傳感半徑兩倍的另一個有向傳感器節點。
所述構建有向覆蓋連通圖具體是，將生成的所有虛擬節點和兩個虛擬邊界節點構成頂點集合，在頂點集合中，當虛擬節點的感知區域覆蓋到左邊界/右邊界時，則在描述左邊界/右邊界的虛擬邊界節點與該虛擬節點之間建立一條邊；當不屬於同一個有向傳感器節點的兩個虛擬節點的感知區域形成覆蓋重疊時，則在這兩個虛擬節點之間建立一條邊。本發明克服了現有判定方法假設簡單、運算量大等在實際應用中的局限性，有效實現有向傳感器網絡強柵欄覆蓋的判定。
圖1是有向傳感器網絡強柵欄覆蓋和弱柵欄覆蓋示意圖，其中，(a)是有向傳感器網絡強柵欄覆蓋示意圖，(b)是有向傳感器網絡弱柵欄覆蓋示意圖；圖2是本發明提供的有向傳感器網絡強柵欄覆蓋判定方法流程圖；圖3是本發明提供的有向傳感器網絡示意圖；圖4是有向傳感器節點方向可調感知模型示意圖；圖5是有向傳感器節點和有向傳感器節點的鄰居節點示意圖；其中，(a)是互為鄰居節點的一對有向傳感器節點通過調整傳感方向，形成重疊傳感區域的示意圖；(b)是互為鄰居節點的一對有向傳感器節點通過調整傳感方向，形成重疊傳感區域的另一種示意圖；圖6是確定有向傳感器網絡左/右邊界節點集的示意圖；圖7是有向傳感器節點擴展為完整的圓形感知區域後的關係示意圖；圖8是有向傳感器節點生成虛擬節點示意圖，其中，(a)是有向傳感器節點的扇形傳感區域繞自身旋轉掃視一周遇到邊界交點生成虛擬節點示意圖，(b)是兩個距離小於等於傳感半徑R的有向傳感器節點中的一個有向傳感器節點的扇形傳感區域繞自身旋轉掃視一周遇到鄰居交點和鄰居節點生成虛擬節點示意圖，(c)是兩個距離大於1倍傳感半徑 R並小於等於2倍傳感半徑R的有向傳感器節點中的一個有向傳感器節點的扇形傳感區域繞自身旋轉掃視一周遇到鄰居交點生成虛擬節點示意圖；圖9是不屬於同一個有向傳感器節點的兩個虛擬節點的感知區域之間形成覆蓋重疊時的示意圖；圖10是本發明構建的有向覆蓋連通圖；圖11是根據本發明提供的方法進行判定的結果示意圖。
具體實施例方式下面結合附圖，對優選實施例作詳細說明。應該強調的是，下述說明僅僅是示例性的，而不是為了限制本發明的範圍及其應用。有向傳感器網絡由具有信息採集、多跳通信和處理等功能的多個有向傳感器節點(Directional Node)、匯聚節點(Sink Node)和兩個虛擬邊界節點(VirtualBoundary Node)組成的，虛擬邊界節點是虛構出來的兩個邊界節點分別用於描述左/右邊界。圖2是本發明提供的有向傳感器網絡強柵欄覆蓋判定方法流程圖，圖2中，向傳感器網絡強柵欄覆蓋判定方法包括步驟1 隨機部署有向傳感器節點，有向傳感器節點通過廣播方式自組織構成有向傳感器網絡。
圖3是本發明提供的有向傳感器網絡強示意圖，圖3中，隨機部署的有向傳感器節點通過廣播方式自組織構成網絡。每個有向傳感器節點通過GPS設備獲知位置信息，並對自身傳感方向可知可控。節點ID、位置和傳感方向等信息通過無線多跳通信方式上傳至充當網絡管理者的匯聚節點，並由匯聚節點生成網絡全局拓撲圖。與傳統基於全向感知模型的傳感器節點不同，有向傳感器節點的感知能力受到方向性限制，即其感知範圍是一個以傳感器節點為圓心，與感知距離和感知視角相關的扇形區域。圖4是有向傳感器節點方向可調感知模型示意圖，圖4中，方向可調感知模型可以用一個四元組來表示。P = (X，y)表示有向傳感器節點的位置坐標；R表示有
向傳感器節點的傳感半徑；單位向量P=ζ)為感知區域的中軸線，即有向傳感器節點
UUULU
的傳感方向Af卩&分別是單位向量卩在X軸和Y軸方向上的投影分量；α表示邊界距離
傳感向量 ■的傳感偏移角度，2 α表示感知視角(FOV)。有向傳感器節點的傳感能力可調可控，它有能力覆蓋到其傳感半徑內的整個圓形區域。定義距離小於等於傳感半徑R的兩倍的一對有向傳感器節點互為鄰居節點，圖5 是有向傳感器節點和有向傳感器節點的鄰居節點示意圖，圖5中，對於互為鄰居的一對有向傳感器節點而言，通過傳感方向的調整彼此有可能形成傳感區域的重疊。步驟2 匯聚節點為每個有向傳感器節點生成虛擬節點。其過程具體是步驟21 匯聚節點分別根據左邊界與有向傳感器節點的位置關係以及右邊界與有向傳感器節點的位置關係，建立左邊界節點集Π ！和右邊界節點集Π匯聚節點根據左/右邊界與有向傳感器節點的位置關係，分別找到距離左/右邊界不超過傳感半徑R(即這些有向傳感器節點通過傳感方向調整有可能覆蓋到左或右邊界)的有向傳感器節點，並加入到左/右邊界節點集Π ！和Π圖6是確定有向傳感器網絡左/右邊界節點集的示意圖。圖6中，有三個有向傳感器節點Stl，S1, S2分別與左邊界距離小於等於傳感半徑R，因此，左邊界節點集Π ！ = {s0, S1, S2I。類似地，右邊界節點集Π r = {sn_i，sj。步驟22 匯聚節點判斷左邊界節點集Π ！和右邊界節點集Π r是否都不為空集時， 如果是，則執行步驟23 ；否則，結束該過程；步驟21結束後，匯聚節點需要進行判定當TI1^ Φ和Π,興Φ同時滿足時，方執行後續過程；否則，判定過程提前結束，可以直接判定有向傳感器網絡不滿足強柵欄覆蓋。步驟23 將每個有向傳感器節點的扇形感知區域擴展為圓形感知區域。步驟24 有向傳感器節點的圓形感知區域與邊界相交形成邊界交點；有向傳感器節點的圓形感知區域與有向傳感器節點的鄰居節點的圓形感知區域相交形成鄰居交點。圖7是有向傳感器節點擴展為完整的圓形感知區域後的關係示意圖。圖7所示的實例涵蓋了有向傳感器節點擴展為完整的圓形感知區域後的四種基本位置關係，包括(Al)有向傳感器節點的圓形感知區域與邊界相交形成邊界交點。如圖7中有向傳感器節點Stl，S1, S2的圓形感知區域與邊界相交形成的邊界交點。(Α2)兩個距離小於等於傳感半徑R的有向傳感器節點(互為鄰居節點)的圓形感知區域相交形成的鄰居交點。如圖7中有向傳感器節點Stl和S1的圓形感知區域相交形成的鄰居交點，以及有向傳感器節點S1和S2的圓形感知區域相交形成的鄰居交點。(A3)兩個距離大於1倍傳感半徑R但小於等於2倍傳感半徑R的有向傳感器節點 (互為鄰居節點)的圓形感知區域相交形成的鄰居交點。如圖7中有向傳感器節點Stl和S2 的圓形感知區域相交形成的鄰居交點。(A4)孤島節點。如圖7中有向傳感器節點S3的圓形感知區域不與邊界相交，也不與其他有向傳感器節點的圓形感知區域相交。
步驟25 每個有向傳感器節點的扇形傳感區域繞自身旋轉掃視一周，當遇到邊界交點、鄰居交點和其他有向傳感器節點時，就在該位置為該有向傳感器節點生成一個虛擬節點。圖7提供了有向傳感器節點擴展為完整的圓形感知區域後的四種基本位置關係， 根據這四種基本位置關係，生成虛擬節點的具體過程分四種情況(Bi)如圖8(a)所示，當有向傳感器節點的圓形感知區域與邊界相交形成邊界交點時，以有向傳感器節點Stl為例，用節點Stl的扇形感知區域從初始傳感方向出發，繞節點順時針旋轉掃視其圓周，一旦遇到與邊界的交點(A和B)時，就在該位置(A和B)為節點Stl生成一個虛擬節點。按虛擬節點生成的先後順序，分別命名為Vt 和V(ll。(B2)如圖8(b)所示，當兩個距離小於等於傳感半徑R的有向傳感器節點(互為鄰居節點)的圓形感知區域相交形成鄰居交點時，以有向傳感器節點Stl和S1為例，有向傳感器節點Stl的扇形感知區域從初始傳感方向出發，繞StJ幌時針旋轉掃視其圓周。一旦遇到與S1的圓形感知區域相交形成的鄰居交點(C和D)時，以及遇到節點S1時，就在該位置(C 點、D點和S1點)為節點Stl生成一個虛擬節點。按虛擬節點生成的先後順序，分別命名為
V02，V03 禾口 V04°(B3)如圖8 (c)所示，當兩個距離大於1倍傳感半徑R但小於等於2倍傳感半徑R 的有向傳感器節點的圓形感知區域相交形成鄰居交點時，以有向傳感器節點S0和S2為例， 用有向傳感器節點Stl的扇形感知區域從初始傳感方向出發，繞節點順時針旋轉掃視其圓周，一旦遇到與S2的圓形感知區域相交形成的鄰居交點(E和F)時，就在該位置(E和F)為有向傳感器節點Stl生成一個虛擬節點，按虛擬節點生成的先後順序，分別命名為Vtl5和Y060(B4)有向傳感器節點為孤島節點時，由於該節點的圓形感知區域不與邊界相交， 也不與其他有向傳感器節點的圓形感知區域相交，因此，孤島節點不能生成虛擬節點。通過上述方式生成的虛擬節點也是具有感知方向和感知區域的，其感知區域是以 R為傳感半徑、2 α為感知視角的扇形感知區域。從上述實例(Β1)-(Β4)可以看出一個有向傳感器節點有可能生成0個或者1個及以上虛擬節點。其中，生成0個虛擬節點就是孤島節點的情況。每個虛擬節點屬於且僅屬於一個真實的有向傳感器節點。假設一個有向傳感器網絡中有η個有向傳感器節點，根據上述方法，匯聚節點為這η個有向傳感器節點生成了 m個虛擬節點(一般地，η < m)。有向傳感器節點與邊界節點、鄰居節點位置關係的差異，會造成不同的有向傳感器節點生成的虛擬節點數目不同。例如圖8中所示，節點Stl生成V(1(1、
V01、V02、V03、V04、V05 和Vtl6共計7個虛擬節點；而節點S1則
生成8個虛擬節點，節點S2生成7個虛擬節點，節點S3生成0個虛擬節點。根據此方法，可以對網絡中的所有有向傳感器節點生成其虛擬節點。步驟3 匯聚節點根據生成的虛擬節點和兩個虛擬邊界節點，構建有向覆蓋連通圖。所有有向傳感器節點生成虛擬節點後，匯聚節點根據生成的虛擬節點和兩個虛擬邊界節點，構建有向覆蓋連通圖。其構建過程是將生成的所有虛擬節點和兩個虛擬邊界節點構成頂點集合，在頂點集合中，當虛擬節點的感知區域覆蓋到左邊界/右邊界時，則在描述左邊界/右邊界的虛擬邊界節點與該虛擬節點之間建立一條邊；當不屬於同一個有向傳感器節點的兩個虛擬節點的感知區域之間形成覆蓋重疊時，則在所述兩個虛擬節點之間建立一條邊。在本實施例中，構建有向覆蓋連通圖分兩種情況(Cl)如圖8(a)所示，如果節點Stl，S1, S2的虛擬節點能覆蓋到左邊界，則在有向覆蓋連通圖G(v，e)中，在左虛擬邊界節點ζ與該虛擬節點之間建立一條邊。例如對％節點而言，如果虛擬節點Vtltl和Vtll的感知區域能覆蓋到左邊界，則在G(v，e)中，在(z，V00)和 (ζ, ν01)兩對頂點之間建立連線。從圖8(a)中可以看出，虛擬節點Vt 和Vtll都落在了左邊界，那麼虛擬節點Vtltl和Vtll的感知區域必然能夠覆蓋左邊界，因此在有向覆蓋連通圖G(v， e)中，在(Z，VJ和(z，V(11)兩對頂點之間建立連線。類似地，如果虛擬節點sn_j「n的感知區域能覆蓋到右邊界，則在有向覆蓋連通圖G(v，e)中，在右虛擬邊界節點t與這些虛擬節點之間，分別建立一條邊。(C2)圖9是不屬於同一個有向傳感器節點的兩個虛擬節點的感知區域之間形成覆蓋重疊時的示意圖。圖9中，虛擬節點Vitl屬於有向傳感器節點Si (即Vitl由Si生成)，虛擬節點、和、屬於有向傳感器節點~。從圖9中看出，虛擬節點Vitl的感知區域分別與虛擬節點、和 的感知區域形成重疊覆蓋，則在有向覆蓋連通圖G(v，e)中，分別在(Vitl， vJ0)和(Vitl，Vjl)兩對節點之間建立連線。圖10是按照上述方式構建的有向覆蓋連通圖G(v，e)。步驟4:匯聚節點遍歷有向覆蓋連通圖，如果找到一條從一個虛擬邊界節點到另一個虛擬邊界節點的連通路徑，則判定有向傳感器網絡滿足強柵欄覆蓋；否則，判定有向傳感器網絡不滿足強柵欄覆蓋。圖11是根據本發明提供的方法進行判定的結果示意圖。圖11中，在判定階段，匯聚節點遍歷有向覆蓋連通圖G (v，e)，若能找到一條從ζ到t的連通路徑，則判定有向傳感器網絡滿足強柵欄覆蓋。需要格外指出的是屬於同一個有向傳感器節點的多個虛擬節點，最多也只有一個處於該連通路徑中。例如，對於節As1，它有k個虛擬節點，Vltl，vn，V12，…， Vlk，但Vli (i = 0，1，2，...，k)在構成從ζ到t的連通路徑中只能出現一次。這是因為，對於一個有向傳感器節點而言，在某個具體時刻它能且只能處於一個虛擬節點的狀態。圖10中，找到一條從ζ到t的連通路徑P1 = {ζ- > S1- > S2- > S3- > s「> Sj- > sn_「> Sn- > t}(由於屬於同一個有向傳感器節點的虛擬節點在上述路徑中只能出現一次，因此在連通路徑Pl中，使用虛擬節點所屬的有向傳感器節點代替該虛擬節點)，其中連通路徑上面的各個有向傳感器節點根據其相對應的虛擬節點重置其傳感方向，此時可判定該有向傳感器網絡滿足強柵欄覆蓋。另外，有可能找到兩條或更多條從ζ到t的連通路徑p2 = {ζ- > S2- > S4- > Sj- > sn_「> sn- > t}。由此可見構成從ζ到t的連通路徑的虛擬節點以及虛擬節點數目均可以是不相同的，但因為這兩條連通路徑共用有向傳感器節點S2，S4, Sj, Slri和sn，因此只能選擇其中一種連通路徑的條件去重置相應有向傳感器節點的傳感方向。否則，遍歷有向覆蓋連通圖G(V，e)無法找到一條從ζ到t的連通路徑， 我們則可以判定有向傳感器網絡不滿足強柵欄覆蓋。此時就需要部署額外的有向傳感器節點以最終實現網絡的強柵欄覆蓋。與現有技術相比，本發明充分考慮了鄰居節點間的相對位置變化與形成網絡強柵欄覆蓋之間的聯繫，採用有限離散的方法去解決一個無限連續問題，即通過定義有限數目的虛擬節點方法對問題進行簡化和映射。同時，本發明又克服了現有判定方法假設簡單、 運算量大等在實際應用中的局限性。利用本發明提供的方法，可有效實現有向傳感器網絡強柵欄覆蓋的判定，通過調整有向傳感器節點的傳感方向來增強整個網絡的強柵欄覆蓋能力，為以有向感器網絡為基礎的移動目標穿越監測提供良好的監測性能。以上所述，僅為本發明較佳的具體實施方式
，但本發明的保護範圍並不局限於此， 任何熟悉本技術領域的技術人員在本發明揭露的技術範圍內，可輕易想到的變化或替換， 都應涵蓋在本發明的保護範圍之內。因此，本發明的保護範圍應該以權利要求的保護範圍為準。
權利要求
1.一種有向傳感器網絡強柵欄覆蓋判定方法，有向傳感器網絡由有向傳感器節點、匯聚節點和兩個虛擬邊界節點組成；其中，有向傳感器節點的感知區域是以R為傳感半徑， 2α為感知視角，感知視角的角平分線為中軸線的扇形感知區域，兩個虛擬邊界節點分別用於描述有向傳感器網絡的左邊界和右邊界，其特徵是所述方法包括步驟1 隨機部署有向傳感器節點，有向傳感器節點通過廣播方式自組織構成有向傳感器網絡；步驟2 匯聚節點為每個有向傳感器節點生成虛擬節點；所述虛擬節點的感知區域是以2α為感知視角，以R為傳感半徑的扇形區域；步驟3 匯聚節點根據生成的虛擬節點和兩個虛擬邊界節點，構建有向覆蓋連通圖；步驟4 匯聚節點遍歷有向覆蓋連通圖，如果找到一條從一個虛擬邊界節點到另一個虛擬邊界節點的連通路徑，則判定有向傳感器網絡滿足強柵欄覆蓋；否則，判定有向傳感器網絡不滿足強柵欄覆蓋。
2.根據權利要求1所述的一種有向傳感器網絡強柵欄覆蓋判定方法，其特徵是所述匯聚節點為每個有向傳感器節點生成虛擬節點具體包括步驟21 匯聚節點分別根據左邊界和右邊界與有向傳感器節點的位置關係，建立左邊界節點集Π ！和右邊界節點集Π r ；步驟22 匯聚節點判斷左邊界節點集Π ！和右邊界節點集Π r是否都不為空集，如果是，則執行步驟23 ；否則，結束該過程；步驟23 將每個有向傳感器節點的扇形感知區域擴展為圓形感知區域；步驟M 有向傳感器節點的圓形感知區域與邊界相交形成邊界交點；有向傳感器節點的圓形感知區域與有向傳感器節點的鄰居節點的圓形感知區域相交形成鄰居交點；步驟25 每個有向傳感器節點的扇形傳感區域繞自身旋轉掃視一周，當遇到邊界交點、鄰居交點或者其他有向傳感器節點時，就生成一個虛擬節點。
3.根據權利要求2所述的一種有向傳感器網絡強柵欄覆蓋判定方法，其特徵是所述步驟21具體是匯聚節點找到距離左邊界不超過傳感半徑R的有向傳感器節點，並將其加入到左邊界節點集Π！中；並找到距離右邊界不超過傳感半徑R的有向傳感器節點，並將其加入到右邊界節點集TIr中。
4.根據權利要求2所述的一種有向傳感器網絡強柵欄覆蓋判定方法，其特徵是所述有向傳感器節點的鄰居節點是指與所述有向傳感器節點的距離小於等於傳感半徑兩倍的另一個有向傳感器節點。
5.根據權利要求1所述的一種有向傳感器網絡強柵欄覆蓋判定方法，其特徵是所述構建有向覆蓋連通圖具體是，將生成的所有虛擬節點和兩個虛擬邊界節點構成頂點集合，在頂點集合中，當虛擬節點的感知區域覆蓋到左邊界/右邊界時，則在描述左邊界/右邊界的虛擬邊界節點與該虛擬節點之間建立一條邊；當不屬於同一個有向傳感器節點的兩個虛擬節點的感知區域形成覆蓋重疊時，則在這兩個虛擬節點之間建立一條邊。
全文摘要
本發明公開了無線通信技術領域中的一種有向傳感器網絡強柵欄覆蓋判定方法，用以解決目前有向傳感器網絡強柵欄覆蓋的研究存在的問題。該方法包括隨機部署有向傳感器節點，有向傳感器節點通過廣播方式自組織構成有向傳感器網絡；匯聚節點為每個有向傳感器節點生成虛擬節點；虛擬節點也具有感知方向和感知區域；匯聚節點根據生成的虛擬節點和兩個虛擬邊界節點，構建有向覆蓋連通圖；匯聚節點遍歷有向覆蓋連通圖，並判定有向傳感器網絡是否滿足強柵欄覆蓋。本發明克服了現有判定方法假設簡單、運算量大等在實際應用中的局限性，有效實現了有向傳感器網絡強柵欄覆蓋的判定。
文檔編號H04W84/18GK102158988SQ20111009340
公開日2011年8月17日 申請日期2011年4月14日 優先權日2011年4月14日
發明者陶丹 申請人:北京交通大學