摘要 - 我們提出了兩種算法，用于傳感器領域中傳感器的高效放置。所提出的方法旨在優(yōu)化傳感器的數量并確定它們的位置以支持分布式傳感器網絡。由于與傳感器檢測相關的不確定性，優(yōu)化框架是固有的概率性的。所提出的算法在不精確檢測和地形屬性的約束下，對覆蓋優(yōu)化進行了定位。這些算法的目標是平均覆蓋面以及最大限度地提高最脆弱網格點的覆蓋面。網格點的優(yōu)先覆蓋問題（基于安全性和戰(zhàn)術重要性的相對措施）也被建模。具有障礙物的示例傳感器場的實驗結果表明我們的方法的應用。
傳感器布置直接影響資源管理以及必須用分布式傳感器網絡中感測數據執(zhí)行的后端處理和開發(fā)的類型。傳感器資源管理中的一個關鍵挑戰(zhàn)是確定優(yōu)化成本的傳感器現場架構，并提供高傳感器覆蓋率，對傳感器故障的恢復能力以及適當的計算/通信權衡。智能傳感器放置有助于傳感器/開發(fā)系統的統一設計和操作，并減少對過度的網絡通信進行監(jiān)視，目標定位和跟蹤的需要。傳感器放置因此在前端感測和后端開發(fā)之間形成必不可少的“膠”。
在這項工作中，我們提出了一個在需要覆蓋足夠傳感器范圍的網格的限制下，對資源有限的傳感器資源管理優(yōu)化框架。所提出的方法提供了分布式傳感器網絡的獨特的“簡約”想法（這里指的就是在滿足可工作的條件下，使用最少的資源），其中部署了最少數量的傳感器，并且它們傳送/報告最小量的感測數據。智能傳感器的放置確保該數據的集合包含足夠的信息，用于數據處理中心隨后查詢少量傳感器以獲取詳細信息，例如，圖像和時間序列數據。所提出的方法旨在優(yōu)化傳感器的數量及其在網絡配置中的布局，并支持這樣的簡約傳感器網絡。
傳感器部署必須考慮到地形的性質，例如紅外傳感器視線中的建筑物和樹木等障礙物，丘陵地帶的不平坦表面和高程，傳感器故障的可能性造成的冗余以及所需的電力在部署的傳感器之間以及部署的傳感器和集群頭之間傳輸信息。
我們將傳感器場表示為一個網格（二維或三維）點。因此，傳感器領域中的目標是一個邏輯對象，它由一組可以看到它的傳感器表示。不規(guī)則傳感器場被建模為網格集合。然而，由于與傳感器檢測相關的不確定性，優(yōu)化框架本質上是概率性的。我們提出了兩種用于傳感器布置的算法，在不精確檢測和地形屬性的約束下解決覆蓋優(yōu)化問題。網格點的優(yōu)先覆蓋問題（基于安全性和戰(zhàn)術重要性的相對措施）也被建模。我們將本文的討論限于固定傳感器。具有障礙物的示例傳感器場的實驗結果表明我們的方法的應用。
隨著傳感器在現場操作中的使用越來越多，高效的部署策略越來越重要。運動規(guī)劃的地形模型獲取的相關工作集中在機器人在未開發(fā)的“傳感器領域”的運動[1]。雖然地形的知識對于監(jiān)視至關重要，但它并不直接解決傳感器放置問題。 [8]提出了基于潛在領域概念的移動傳感器的自我部署。然而，自我部署不能為需要部署在特定配置中的靜態(tài)傳感器提供解決方案，以用于環(huán)境監(jiān)控等應用。無線傳感器網絡中的一個相關問題是空間定位[9]。當確定性地部署傳感器時，本地化尤其重要，例如，當傳感器從戰(zhàn)場上的飛機投擲時，以及由于漂移可能移動的水下傳感器。最近提出了一些用于精細和粗粒度定位的技術[6,10]。
在文獻[7]中還討論了確定傳感器給定放置提供的覆蓋范圍的問題。傳感器放置在二維和三維網格上已被公式化為組合優(yōu)化問題，并使用整數線性規(guī)劃求解[2,3]。這種方法有兩個主要缺點。首先，計算復雜度使得該方法對于大問題實例不可行。第二，電網覆蓋方法依賴于“完美”傳感器檢測，即傳感器預期在每種情況下產生二進制的是/否檢測結果。傳感器讀數存在固有的不確定性，因此必須對傳感器檢測進行概率建模。
傳感器放置問題與藝術畫廊問題（AGP）在藝術畫廊定理[4]中存在著非常相似的關系。 AGP問題可以非正式地說明為確定覆蓋藝術畫廊內部所需的最少衛(wèi)兵數量。我們的傳感器放置問題與AGP的不同之處有兩個基本的方面：（a）傳感器可以具有不同的范圍，不同于在AGP中，衛(wèi)星被假設具有相似的能力，（b）與衛(wèi)兵的入侵者檢測不同，傳感器檢測結果是概率性的。其他相關工作包括放置一定數量的傳感器以降低通信成本[5]，以及給定目標分布的最佳傳感器放置。
本文的其余部分組織如下。在第2節(jié)中，我們描述了我們的傳感器檢測模型以及我們對地形建模的方法。第3節(jié)描述了放置傳感器以提供傳感器場的足夠覆蓋的兩個程序。我們還展示了如何增加放置算法以提供網格點的差異覆蓋（基于安全性和戰(zhàn)術重要性的相對度量）。第4節(jié)介紹了各種問題實例的實驗結果。提出了隨機傳感器放置和傳感器均勻放置的比較，以突出所提出的算法的有效性。最后，第5節(jié)總結了本文，并描述了未來工作的方向。
II. SENSOR AND TERRAIN MODEL
傳感器放置需要準確但計算可行的傳感器檢測模型。在這項工作中，我們首先假設傳感器場由網格點組成。網格的粒度（連續(xù)網格點之間的距離）由傳感器放置所需的準確度決定。
我們假設傳感器檢測目標的概率隨著目標和傳感器之間的距離而呈指數級變化。該模型在圖1中示出。來自傳感器的距離d處的目標由具有概率e^-αd的傳感器檢測。參數α可用于對傳感器的可靠性和其檢測概率隨距離減小的速率進行建模。顯然，如果目標位置和傳感器位置重合，檢測概率為1。對于傳感器場中的每兩個網格點i和j，我們將兩個概率值相關聯：（i）pij，其表示網格點i處的傳感器在網格點j處檢測到的目標的概率; （ii）pji，其表示在網格點j處由傳感器檢測到網格點i處的目標的概率。在沒有障礙物的情況下，這些值是對稱的，即pij = pji。然而，我們將在本節(jié)稍后展示這些值在存在障礙物時不必相等。
注意，傳感器檢測模型的選擇不會以任何方式限制放置算法的適用性。檢測模型僅僅是放置算法的輸入參數。因此可以考慮替代檢測模型，而不需要重新設計放置算法。
接下來，我們將介紹如何在這個框架中模擬地形中的障礙。多個傳感器，例如紅外攝像機，需要一個目標躺在他們的視線。障礙物引起閉塞并使這種傳感器對檢測無效。我們假設在傳感器放置之前獲取一些關于地形的知識，例如。通過衛(wèi)星圖像。然后通過改變適當的網格點對的檢測概率來建模障礙物。例如，如果諸如建筑物或樹葉的對象存在于從網格點i到網格點j的視線中，則我們設置pij = 0。部分遮擋也可以通過設置非零但小的檢測概率的值。
例如，考慮圖2傳感器領域的兩個障礙物。該圖中的網格點從1到16進行編號。如果我們假設這些障礙是對稱的，那么它們會導致p36，p63，p27，p72和許多其他檢測概率要呈現為零。直接確定對于任何兩個網格點i和j，pij是否受到障礙物的影響。每個網格點與平面中的一對（x，y）坐標相關聯。類似地，障礙物還具有關聯（x，y）坐標。我們確定連接i和j的直線的方程。如果障礙物的坐標滿足該等式，則將概率pij設置為零。
在許多實際情況下，傳感器場中的障礙物是不對稱的，即pij = 0并不意味著pji = 0。這可能發(fā)生在例如丘陵地帶的情況下。較低仰角的傳感器不太可能在較高仰角處檢測到目標，但是在較高仰角處的傳感器可以在較低高度檢測目標。通過使用適當的檢測概率值，可以在我們的框架中輕松建模這種情況。
III. SENSOR PLACEMENT ALGORITHMS
在本節(jié)中，我們描述了傳感器領域（無論是否有障礙物）中給定的一組檢測概率的傳感器放置算法。傳感器放置算法的目標是確定傳感器的最小數量及其位置，以便每個網格點都以最小置信度水平覆蓋。我們使用術語覆蓋閾值來引用這個置信水平。提供覆蓋閾值T作為放置算法的輸入。我們的目標是確保每個網格點的概率至少為T。
第一個程序MAX_AVG_COV嘗試最大化網格點的平均覆蓋。第二個程序MAX_MIN_COV嘗試最大限度地提高覆蓋率最小的網格點。
我們首先為傳感器場中的所有網格點對生成傳感器檢測矩陣D =[pij]。對于n×n網格，我們共有n2個網格點，因此矩陣D由n2行和n2列組成，總共包含n4個元素。
從傳感器檢測矩陣D，我們確定未知概率矩陣M = mij，其中mij = 1-pij。我們不會在傳感器放置算法中直接使用D。相反，我們使用未命中概率矩陣M。傳感器放置算法都使用貪心啟發(fā)式來一次確定一個傳感器的最佳位置。算法是迭代的，并且它們在每次迭代期間將一個傳感器放置在傳感器場中。當達到傳感器數量的預設上限，或者達到網格點的足夠覆蓋時，它們終止。
我們將矢量M * =（M1，M2，...，MN）定義為傳感器場中N = n^2個網格點的遺漏概率集合。該矢量中的Mi表示網格點i未被集成在傳感器場中的傳感器集合覆蓋的概率。在放置算法開始時，矢量M被初始化為全1矢量，即M * =（1,1，...，1）。放置在傳感器區(qū)域中的每個傳感器減少該矢量中的一個或多個Mi。當遺漏概率矩陣中的相應行和列變得多余時，傳感器的放置也將遺漏概率矩陣的順序降低1。第一傳感器放置算法MAX_AVG_COV的偽代碼步驟在圖3中概述。令Mmin = 1-T是任何網格點允許的未命中概率的最大值。
請注意，通過Σi參數在MAX_AVG_COV過程中測量由附加傳感器引起的電網覆蓋的有效性。這種方法嘗試通過對各個網格點的遺漏概率的變化求和來評估附加傳感器的全局影響。接下來我們將介紹傳感器布置方法如何有助于網格點的優(yōu)先覆蓋。在典型的軍事力量保護或民防方案中，必須給予某些裝置額外的保護。這樣的設施可能包括核電廠，指揮總部或民政管理中心。
為了模擬優(yōu)先覆蓋，我們?yōu)槊總€網格點i分配不同的保護概率pri。網格點i的未知概率閾值則表示為Mimin = 1-pri。程序MAX_AVG_COV被修改為使得重復/直到循環(huán)的終止標準基于檢查已經達到每個網格點的各個未知概率閾值。
傳感器放置的另一種方法是將傳感器放置在柵格點的每次迭代處，覆蓋面最小。 （第一個傳感器隨機放置在網格中）然后計算每個網格點的覆蓋范圍，并將下一個傳感器放置在網格中的最小覆蓋點。這個過程一直持續(xù)到所有的傳感器都被放置，或者超出了覆蓋范圍上的預定閾值。傳感器放置算法MAX_MIN_COV的偽代碼步驟如圖4所示。
個人觀點：兩者的區(qū)別是上面一種算法將傳感器放在使得全局降低最多的地方，而這種算法則放在覆蓋率最低的地方。
MAX_AVG_COV和MAX_MIN_COV算法的計算復雜度為O（kN），其中k是給定覆蓋閾值所需的傳感器數量。由于k不是先驗知道的，我們使用N作為k的上限，并獲得O（N^2）的計算復雜度。
MAX_AVG_COV和MAX_MIN_COV算法的偽代碼描述使得傳感器檢測是獨立的隱式假設，即如果傳感器以概率p1在網格點處檢測到目標，并且另一個傳感器以概率p2在該網格點處檢測到相同的目標，則目標的未命中概率為（1- p1）（1- p2）。
迄今為止，我們已經考慮了傳感器領域中只有網格點的覆蓋范圍。為了提供傳感器場的穩(wěn)健覆蓋，我們還需要確保位于網格點之間的區(qū)域被充分覆蓋，即每個非網格點的故障概率小于閾值Mmin。考慮圖5中位于正方形四角的四個網格點。讓這些網格點之間的距離為d *。平方對角線的交點與四個網格點的距離為d * /√2。以下定理提供了足夠的條件，在該條件下，非柵極點被MAX_AVG_COV和MAX_MIN_COV算法充分覆蓋。
定理1：使網格點P1和潛在傳感器位置P2之間的距離為d。讓相鄰網格點之間的距離為d *。如果使用d + d * /√2的值來計算由于傳感器在P2處的網格點P1的覆蓋范圍，并且可用傳感器的數量是足夠的，則所有非網格點的未命中概率小于算法MAX_AVG_COV和MAX_MIN_COV終止時的閾值Mmin。
證明：考慮圖5中的四個網格點。平方的中心，即對角線的交點與四個網格點中的每一個距離為d * /√2。每個其他非網格點距離四個網格點中的至少一個更短的距離（小于d * /√2）。因此，如果使用d + d * /√2的值來確定MAX_AVG_COV和MAX_MIN_COV算法中的覆蓋范圍，則可以保證每個非網格點以超過1 Mmin的概率被覆蓋。
為了說明定理1，我們考慮一個8乘8格，α= 0.6，Mmin = 0.4。我們使用定理1和MAX_AVG_COV算法來確定傳感器位置，并計算所有正方形中心的遺漏概率。圖6所示的結果表明，遺漏概率總是小于閾值Mmin，從而確保對非網格點的充分覆蓋。
在本節(jié)中，我們提出了兩種傳感器放置算法的實驗結果。我們首先確定傳感器位置，以最小化給定覆蓋閾值的傳感器數量。我們將MAX_AVG_COV和MAX_MIN_COV與傳感器的隨機放置以及均勻放置進行比較。我們使用定理1來保證所有非網格點都被充分覆蓋。我們的第一個觀察是，如果傳感器領域沒有障礙物，并且所有的傳感器被認為是相同的，則隨機放置與MAX_AVG_COV一樣有效。這不是意想不到的，因為這些問題實例的規(guī)律性使得它們特別適合隨機放置。我們接下來顯示，當傳感器場包含障礙物并且需要優(yōu)先覆蓋時，隨機放置執(zhí)行得更差。
