趙 猛，左 燕，李明地，郭寶峰

（杭州電子科技大學通信信息傳輸與融合技術國防重點學科實驗室，杭州 310018）

通信受限下分布式多傳感器協(xié)同跟蹤算法*

趙 猛，左 燕，李明地，郭寶峰

（杭州電子科技大學通信信息傳輸與融合技術國防重點學科實驗室，杭州 310018）

在分布式多傳感器目標跟蹤系統(tǒng)中，由于局部融合中心（LFC）的物理限制（如：有限的頻率信道、處理器容量有限等），只能接收有限個傳感器的傳送數(shù)據(jù)。此外，信息傳輸?shù)姆绞揭矊⒂绊憘鞲芯W(wǎng)的使用壽命，因此，研究了通信受限下的分布式多傳感器目標協(xié)同跟蹤問題。首先對監(jiān)視區(qū)內分布的傳感器進行聚類分簇形成若干個子網(wǎng)，接著從通信能耗的角度出發(fā)，對傳感器采集信息的傳遞路徑進行最優(yōu)路徑規(guī)劃；進而對子網(wǎng)局部狀態(tài)進行估計，在子網(wǎng)信息融合中，分別采用最大距離和、最大化信息增量兩種準則進行最佳傳感器選擇，最后通過各子網(wǎng)全局航跡融合實現(xiàn)分布式多傳感器協(xié)同跟蹤。仿真驗證了算法的有效性。

分布式，通信受限，最短路徑規(guī)劃，聚類分簇，航跡融合

0 引言

利用空間分布的多個傳感器（雷達、紅外、激光測距儀、聲吶等）來協(xié)同跟蹤目標是未來網(wǎng)絡化作戰(zhàn)的特點［1］。在網(wǎng)絡化協(xié)同跟蹤系統(tǒng)中，地域分散的多個傳感器協(xié)同工作，獲得目標的精確運動。在多傳感網(wǎng)信息融合系統(tǒng)中，集中式與分布式融合結構是最基本和最重要的兩種結構。目前，關于集中式融合結構的相關理論已經(jīng)比較成熟。基于此，從分布式的角度來考慮傳感器組網(wǎng)協(xié)同跟蹤問題是必然的。

在多源信息融合系統(tǒng)中，傳感器管理是必然要考慮的問題。傳感器資源的相對不足，目標環(huán)境機動性增強，不確定性增加，這些都加劇了傳感器對目標的有效分配難度［2］。當多個傳感器同時用于多個目標的檢測、跟蹤和識別時，必須解決傳感器與目標之間以及檢測、跟蹤和識別之間的資源調度問題，也就是如何在一定條件下，合理充分利用傳感器資源且滿足系統(tǒng)最優(yōu)性能的要求。在分布式多傳感器跟蹤系統(tǒng)中，由于局部融合中心（LFC）的物理限制（如：有限的頻率信道、處理器容量有限等），只能接收有限個傳感器的傳送數(shù)據(jù)［3］。因此，在由大量傳感器組成的傳感器網(wǎng)絡中，必須要考慮傳感器的選擇問題。目前，國內外關于傳感器管理的方法主要有：協(xié)方差、信息論、規(guī)劃論以及智能方法［4］。而在諸多傳感器管理方法中，既具有科學性又具有可行性的方法應當建立在信息論與規(guī)劃論基礎之上，這類方法對一般的傳感器管理才更具有普遍意義。所以，本文傳感器選擇算法是基于信息增益和距離和的方法；另外需要考慮的一個問題就是傳感器的使用壽命，影響傳感器使用壽命的因素有很多，而很重要的一個原因就是傳感器的通信能耗。因此，本文從信息傳輸方式的角度出發(fā)，進行最優(yōu)傳輸路徑規(guī)劃，進而達到減少能耗，延長傳感器使用壽命的目的。

1 問題描述

1.1 聚類分簇

本文考慮的是大量傳感器，將監(jiān)視區(qū)域內的傳感器聚類分簇并進行分布式處理，這不僅有助于降低系統(tǒng)的通信負擔，也能提高系統(tǒng)的容錯性［5］。本文采用C均值算法進行聚類分簇，將所給的隨機傳感器聚類分成k簇，其中k值的大小根據(jù)最小化誤差平方和Je（k）獲得［6］。具體的算法步驟如下：

①初始根據(jù)經(jīng)驗分為k1個聚類，選擇前k1個傳感器作為初始聚類的核心；

②根據(jù)距核心距離最小原則將其余的樣本劃分到各初始類中；

1.2 LFC選定

在分布式結構中，局部中心（LFC）個數(shù)有給定和隨變兩種。本文選擇的是LFC個數(shù)隨變即有幾個簇就有幾個LFC，相比個數(shù)給定的優(yōu)點是能夠根據(jù)環(huán)境的實時性做出調整，節(jié)約資源。對于每個子網(wǎng)中LFC的選定原則是Di最小。用到如下公式：

式中，Di表示第i個子網(wǎng)的平均距離，Ni表示第i個子網(wǎng)中傳感器個數(shù)，Xi，j表示第i個子網(wǎng)第j個傳感器的位置，Xi，ni表示第i個子網(wǎng)中選定的局部融合中心傳感器ni的位置。

1.3 能耗模型及處理算法

傳感器節(jié)點由傳感器模塊、處理器模塊、無線通信模塊和能量供應模塊4部分組成。傳感器模塊負責監(jiān)視區(qū)域內信息采集和數(shù)據(jù)轉換；處理器模塊負責控制整個傳感器節(jié)點的操作，存儲和處理本身采集數(shù)據(jù)以及其他節(jié)點發(fā)來的數(shù)據(jù)；無線通信模塊負責與其他傳感器節(jié)點進行無線通信，交換控制消息和收發(fā)采集數(shù)據(jù)；能量供應模塊為傳感器節(jié)點提供所需的能量［7］。這些模塊中，通信模塊耗能最高，它通常由通信雙方節(jié)點的位置和傳輸時間決定。通信模塊為一階系統(tǒng)，傳感器發(fā)送r bit數(shù)據(jù)到距離d所耗的能量為：

式中，eie是發(fā)射電路能耗，εa為功率放大能耗，rimax為該傳感器的最大通信距離，r為要發(fā)送的bit數(shù)據(jù)。相應地，傳感器接收r bit數(shù)據(jù)所耗的能量為：

式中，ere是接收電路能耗。通信模塊的參數(shù)通常采 用 的 設 置 如 下 ：eie=50 nJ/bit，εa=100 pJ/m2/bit，ere=50 nJ/bit。

由式（1）可知，信息傳遞能耗隨著兩個傳感器間距離的增加而急劇上升，即相距較遠的兩個傳感器進行直接通信比多跳通信能耗大，所以采用多跳路徑理論上可以有效地節(jié)約能量。所以對每個子網(wǎng)中傳感器向LFC的傳遞路徑進行最優(yōu)路徑規(guī)劃，在這里采用的是Dijkstra算法獲得［8］。該方法是圖論中尋求最優(yōu)路徑的有效方法，可求每簇中LFC到各傳感器的最短路徑即最低能耗路徑。關于Dijkstra的算法步驟如下：

①初始化。設置權值矩陣W，考慮傳感器的通信范圍，超過通信的最大值代價設為+∞。將起始點設置為已標記點visit，其他所有點設為未標記點；

②計算所有已標記的點visit到其直接連接且未標記的點j的距離，并記錄，其中，lkj是從點k到點j的直接連接距離；

④找到點i的前一點。從已標記的點中找到直接連接到點i的點j*，作為前一點，并記錄i=j*；

⑤標記點i。如果所有點均已標記，則算法完成。

2 子網(wǎng)傳感器選擇

2.1 基于最大距離和的傳感器管理算法

由信息融合理論可知，為了獲得更高的跟蹤精度，往往可以采取選擇更多傳感器參與目標跟蹤的方法來實現(xiàn)。但是每個LFC能夠處理數(shù)據(jù)的能力是有限的，因此，要對每個子網(wǎng)中所采用的傳感器進行選擇。在已有的認識中可知，對于每個傳感器而言，距離目標近的傳感器測得的精度總是要相對高的。因此，對每個子網(wǎng)中要選擇的傳感器采用的代價函數(shù)是最大距離和，即所選擇的傳感器到LFC的距離和最大，公式如下：

Di表示第i個子網(wǎng)的平均距離，Ni表示第i個子網(wǎng)中傳感器個數(shù)，Xi，j表示第i個子網(wǎng)第j個傳感器的位置，Xi，ni表示第i個子網(wǎng)中選定的局部融合中心傳感器的位置。

2.2 基于最大信息增量的傳感器管理算法

根據(jù)信息論的觀點，傳感器探測的目的就是與目標環(huán)境相互作用以減少目標環(huán)境的不確定性。傳感器選擇的任務是產(chǎn)生一個合理的傳感器使用序列盡可能在每一次觀測中最大程度獲取信息［9］。對于目標跟蹤而言，通過改善已跟蹤目標的跟蹤精度能夠產(chǎn)生信息增量，而信息增量由跟蹤目標狀態(tài)向量的不確定性決定。這種不確定性可以用信息熵來定量描述，通過一個測量行為執(zhí)行前后信息熵的減少可以求得信息增量，然后根據(jù)使信息增量最大的準則能夠對傳感器資源進行科學合理的分配。

Shannon認為某個事件的信息可以用發(fā)生概率倒數(shù)描述。假設事件中每一種情況i（i=1，…，n）出現(xiàn)的概率為pi，則信息熵描述為：

若有一離散有限集合T，其狀態(tài)t（t=0，…，T）互斥，其中 q（t）、p（t）都是關于狀態(tài) t的概率密度函數(shù)，區(qū)別在于兩者分別表示量測前和量測后，則用先驗信息熵減去后驗信息熵來定義的信息增量可描述為：

其中 r表述某一正數(shù)，當 p（t）=q（t）時，表示本次測量沒有帶來新的信息，當 p（t）≠q（t）時，表示本次測量帶來了新的信息。

假設隨機變量x的概率密度分布p（x）可描述為：

則信息增量可以定義為量測前后信息熵之差：

其中，P（k|k）和 P（k|k-1）可由濾波算法得出。在傳感器管理中，通過計算目標狀態(tài)在前后第k次觀測前后的熵，然后計算得到信息增量I，最大化I完成傳感器的選擇。

3 分布式航跡融合

本文共同噪聲和共同先驗估計誤差均忽略，只考慮局部節(jié)點的估計狀態(tài)及方差且相互獨立，并且不考慮全局節(jié)點的先驗估計與方差。在此前提條件下，凸組合融合算法的效果是最優(yōu)的［10-11］。因此，從LFC到中心融合節(jié)點的航跡融合，本文采用的是凸組合融合算法。

根據(jù)文獻［4］可知，分布式融合系統(tǒng)中的航跡融合方程如下：

4 仿真

假設監(jiān)視區(qū)域內隨機分布著20個傳感器，每個傳感器都可以被當成局部融合中心（LFC）來處理其他傳感器傳來的數(shù)據(jù)，但是其所接受的最大傳感器數(shù)目是6，另外每個傳感器的量測噪聲協(xié)方差也是不同的，而目標采用是CV模型，并且是單目標。仿真結果，每簇以最大化距離和代價函數(shù)進行局部狀態(tài)估計，進而給出全局跟蹤狀態(tài)估計如圖1，以及最大化信息增量為代價函數(shù)的跟蹤效果如圖2，均方根誤差（RMSE）如圖3，聚類分簇及局部融合中心（LFC）選擇圖 4。

圖1 基于最大距離和跟蹤效果

圖2 基于最大化信息增量跟蹤效果

圖3 跟蹤均方根誤差值（RMSE）

由上圖的仿真結果可以看出，跟蹤效果很好接近于重合，產(chǎn)生這種結果的原因主要是對目標跟蹤的傳感器很多。由信息論可知，傳感器越多，跟蹤的精度越高。另外，由RMSE圖分析，可以看出兩種代價函數(shù)的跟蹤效果差不多。但事實上，基于距離和為代價函數(shù)實際上的可行性并不高，首先是因為計算量太大；其次，牽扯到目標運動模型未知時，此種算法跟蹤精度太低。

5 總結與展望

本文給出了一種通信受限情況下的分布式多傳感器目標跟蹤算法，并且從減少能耗提高傳感器使用壽命的角度給出了最短路徑規(guī)劃。本文針對分布式多傳感器目標跟蹤問題給出了一種結構框架即分簇、子網(wǎng)融合、全局融合；給出了兩種代價函數(shù)即最大化距離和以及最大化信息增量。從單目標的仿真效果來看，證明了其有效性。因此，考慮到實際應用，多目標動態(tài)傳感器跟蹤問題可以在此基礎上進一步探索。

［1］劉先省，申石磊，潘泉.傳感器管理及方法綜述［J］.電子學報，2002，30（3）：394-398.

［2］羅開平，姜維，李一軍.傳感器管理評述［J］.電子學報，2010，38（8）：1900-1907.

［3］THARMARASA R，KIRUBARAJAN T，SINHA A，et al.Decentralized sensor selection for large-scale multisensor-multitarget tracking［J］.In IEEE Transactions on Aerospace and Electronic Systems，2011，47（2）：1307-1324.

［4］劉先省.傳感器管理方法研究［D］.西安：西北工業(yè)大學，2000.

［5］唐東明.聚類分析及其應用研究［D］.成都：電子科技大學，2010.

［6］楊德剛.基于模糊C均值聚類的網(wǎng)絡入侵檢測算法［J］.計算機科學,2005，31（1）：86-87，91.

［7］劉欽.多傳感器組網(wǎng)協(xié)同跟蹤方法研究［D］.西安：西安電子科技大學，2013.

［8］任豐原，黃海寧，林闖.無線傳感器網(wǎng)絡［J］.軟件學報，2003，14（7）：1282-1291.

［9］李學明，李海瑞，薛亮，等.基于信息增益與信息熵的TFIDF 算法［J］.計算機工程，2012，38（8）：37-40.

［10］劉衛(wèi)東,劉洋，高立娥.基于凸組合和Bar-Shalom-Campo的航跡融合算法研究［J］.計算機工程與應用，2014，51（2）：49-53.

［11］李洋，杜立夫，禹春梅.一種基于復合模型的機動目標跟蹤算法［J］.四川兵工學報，2015，36（5）：127-132.

Distributed Multi-sensor Target Collaborative Tracking Algorithm under Communication Constraints

ZHAO Meng，ZUO Yan，LI Ming-di，GUO Bao-feng
（Institute of Information and Control，Hangzhou Dianzi University，Hangzhou 310018，China）

In a distributed multi-sensor target tracking system，the physical limitation of the local fusion center（LFC）（limited frequency channel，limited processor capacity）is considered，which can only receive the transmission data of a finite number of sensors.In addition，the way of information transmission will affect the service life of the sensor network，so this paper studies the distributed multi-sensor target tracking problem under communication constraints.In this paper，the distributed sensors in the monitoring area are firstly combined to a number of sub-networks，and then the optimal transmission path of sensor data is determined by minimizing the communication consumption costs.Moreover the local state of each sub-network is estimated.In the local fusion center，the sensor is selected based on the maximum distance and the maximum information increment.Finally the multisensor collaborative tracking is implemented by the global track fusion.Simulation results show the effectiveness of the proposed algorithm.

distributed，limited communication，shortest path planning，cluster，track fusion

TN953；E96

：A

10.3969/j.issn.1002-0640.2017.06.002

2016-05-08

：2016-06-09

國家自然科學基金（61004119，61174024，61375011）；浙江省自然科技基金資助項目（LY16F030009）

趙 猛（1990- ），男，河南息縣人，碩士研究生。研究方向：目標跟蹤和傳感器資源管理。

1002-0640（2017）06-0006-04