基于改進(jìn)自適應(yīng)聚類的無線傳感器目標(biāo)跟蹤算法*

苗 麗，元昌安，覃 曉

（1.廣西經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院，南寧 530021；2.廣西教育學(xué)院，南寧 530021；3.南寧師范大學(xué)，南寧 530001）

0 引言

隨著傳感器技術(shù)的發(fā)展，微機(jī)電系統(tǒng)和無線通信極大地促進(jìn)了現(xiàn)代無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSNs）的出現(xiàn)和發(fā)展。WSNs 通常由大量體積小、低功率、低成本的傳感器節(jié)點(diǎn)組成，這些節(jié)點(diǎn)配備小容量、不可充電電池。WSNs 將人類、機(jī)器和環(huán)境之間的交互引入一個(gè)新的范式，WSNs 的快速發(fā)展促使其在許多領(lǐng)域得到應(yīng)用，如環(huán)境監(jiān)測、生物醫(yī)學(xué)健康監(jiān)測和軍事目標(biāo)跟蹤和監(jiān)視等。目標(biāo)跟蹤是WSNs 中最基本的應(yīng)用之一。它的目的是檢測目標(biāo)的存在并對目標(biāo)位置進(jìn)行估計(jì)和持續(xù)跟蹤。為了提高目標(biāo)跟蹤的精度，需要兩個(gè)以上的傳感器節(jié)點(diǎn)跟蹤一個(gè)目標(biāo)，這就需要一個(gè)協(xié)調(diào)策略，同時(shí)，要實(shí)現(xiàn)高精度的跟蹤并保持能源效率是非常具有挑戰(zhàn)性的，通常存在傳感器節(jié)點(diǎn)能量有限，通信距離短，帶寬低，處理和存儲(chǔ)有限、大多數(shù)用于目標(biāo)跟蹤應(yīng)用的WSNs 是密集的、稀疏的，并且部署復(fù)雜的環(huán)境中、相鄰的傳感器節(jié)點(diǎn)通常具有相似的數(shù)據(jù)、各種各樣的噪聲降低了目標(biāo)的精度等問題。因此，如何盡可能地在降低能量消耗延長網(wǎng)絡(luò)生命周期的同時(shí)提高跟蹤精度是亟需解決的問題。

現(xiàn)有文獻(xiàn)中用于無線傳感器目標(biāo)跟蹤的算法和協(xié)議，基本上分為基于樹的、基于預(yù)測的和基于簇的跟蹤協(xié)議。在基于樹的跟蹤方法中，移動(dòng)目標(biāo)被傳感器節(jié)點(diǎn)包圍，當(dāng)目標(biāo)移動(dòng)時(shí)，動(dòng)態(tài)地配置樹來添加和刪除一些節(jié)點(diǎn)。文獻(xiàn)［5］中提出的基于動(dòng)態(tài)前饋生成樹的跟蹤算法，在預(yù)測目標(biāo)方向上形成前饋樹，目的是減少快速移動(dòng)目標(biāo)丟失的次數(shù)?；陬A(yù)測的方法，基于歷史數(shù)據(jù)來預(yù)測移動(dòng)對象的下一個(gè)位置。文獻(xiàn)［4］提出了一個(gè)基于預(yù)測的能源節(jié)約方案，該方案包括預(yù)測模型、喚醒機(jī)制和恢復(fù)機(jī)制。文獻(xiàn)［6］中提出了一種擴(kuò)展版本的KFs（EKFs）用于非線性目標(biāo)跟蹤。

基于聚類的跟蹤方法中，網(wǎng)絡(luò)被分成稱為簇的小子集，一般分為靜態(tài)跟蹤和動(dòng)態(tài)跟蹤兩種。在靜態(tài)方法中，簇是在網(wǎng)絡(luò)部署時(shí)靜態(tài)地構(gòu)建的。每個(gè)簇的屬性（例如簇的大小、它所覆蓋的區(qū)域以及它擁有的成員）是靜態(tài)的。文獻(xiàn)［7］（EET）通過提出一個(gè)事件驅(qū)動(dòng)的睡眠機(jī)制來降低能量消耗。但是，該算法存在調(diào)度消息帶來的通信開銷大的問題。在文獻(xiàn)［8］（GSCTA）定義了所有成員節(jié)點(diǎn)及其相關(guān)的leader 節(jié)點(diǎn)。雖然這種預(yù)先構(gòu)建的簇為目標(biāo)跟蹤帶來了簡單性，但由于不同簇中的節(jié)點(diǎn)無法相互協(xié)作，對成員關(guān)系的約束會(huì)導(dǎo)致容錯(cuò)問題。在動(dòng)態(tài)方法中，當(dāng)事件發(fā)生時(shí)就會(huì)觸發(fā)簇的構(gòu)造，并且簇的屬性沒有限制?，F(xiàn)有的基于動(dòng)態(tài)簇的目標(biāo)跟蹤方法可分為分布式預(yù)測跟蹤、自適應(yīng)動(dòng)態(tài)簇跟蹤協(xié)議、動(dòng)態(tài)簇頭選擇與條件再聚類、自適應(yīng)簇頭聚類算法。文獻(xiàn)［9］提出了一種基于節(jié)點(diǎn)和簇頭分離算法的運(yùn)動(dòng)目標(biāo)分布式預(yù)測跟蹤協(xié)議，算法為了保證能源效率和可擴(kuò)展性，基于需要選擇聚類形式。簇頭使用一個(gè)目標(biāo)描述符來識別目標(biāo)并預(yù)測它的下一個(gè)位置。文獻(xiàn)［10］提出了一種分布式的、可擴(kuò)展的基于簇的無線傳感器網(wǎng)絡(luò)移動(dòng)目標(biāo)跟蹤協(xié)議，該協(xié)議選擇距離目標(biāo)預(yù)測位置最近的傳感器節(jié)點(diǎn)作為簇頭。簇頭根據(jù)數(shù)據(jù)有用性和能量消耗相結(jié)合的最優(yōu)選擇函數(shù)，形成具有合適傳感器節(jié)點(diǎn)數(shù)的簇。文獻(xiàn)［11］允許每個(gè)傳感器節(jié)點(diǎn)根據(jù)數(shù)據(jù)檢測和傳輸將消耗的能量來確定自己的激勵(lì)。該激勵(lì)值表示當(dāng)新簇頭持續(xù)存在時(shí)，傳感器節(jié)點(diǎn)不考慮簇頭的輪數(shù)。當(dāng)前簇頭節(jié)點(diǎn)根據(jù)每個(gè)傳感器節(jié)點(diǎn)建議的激勵(lì)機(jī)制重新調(diào)度下一輪將使用的簇頭序列，從而減少能量消耗。自適應(yīng)簇頭聚類算法被提出，以解決資源約束和跟蹤精度之間的權(quán)衡，通過利用聚類架構(gòu)和可行的功率控制機(jī)制來實(shí)現(xiàn)。然而，自適應(yīng)簇頭聚類算法中主節(jié)點(diǎn)的選擇機(jī)制僅基于檢測傳感器節(jié)點(diǎn)與移動(dòng)目標(biāo)之間的距離，不考慮節(jié)點(diǎn)的能量以及節(jié)點(diǎn)到基站的距離。事實(shí)上，這可能會(huì)導(dǎo)致傳感器節(jié)點(diǎn)的提前死亡，從而降低網(wǎng)絡(luò)的生存期。該算法的另一個(gè)缺點(diǎn)是當(dāng)目標(biāo)速度提高到10 m/s 以上時(shí)，隨著目標(biāo)的快速移動(dòng)，形成的簇頻繁地偏離目標(biāo)，導(dǎo)致跟蹤誤差急劇增加。

針對這些問題，本文提出改進(jìn)算法來優(yōu)化自適應(yīng)聚類算法。該算法首先采用動(dòng)態(tài)聚類算法，通過考慮節(jié)點(diǎn)剩余能量、傳感器節(jié)點(diǎn)到匯聚的距離和傳感器節(jié)點(diǎn)到運(yùn)動(dòng)目標(biāo)的距離3 個(gè)參數(shù)，最大限度地減少簇頭與基站之間的遠(yuǎn)程通信，從而節(jié)約網(wǎng)絡(luò)能量，延長網(wǎng)絡(luò)壽命，降低目標(biāo)漏失概率。在此基礎(chǔ)上，加入預(yù)測機(jī)制，采用線性預(yù)測的方法預(yù)測運(yùn)動(dòng)目標(biāo)的下一個(gè)位置，繼而根據(jù)得到的預(yù)測誤差，改變集群的大小和形狀，從而減少參與跟蹤過程的傳感器節(jié)點(diǎn)數(shù)量，節(jié)約網(wǎng)絡(luò)能量，保持合理的跟蹤精度。仿真實(shí)驗(yàn)對網(wǎng)絡(luò)能源消耗、跟蹤誤差和網(wǎng)絡(luò)壽命進(jìn)行分析，實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有算法相比，該算法在考慮隨機(jī)運(yùn)動(dòng)速度的情況下仍能準(zhǔn)確地跟蹤目標(biāo)，且能耗更低，大大延長了網(wǎng)絡(luò)的生命周期，從而表明本文所提算法的有效性和可行性。

1 系統(tǒng)模型建立

1.1 無線電波能量和信道傳播模型

在本文中，假設(shè)使用與文獻(xiàn)［13］相同的無線電能量模型。傳感器無線電能量模型由微控制器處理、無線電發(fā)射和無線電接收組成。在發(fā)射機(jī)中，能量在運(yùn)行無線電電子設(shè)備和功率放大器時(shí)消耗，在接收機(jī)中，能量在運(yùn)行無線電電子設(shè)備時(shí)消耗。

在無線信道中，電磁波的傳播可以被建模為發(fā)射機(jī)和接收機(jī)之間距離的冪律函數(shù)。此外，接收功率隨著發(fā)射機(jī)和接收機(jī)之間距離的增加而減小。在模擬中，自由空間（視線直線）和多徑衰落（雙射線地面）信道模型的使用取決于發(fā)射和接收之間的距離。簡而言之，如果發(fā)射機(jī)和接收機(jī)之間的距離小于一定的交叉距離（dcrossover），則使用自由空間傳播模型（d衰減）；否則，采用雙射線地面?zhèn)鞑ツＰ停╠衰減）。因此，k 比特?cái)?shù)據(jù)包傳輸距離d 所需的總能量計(jì)算如下：

1.2 系統(tǒng)假設(shè)

對于本文所提出的算法，對網(wǎng)絡(luò)模型的假設(shè)如下：1）無線傳感器網(wǎng)絡(luò)由大量的傳感器節(jié)點(diǎn)和簇節(jié)點(diǎn)構(gòu)成；2）傳感器節(jié)點(diǎn)均勻分布在固定長度距離的正方形網(wǎng)格上；3）所有傳感器節(jié)點(diǎn)具有相同的處理能力；4）簇節(jié)點(diǎn)位于無線傳感器網(wǎng)絡(luò)的中間；5）傳感器和基站是靜止的，傳感器節(jié)點(diǎn)知道它們的位置坐標(biāo)；6）每個(gè)傳感器節(jié)點(diǎn)具有相同的傳感和通信能力，所有節(jié)點(diǎn)的時(shí)鐘是同步的；7）傳感器節(jié)點(diǎn)使用雙向鏈路在彼此之間和接收器之間中繼數(shù)據(jù)；8）目標(biāo)的運(yùn)動(dòng)行為是隨機(jī)選擇的，每個(gè)傳感器節(jié)點(diǎn)一次只能檢測到一個(gè)目標(biāo)。

2 本文提出的算法

2.1 改進(jìn)的簇頭自適應(yīng)算法

為更有效、更精確地跟蹤移動(dòng)目標(biāo)，本文提出了改進(jìn)的簇頭自適應(yīng)算法。該算法考慮了一個(gè)基于動(dòng)態(tài)簇的架構(gòu)，其中簇是根據(jù)移動(dòng)目標(biāo)的存在而動(dòng)態(tài)形成的。算法的操作分為兩組，一組低能量適應(yīng)聚類層。每一輪有兩個(gè)階段：建立階段和穩(wěn)定階段。在設(shè)置階段，根據(jù)選舉技術(shù)選擇簇頭，將在本節(jié)中進(jìn)一步討論。在穩(wěn)態(tài)階段，簇中的每個(gè)成員節(jié)點(diǎn)將數(shù)據(jù)傳輸?shù)狡浯仡^，簇頭再將數(shù)據(jù)聚合并報(bào)告給基站。為了減少能量消耗，穩(wěn)態(tài)階段通常較長，然而，輪轉(zhuǎn)時(shí)間是由基站在網(wǎng)絡(luò)部署的初始時(shí)刻指定的。改進(jìn)算法包括以下3 個(gè)階段：初始階段、目標(biāo)跟蹤階段和主選階段。

2.1.1 初始階段

在此階段，傳感器節(jié)點(diǎn)均勻分布在網(wǎng)絡(luò)區(qū)域內(nèi)。在初始時(shí)刻，所有傳感器節(jié)點(diǎn)都處于睡眠狀態(tài)。它們只是定期喚醒并在短時(shí)間內(nèi)（設(shè)置時(shí)間）進(jìn)行檢測。如果什么都沒有發(fā)生，那么它們將在另一段時(shí)間內(nèi)保持睡眠狀態(tài)。如果任何傳感器節(jié)點(diǎn)檢測到目標(biāo)，則啟動(dòng)目標(biāo)跟蹤過程。

2.1.2 目標(biāo)跟蹤階段

在這個(gè)階段，第1 個(gè)探測到目標(biāo)的節(jié)點(diǎn)將使用多址訪問（CSMA）協(xié)議向網(wǎng)絡(luò)中其他節(jié)點(diǎn)或者更遠(yuǎn)的節(jié)點(diǎn)廣播一條廣告消息。此消息使檢測目標(biāo)的其他節(jié)點(diǎn)知道該節(jié)點(diǎn)被選為第1 輪的主節(jié)點(diǎn)，從而阻止這些節(jié)點(diǎn)發(fā)送其他廣告消息。因此，主節(jié)點(diǎn)發(fā)送請求信息給其他所有與主節(jié)點(diǎn)一跳距離的鄰居節(jié)點(diǎn)，將其作為從節(jié)點(diǎn)并直接形成一個(gè)簇。每個(gè)相鄰的傳感器節(jié)點(diǎn)發(fā)送1 個(gè)加入請求消息到主節(jié)點(diǎn)，其中包含位置信息，通知主節(jié)點(diǎn)將它作為從節(jié)點(diǎn)。簇形成后，主節(jié)點(diǎn)建立一個(gè)時(shí)分多址（TDMA）計(jì)劃，并相應(yīng)地發(fā)送給它的從節(jié)點(diǎn)，這一機(jī)制避免了發(fā)送消息的沖突。在所有從節(jié)點(diǎn)都知道TDMA 調(diào)度之后，每個(gè)檢測目標(biāo)的從節(jié)點(diǎn)會(huì)找到它的剩余能量并使用到TOA 方法計(jì)算它到目標(biāo)的距離。該數(shù)據(jù)在分配的TDMA 時(shí)隙通過從節(jié)點(diǎn)數(shù)據(jù)消息發(fā)送到主節(jié)點(diǎn)。另一方面，主節(jié)點(diǎn)在從節(jié)點(diǎn)消息中獲得數(shù)據(jù)且聚合自己的數(shù)據(jù)，從而計(jì)算探測傳感器節(jié)點(diǎn)與基站之間的距離。主協(xié)議基本維護(hù)3 個(gè)列表：第1 個(gè)列表包含目標(biāo)到檢測傳感器節(jié)點(diǎn)的距離；第2 種包含檢測傳感器節(jié)點(diǎn)的剩余能量；第3 個(gè)包含所述檢測傳感器節(jié)點(diǎn)與接收節(jié)點(diǎn)之間的距離。主協(xié)議使用這些列表根據(jù)以下公式來查找權(quán)重最大的傳感器節(jié)點(diǎn)：

在weight表示檢測待選為主節(jié)點(diǎn)的傳感器節(jié)點(diǎn)的權(quán)重，E表示檢測傳感器節(jié)點(diǎn)的剩余能量，D表示檢測傳感器節(jié)點(diǎn)到基站的距離，D表示檢測傳感器節(jié)點(diǎn)到目標(biāo)的距離。如果當(dāng)前的主節(jié)點(diǎn)仍然擁有最高的權(quán)值，那么在下一輪中它仍將是主節(jié)點(diǎn)，并重新分配相同的從節(jié)點(diǎn)。否則，必須選擇一個(gè)新的主節(jié)點(diǎn)。此外，在主節(jié)點(diǎn)中維護(hù)的第1個(gè)列表在定位算法中用于估計(jì)目標(biāo)位置，稍后將對此進(jìn)行討論。估計(jì)目標(biāo)位置后，主節(jié)點(diǎn)將估計(jì)的目標(biāo)位置記錄在目標(biāo)存檔中，然后通過簇節(jié)點(diǎn)消息發(fā)送給基站。

2.1.3 主選舉階段

主節(jié)點(diǎn)的選擇非常重要，也就是說，它不僅僅影響目標(biāo)跟蹤的精度，同時(shí)影響簇的能量效率。因此，整個(gè)網(wǎng)絡(luò)的生命周期可能會(huì)受到嚴(yán)重影響。在這個(gè)階段，主協(xié)議選擇擁有最高權(quán)值的節(jié)點(diǎn)作為新的主節(jié)點(diǎn)。當(dāng)前的主節(jié)點(diǎn)向新選擇的主節(jié)點(diǎn)發(fā)送一個(gè)MigrateMaster 消息，其中包含目標(biāo)位置歷史記錄。然后由新的主節(jié)點(diǎn)執(zhí)行從節(jié)點(diǎn)邀請、目標(biāo)定位以及向接收器發(fā)送目標(biāo)位置等操作。

下面顯示了在選擇主節(jié)點(diǎn)時(shí)使用的參數(shù)的描述：

1）節(jié)點(diǎn)剩余能量。任何節(jié)點(diǎn)的剩余能量都是基于節(jié)點(diǎn)在發(fā)送和接收過程中消耗的能量。因此，每輪傳感器節(jié)點(diǎn)的平均能量計(jì)算公式如下：

主節(jié)點(diǎn)消耗更多的能量，因?yàn)樗鼤?huì)傳送3 類信息，包括InviteSlave，SinkData 和MigrtateMaster。第1個(gè)用于邀請從服務(wù)器，第2 個(gè)用于向接收發(fā)送目標(biāo)估計(jì)位置，最后一個(gè)用于將主節(jié)點(diǎn)遷移到新的主節(jié)點(diǎn)。另一方面，從節(jié)點(diǎn)傳輸兩種消息，即JoinRequest和slavedata。第1 個(gè)用于通知主節(jié)點(diǎn)，它將作為簇中的從節(jié)點(diǎn)，另一個(gè)用于向主節(jié)點(diǎn)發(fā)送從數(shù)據(jù)。據(jù)此，主節(jié)點(diǎn)和從節(jié)點(diǎn)兩類傳感器節(jié)點(diǎn)的剩余能量可以表示為：

其中，E和E分別表示主從節(jié)點(diǎn)的剩余能量，（n）表示從節(jié)點(diǎn)的數(shù)量，d、d和d分別表示主節(jié)點(diǎn)與從節(jié)點(diǎn)、接收器和新選出的主節(jié)點(diǎn)間的距離。

2）探測傳感器節(jié)點(diǎn)與匯聚節(jié)點(diǎn)之間的距離，利用歐幾里得距離公式：

其中，點(diǎn)（x，y）表示檢測傳感器節(jié)點(diǎn)的位置，（x，y）表示接收器的位置。

3）為了計(jì)算運(yùn)動(dòng)目標(biāo)與檢測傳感器節(jié)點(diǎn)之間的距離，本文采用了TOA 方法。在本文提出的算法中，TOA 表示信號從檢測傳感器節(jié)點(diǎn)到運(yùn)動(dòng)目標(biāo)的時(shí)間。因此，考慮到信號速度約為340 m/s，目標(biāo)與探測傳感器節(jié)點(diǎn)的距離可直接根據(jù)式（11）計(jì)算：

在一些應(yīng)用中，可能會(huì)有障礙阻止傳感器節(jié)點(diǎn)和目標(biāo)之間的直接視線。因此，TOA 的讀數(shù)可能受到影響。然而，在IAH 中所采用的定位算法與簇頭自適應(yīng)聚類算法相同，主要依賴于圖1 所示的圓交原理。定位算法利用式（11）的結(jié)果，結(jié)合檢測傳感器節(jié)點(diǎn)的位置，得到一組圓方程：

圖1 利用圓交求目標(biāo)估計(jì)位置

在（a，b）的位置檢測傳感器節(jié)點(diǎn)，每個(gè)傳感器節(jié)點(diǎn)在網(wǎng)絡(luò)部署時(shí)知道它的位置，r是檢測傳感器節(jié)點(diǎn)和移動(dòng)目標(biāo)之間的距離，n 代表所需的檢測傳感器節(jié)點(diǎn)且數(shù)量必須至少有3 個(gè)。則求解這組方程，得到目標(biāo)（x，y）的估計(jì)位置。

在本文所提算法中，傳感器節(jié)點(diǎn)一般按照圖2 所示的狀態(tài)轉(zhuǎn)換模型工作。根據(jù)簇頭自適應(yīng)頭算法的定義，每個(gè)傳感器節(jié)點(diǎn)應(yīng)該處于以下4 種狀態(tài)之一：主、從、監(jiān)聽或休眠。然而，在本文提出的算法中，除了接收和發(fā)送消息的能力之外，接收者或從者狀態(tài)還可以檢測到其范圍內(nèi)的目標(biāo)。該傳感器處于偵聽狀態(tài)，可以檢測到其范圍內(nèi)的目標(biāo)，而不是其從鄰近傳感器接收消息的能力。當(dāng)處于睡眠狀態(tài)時(shí)，傳感器無法檢測目標(biāo)或接收任何消息。因此，這種狀態(tài)更省電。

圖2 算法中傳感器節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)移模型

2.2 基于預(yù)測機(jī)制的的簇頭自適應(yīng)算法

目標(biāo)的運(yùn)動(dòng)是不確定的但通常遵循一定的物理規(guī)律?；陬A(yù)測的方法能有助于優(yōu)化能量效率和跟蹤精度。因此，本文將基于預(yù)測的方法與2.1 節(jié)提出的自適應(yīng)算法相結(jié)合，以提高算法的性能?；陬A(yù)測的方法用于預(yù)測運(yùn)動(dòng)目標(biāo)的下一個(gè)位置。利用了這一點(diǎn)，提出了一種節(jié)能的方法，在一定的誤差閾值的基礎(chǔ)上，可以有效地將形成的簇中激活的傳感器節(jié)點(diǎn)數(shù)量減少一半。除此之外，所提算法為簇頭的選擇公式增加了一個(gè)新的維度，包括節(jié)點(diǎn)與預(yù)測位置的距離。本文采用線性預(yù)測方法，這種機(jī)制使用目標(biāo)的當(dāng)前和以前的位置來預(yù)測它的下一個(gè)位置。整個(gè)預(yù)測過程分為5 個(gè)步驟，這5 個(gè)步驟都是由主節(jié)點(diǎn)完成的。假設(shè)當(dāng)前目標(biāo)位置為時(shí)刻（t），則

步驟1：根據(jù)當(dāng)前位置（x，y）和以前的位置（x，y）獲得當(dāng)前速度v 和方向θ，通過MigraMaster 消息發(fā)送，計(jì)算如下：

D表示預(yù)測位置和檢測節(jié)點(diǎn)之間的距離。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 參數(shù)設(shè)置

在Windows7 環(huán)境下的Intel core 2 Duo 2.20GHz和4 GB 內(nèi)存上進(jìn)行仿真實(shí)驗(yàn)。在本實(shí)驗(yàn)中，（24×24）傳感器節(jié)點(diǎn)均勻分布在230 m×230 m 的二維正方形網(wǎng)格上。接收器位于位置（x=115，y=115），無線電電子能量設(shè)置為50 nj/bit，其中，無線電發(fā)射機(jī)能量設(shè)置為當(dāng)距離小于d時(shí)，值為10 pj/bit/m2，如果距離大于d時(shí)，值為0.001 3 pj/bit/m2。相鄰節(jié)點(diǎn)之間的定長距離設(shè)置為10 m。每個(gè)節(jié)點(diǎn)的感知范圍為10×√2 m。每個(gè)節(jié)點(diǎn)初始為0.5 j 的能量。在本文提出的第1 個(gè)算法（改進(jìn)的簇頭自適應(yīng)算法）的仿真模型中，簇由8 個(gè)從節(jié)點(diǎn)和1 個(gè)位于集群中心的主節(jié)點(diǎn)組成。在第2 種改進(jìn)的算法中（基于預(yù)測機(jī)制的的簇頭自適應(yīng)算法），簇由1 個(gè)主節(jié)點(diǎn)，位于簇的中心，通過一定誤差門限選擇4 個(gè)或者8 個(gè)從節(jié)點(diǎn)。在兩種算法中簇的形狀均為正方形，用于處理簇壓蓋或者主節(jié)點(diǎn)與從節(jié)點(diǎn)之間的通信距離。

實(shí)驗(yàn)證明數(shù)據(jù)傳輸比數(shù)據(jù)處理和局部感知會(huì)消耗更多的能量。因此，在設(shè)計(jì)目標(biāo)跟蹤算法時(shí)必須充分考慮。在本文提出的算法中，傳感器通過5個(gè)控制消息相互通信：InviteSlave、JointRequest、SlaveData、SinkData 和Migratemaster 消息。這些消息的格式基本上由以下5 個(gè)部分組成：頭部用于區(qū)分控制消息和可能的上層使用，距離讀數(shù)描述為被檢測目標(biāo)到檢測節(jié)點(diǎn)的距離，目標(biāo)位置歷史記錄讀取顯示主節(jié)點(diǎn)上先前接收到的目標(biāo)位置的歷史記錄，預(yù)測讀數(shù)表示目標(biāo)的預(yù)測位置，剩余能量部分表示從節(jié)點(diǎn)的剩余能量。最后，主ID、從ID 和接收ID 分別表示主、從和接收標(biāo)識符。利用仿真實(shí)驗(yàn)來評估本文算法的性能，主要使用3 個(gè)性能指標(biāo)，包括能源消耗、網(wǎng)絡(luò)壽命和跟蹤誤差。它們的定義如下：

1）能量消耗：表示仿真開始后傳感器節(jié)點(diǎn)之間通信所消耗的總能量。

2）網(wǎng)絡(luò)生存期：它表示從最初部署到網(wǎng)絡(luò)中第1 個(gè)節(jié)點(diǎn)死亡的時(shí)間，以輪為單位計(jì)算。

3）跟蹤誤差：得到的估計(jì)位置與實(shí)際位置之間的歐氏距離的平均值，用于測量跟蹤誤差。

3.2 仿真結(jié)果及分析

本文使用多種場景來驗(yàn)證所提算法的性能。首先，研究了增加傳感器密度對能量消耗的影響，增加傳感器密度意味著減少所使用的固定長度的距離。其次，研究了改變傳感器密度對跟蹤誤差的影響。第三，對比了不同的目標(biāo)速度對跟蹤誤差的影響。第四，研究了擴(kuò)大網(wǎng)絡(luò)規(guī)模對能耗的影響。最后，研究了當(dāng)初始能量變化時(shí)網(wǎng)絡(luò)的生命周期。將本文所提算法與文獻(xiàn)［12］所提簇頭自適應(yīng)算法進(jìn)行比較，下文中Algorithm1 表示文獻(xiàn)［12］所提算法，Algorithm2 表示本文所提第1 種算法，Algorithm3 表示本文所提第2 種算法。

3.2.1 能量消耗與傳感器密度關(guān)系分析

圖3 給出了文獻(xiàn)［12］所提算法、本文所提算法1 和本文所提算法2 的能量消耗與傳感器密度的對比。在這個(gè)圖中，網(wǎng)絡(luò)中的傳感器密度從361 個(gè)節(jié)點(diǎn)到2 025 個(gè)節(jié)點(diǎn)不等。正如預(yù)期的那樣，所有算法的能量消耗都隨著環(huán)境密度的增加而增加，因?yàn)榄h(huán)境之間的距離越來越近，而形成環(huán)境變化趨勢的可能性也在增加。因此，檢測目標(biāo)的傳感器數(shù)量增加，從而消耗更多的能量。相對于文獻(xiàn)［12］所提算法，本文所提第1 種算法的能耗降低了15%。實(shí)際上，這是由于在選擇主節(jié)點(diǎn)時(shí)采用了一種新的準(zhǔn)則，主要有助于縮短主節(jié)點(diǎn)和匯聚節(jié)點(diǎn)之間的通信距離。為了滿足這個(gè)條件，每個(gè)從臺只向主節(jié)點(diǎn)發(fā)送1 條控制消息，這足以估計(jì)目標(biāo)位置并選擇新的主臺。因此，交換的控制消息的數(shù)量保持在較低水平。如圖3 所示，在考慮所有密度值時(shí)，本文所提第2 種算法在能量消耗方面優(yōu)于其他所有算法。相對于本文所提第1 種算法和文獻(xiàn)［12］所提算法，本文所提第2 種算法的能耗分別降低了28%和43%。

圖3 算法的能量消耗與傳感器密度的對比

3.2.2 跟蹤誤差與傳感器密度關(guān)系

在此情況下，通過仿真研究了傳感器密度對跟蹤誤差的影響。圖4 給出了文獻(xiàn)［12］所提算法、本文所提算法1 和本文所提算法2 的跟蹤誤差與傳感器密度的變化關(guān)系圖。由跟蹤誤差的結(jié)果可以清楚地看到，文獻(xiàn)［12］所提算法在目標(biāo)低速運(yùn)動(dòng)（0 ～10 m/s）的約束下，跟蹤誤差取得了有趣的結(jié)果。事實(shí)上，主選過程只取決于目標(biāo)的檢測。隨著目標(biāo)移動(dòng)的越來越快，形成的簇經(jīng)常會(huì)錯(cuò)過目標(biāo)，這反過來會(huì)導(dǎo)致罕見的簇形成，從而觸發(fā)跟蹤誤差的急劇增加。另一方面，本文所提算法1 和本文所提算法2的跟蹤誤差（與門限45°）算法是穩(wěn)定的。換句話說，目標(biāo)速度的任何提高都不會(huì)對跟蹤誤差產(chǎn)生太大的影響，因?yàn)檫x擇新節(jié)點(diǎn)采用了一種新的程序，如前所述，其中組合了多個(gè)參數(shù)，并相應(yīng)地考慮了這些參數(shù)的最高權(quán)重。因此，降低了目標(biāo)丟失的概率，從而提高了跟蹤精度。本文提出的算法對目標(biāo)速度在［10 m/s～16 m/s］范圍內(nèi)的跟蹤誤差提高了近52%。隨著傳感器密度的增加，傳感器之間的距離越來越近，所以所有算法的跟蹤誤差都比較小，并且表現(xiàn)出相似的行為。這使得對目標(biāo)的定位更加準(zhǔn)確，從而使得動(dòng)態(tài)形成的簇偏離目標(biāo)的概率越來越低。

圖4 算法的跟蹤誤差與傳感器密度的對比

3.2.3 跟蹤錯(cuò)誤與目標(biāo)速度的對比

圖5 描述了所有可比較算法提高目標(biāo)速度對比。

圖5 算法的跟蹤誤差與目標(biāo)速度對比

3.2.4 能源消耗與網(wǎng)絡(luò)大小的對比

圖6 描述了在考慮上述所有算法的情況下，增加網(wǎng)絡(luò)規(guī)模對能耗的影響。網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)密度保持不變（0.011 5 sensor/m2），而網(wǎng)絡(luò)大小從（100 m×100 m）到（350 m×350 m）不等。首先，所有算法都具有遞增行為，隨著網(wǎng)絡(luò)規(guī)模的增大，傳感器節(jié)點(diǎn)之間的距離越來越遠(yuǎn)，數(shù)據(jù)傳輸?shù)木嚯x也越來越遠(yuǎn)，從而導(dǎo)致了大量能量的消耗。其次，本文所提兩種算法的性能優(yōu)于自適應(yīng)頭算法。因?yàn)橹鞴?jié)點(diǎn)的選擇過程得到了改進(jìn)，這充分有助于在與基站通信時(shí)保持使用自由空間模型而不是多徑衰落信道。最后，可以進(jìn)一步觀察到，本文所提第2 種算法在閥值為45°時(shí)，在能源消耗方面優(yōu)于所有其他算法，分別減少了27%和40%。

圖6 算法的能耗與網(wǎng)絡(luò)維數(shù)對比

3.2.5 網(wǎng)絡(luò)生命周期與初始能量

圖7 描述了在網(wǎng)絡(luò)生命周期中使用不同初始能量的結(jié)果。正如預(yù)期的那樣，隨著初始能量的增加，所有算法都趨向于擁有更長的生命周期。事實(shí)上，增加傳感器節(jié)點(diǎn)的初始能量可以使其工作時(shí)間更長，從而使網(wǎng)絡(luò)壽命更長。結(jié)果表明，本文所提算法的網(wǎng)絡(luò)生存期比文獻(xiàn)［12］所提算法的網(wǎng)絡(luò)生存期要高。這是由于選擇方法縮短了主節(jié)點(diǎn)和接收節(jié)點(diǎn)之間的通信距離。這樣，在主傳輸期間消耗的能量就減少了，從而使網(wǎng)絡(luò)的生命周期更長。這種新的選擇方法不僅縮短了通信距離，而且通過將傳感器節(jié)點(diǎn)的剩余能量作為參數(shù)插入到選擇準(zhǔn)則中來平衡傳感器節(jié)點(diǎn)的能量消耗。因此，主節(jié)點(diǎn)在網(wǎng)絡(luò)中的大多數(shù)傳感器節(jié)點(diǎn)之間進(jìn)行旋轉(zhuǎn)。換句話說，不會(huì)頻繁地選擇同一個(gè)主節(jié)點(diǎn)。事實(shí)上，這可以降低傳感器節(jié)點(diǎn)早死的可能性，從而增加網(wǎng)絡(luò)的生命周期。同時(shí)隨著初始能量的增加，本文提出的算法比文獻(xiàn)［12］所提算法的輪數(shù)急劇增加，直到第1 個(gè)節(jié)點(diǎn)死亡為止。這是合理的，因?yàn)樗峁┝烁叩哪茉葱省膱D7 中可以明顯看出，本文提出的算法的網(wǎng)絡(luò)壽命比文獻(xiàn)［12］所提算法至少提高了70%。

圖7 網(wǎng)絡(luò)生命周期與節(jié)點(diǎn)初始能量的關(guān)系

綜上，本文所提出的算法通過優(yōu)化主節(jié)點(diǎn)的選擇和減少參與跟蹤過程的傳感器節(jié)點(diǎn)的數(shù)量，達(dá)到了更好的能效和跟蹤質(zhì)量。具體來說，第1 種算法增強(qiáng)了主節(jié)點(diǎn)的選擇機(jī)制，考慮了節(jié)點(diǎn)剩余能量、傳感器節(jié)點(diǎn)到匯聚的距離和傳感器節(jié)點(diǎn)到運(yùn)動(dòng)目標(biāo)的距離3 個(gè)參數(shù)。在第2 種算法中，采用了一種基本影響主選舉過程和激活傳感器數(shù)量的預(yù)測方法。換句話說，主節(jié)點(diǎn)的選擇受1 個(gè)附加參數(shù)的影響超過了前面3 個(gè)描述節(jié)點(diǎn)與預(yù)測位置的距離的參數(shù)。根據(jù)所采用的誤差閾值，參與簇形成的傳感器數(shù)量可能會(huì)下降到4 個(gè)菱形（而不是8 個(gè)）。在能量效率和跟蹤質(zhì)量方面表明，在考慮不同網(wǎng)絡(luò)密度、目標(biāo)速度和網(wǎng)絡(luò)維數(shù)的情況下，本文提出的算法取得了令人滿意的性能，大大優(yōu)于文獻(xiàn)［12］所提算法。此外，目標(biāo)速度的增加對兩種算法的跟蹤誤差影響不大，而在自適應(yīng)頭聚類算法中，當(dāng)目標(biāo)速度增加超過10 m/s 時(shí)，跟蹤誤差急劇增加。本文提出的算法保證了網(wǎng)絡(luò)的可擴(kuò)展性，因?yàn)榧词咕W(wǎng)絡(luò)規(guī)模越來越大，它們也能很好地執(zhí)行。

4 結(jié)論

本文針對無線傳感器網(wǎng)絡(luò)目標(biāo)跟蹤中跟蹤精度與傳感器節(jié)能問題進(jìn)行研究，提出了基于預(yù)測的自適應(yīng)頭聚類算法，該算法首先采用動(dòng)態(tài)聚類算法，通過考慮節(jié)點(diǎn)剩余能量、傳感器節(jié)點(diǎn)到匯聚的距離和傳感器節(jié)點(diǎn)到運(yùn)動(dòng)目標(biāo)的距離3 個(gè)參數(shù)，最大限度地減少簇頭與簇sink 之間的遠(yuǎn)程通信，從而節(jié)約網(wǎng)絡(luò)能量，延長網(wǎng)絡(luò)壽命，降低目標(biāo)漏失概率。在此基礎(chǔ)上，加入預(yù)測機(jī)制，采用線性預(yù)測的方法預(yù)測運(yùn)動(dòng)目標(biāo)的下一個(gè)位置，繼而根據(jù)得到的預(yù)測誤差，改變集群的大小和形狀，從而減少參與跟蹤過程的傳感器節(jié)點(diǎn)數(shù)量，節(jié)約網(wǎng)絡(luò)能量，保持合理的跟蹤精度。仿真實(shí)驗(yàn)對網(wǎng)絡(luò)能源消耗、跟蹤誤差和網(wǎng)絡(luò)壽命進(jìn)行分析，實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有算法相比，該算法在考慮隨機(jī)運(yùn)動(dòng)速度的情況下仍能準(zhǔn)確地跟蹤目標(biāo)，且能耗更低，大大延長了網(wǎng)絡(luò)的生命周期，從而表明本文所提算法的有效性和可行性。