通訊作者，Email：zhangghui1230@163.com（衡陽師范學院數(shù)學與計算科學系， 中國 衡陽421002）

摘要針對目標搜索傳感器調(diào)度問題，歸納總結(jié)了基于Shannon熵、KullbackLeibler熵和Rényi熵3種信息測度以及全局和局部兩種信息增益，衍生出6種基于信息增益的搜索調(diào)度模型.通過數(shù)值仿真計算對比分析6種基于信息增益的搜索調(diào)度模型的目標捕獲性能，結(jié)果表明基于3種信息測度的搜索調(diào)度模型對目標的捕獲性能差別很小，而基于全局信息增益的搜索調(diào)度模型性能更優(yōu)，仿真結(jié)果可為工程實踐中傳感器搜索調(diào)度方法的優(yōu)選提供參考.

關(guān)鍵詞搜索調(diào)度;熵;信息增益;累積捕獲概率

中圖分類號TN9111文獻標識碼A文章編號10002537（2015）06007805

Comparison of the Information Gain Based Sensor Search Scheduling Models

ZHANG ?Guohui*

（Department of Mathematics and Computational Science， Hengyang Normal ?University， Hengyang 421002， China）

AbstractTo deal with the problem of sensor search scheduling， three typical information measures based on Shannon entropy， KullbackLeibler entropy and Rényi entropy are summarized. Additionally， based on both of the ?global information gain and local information gain， 6 kinds of search scheduling models are developed. The acquisition performance of all information based scheduling models are compared through simulation. The results indicate that， as for the three typical information measures， the acquisition performance of the search scheduling methods shows the same rules， while search scheduling model based on the global information gain shows better performance. The simulation results can be used as the reference for the search scheduling method in project.

Key wordssearch scheduling; entropy; information gain; cumulative acquisition probability

目標最優(yōu)搜索理論起源于二戰(zhàn)時期美國海軍的反潛作戰(zhàn)[1]，其動機是增強飛行員對上潛到水面充電的潛艇的檢測能力.Koopman[2]對搜索論進行了系統(tǒng)的總結(jié)，給出最優(yōu)搜索問題的3個基本元素：目標位置先驗信息、搜索資源與檢測概率之間的關(guān)系方程及搜索資源約束，并分別從運動學基礎(chǔ)、目標檢測及搜索資源最優(yōu)配置角度對搜索理論進行了闡述.學者們針對目標最優(yōu)搜索理論和相應的傳感器搜索調(diào)度方法進行了大量研究，涉及雷達[2]、聲納[3]、可見光[4]、紅外[5]、射電望遠鏡等主/被動探測設(shè)備，所建立的搜索調(diào)度模型包括累積發(fā)現(xiàn)概率模型[6]、信息增益模型[2]、自適應搜索模型[7]、分區(qū)搜索模型[8]等，這些研究成果已應用于許多不同的領(lǐng)域，如：水下目標或空間目標搜索、地面或海面搜救、地質(zhì)勘探、信息分配、軍事目標檢測等.

Marcum [2]于1947年建立了累積發(fā)現(xiàn)概率模型，之后該模型被廣泛應用于最優(yōu)搜索，分別產(chǎn)生了最大化累積發(fā)現(xiàn)概率準則、最大化累積檢測概率準則和最小化漏警概率準則，即在相同的時間和能量消耗下，使得傳感器的累積發(fā)現(xiàn)（檢測）概率最大化或使其累積漏警概率最小化.Keith[2]最早將信息論引入搜索調(diào)度領(lǐng)域，針對雷達搜索目標問題，提出最大化分辨力增益準則.Mark[910]針對地雷目標檢測問題，從不同角度建立了兩種目標觀測不確定模型，并基于Keith的分辨力增益最大化準則，提出相應的傳感器搜索調(diào)度方法.Mark[10]、王博[11]分別從理論上證明了搜索單元數(shù)N=2和N∈Z+條件下兩種無調(diào)度搜索方法（順序搜索和隨意搜索）的性能.

信息增益模型作為一種常用的傳感器搜索調(diào)度模型，通常采用Shannon熵[2]、KullbackLeibler熵[9]和Rényi熵[12]等信息測度，以最大化信息增益準則確定傳感器對各區(qū)域的搜索時序，從而達到快速捕獲目標的目的，是目標搜索調(diào)度領(lǐng)域使用最廣泛的方法.本文將針對各種基于信息增益的傳感器搜索調(diào)度模型，通過數(shù)值仿真計算，對比分析各種模型的搜索性能，以期為目標最優(yōu)搜索方法的研究提供參考.

湖南師范大學自然科學學報第38卷第6期張國輝：基于信息增益的傳感器搜索調(diào)度模型對比分析1基于信息增益的傳感器搜索調(diào)度模型

對于預先編排好的n個搜索區(qū)域，任意區(qū)域k，k=1，2，…，n的狀態(tài)Hk為二元，即有目標或無目標，可表示為Hk=1、Hk=0.假定傳感器也是二元觀測，即“目標存在”或“目標不存在”，t時刻對第k個區(qū)域的觀測結(jié)果記為zk（t），則zk（t）∈{0，1}，而檢測概率pd，虛警概率pf分別為pd=P（zk=1|Hk=1）， pf=P（zk=1|Hk=0）.基于上述假定，傳感器搜索目標本質(zhì)上是二元觀測問題.

在基于信息增益的傳感器搜索調(diào)度模型框架下，3個典型的信息測度Shannon熵DShannon，KullbackLeibler熵DKL和Rényi熵DRenyi分別定義為

DShannon（pki（t+1），pki（t））=pki（t+1）·log（pki（t+1））+（1-pki（t+1））·

log（1-pki（t+1））-pki（t）·log（pki（t））-（1-pki（t））·log（1-pki（t））， （1）

DKL（pki（t+1），pki（t））=pki（t+1）·log（pki（t+1）pki（t））+（1-pki（t+1））·log（1-pki（t+1）1-pki（t）），（2）

DRenyi（pki（t+1），pki（t））=1α-1log [（pki（t+1））α（pki（t））1-α+（1-pki（t+1））α（1-pki（t））1-α]，（3）

式（1）～（3）中pki（t），pki（t+1）分別表示傳感器第t次觀測前后目標出現(xiàn)在第k個搜索區(qū)域內(nèi)的概率，即截獲概率[1315]，也稱為搜索區(qū)域的先驗和后驗狀態(tài)概率密度.pki（t+1）可由pki（t）和觀測結(jié)果通過Bayesian公式得到[2]，即

pki（t+1）=P（Hk=1|zk（t+1））=P（zk（t+1）|Hk=1）P（Hk=1|zk（t））∑1j=0P（zk（t+1）|Hk=j）P（Hk=j|zk（t））. ? （4）

當Hk，zk取不同值時，對于式（4）P（zk（t+1）|Hk）項有

P（zk=1|Hk=1）=pd，P（zk=0|Hk=1）=1-pd，

P（zk=1|Hk=0）=pf，P（zk=0|Hk=0）=1-pf.（5）

信息增益實際上是t時刻傳感器搜索前后的目標位置不確定性減少量的反映，常作為傳感器搜索調(diào)度的準則.定義t時刻選擇的搜索區(qū)域為k（t），則信息增益函數(shù)EI可表示為

EI（t，k（t））=∑1j=0D·（P（Hk=1|zk（t）=j，k（t）），pki（t-1））·P（zk（t）=j|k（t））， ?（6）

式中D·表示式（1）～（3）的3種常用信息測度;P（zk（t）=j|k（t））表示t時刻所選搜索區(qū)域k（t）的觀測結(jié)果，可由下式預測

P（zk（t）|k（t））=∑1j=0P（zk（t）|Hk（t）=j，k（t））·P（Hk（t）=j）. ? ? ? ? （7）

文獻[2]經(jīng)分析還提出一種全局信息增益EG，反映了目標檢測結(jié)果對所有搜索區(qū)域信息增益的影響，定義為

EG（t，k（t））=∑nk=1∑1j=0D·（P（Hk=1|zk（t）=j，k（t）），pki（t-1））·P（zk（t）=j|k（t））. （8）

相應地，本文稱式（6）的信息增益為局部信息增益.

在信息增益準則下，通過信息增益最大化選擇區(qū)域進行搜索.引入傳感器觀測能力約束和捕獲時效性約束，可建立如下搜索調(diào)度模型

max{E·（t，k（t）），k（t）∈{1，2，…，n}}

s.t.Tj∈S，

1fk<tk，k=1，2，…，n，（9）

式中E·表示式（6）或式（8）的信息增益函數(shù)，Tj∈S表示目標Tj在傳感器S的觀測范圍內(nèi)，1fk<tk表示傳感器完成一次探測的時間（等于探測數(shù)據(jù)率的倒數(shù)）小于在該搜索區(qū)域的駐留時間.

分別采用式（1）～（3）的3種信息測度與式（6）和式（8）兩種信息增益函數(shù)，可以得到6種典型的基于信息增益的傳感器搜索調(diào)度模型：基于全局Shannon熵增益的搜索調(diào)度（SSGShannon）;基于全局KullbackLeibler熵增益的搜索調(diào)度（SSGKL）;基于全局Rényi熵增益的搜索調(diào)度（SSGRényi）;基于局部Shannon熵增益的搜索調(diào)度（SSLShannon）;基于局部KullbackLeibler熵增益的搜索調(diào)度（SSLKL）和基于局部Rényi熵增益的搜索調(diào)度（SSLRényi）.

2搜索性能仿真對比分析

為確定傳感器搜索調(diào)度方法對目標捕獲性能提高的程度，需要比較搜索調(diào)度方法和無調(diào)度方法的性能.在現(xiàn)有研究中，主要有兩種無調(diào)度方法，即順序搜索（SQS， Sequential Search）和隨意搜索（RDS， Random Search）[10，11].對于SQS方法，傳感器按照各搜索區(qū)域的編號依次搜索，搜索完最后一個區(qū)域時，重新從第一個區(qū)域開始順次搜索;對于RDS方法，傳感器每次觀測都隨意選擇一個區(qū)域進行搜索，且以同等概率選擇任一區(qū)域.

本文仿真對比分析了6種基于信息增益的搜索調(diào)度方法和兩種無調(diào)度方法，并采用目標累積捕獲概率評價搜索調(diào)度方法性能.多幀累積捕獲概率pcc定義為：n幀捕獲中有不小于m幀成功捕獲目標的概率，即

pcc（l≥m）=∑ni=mpcc（i）=∑ni=m（n

i）·pic·（1-pc）n-i，（10）

式中l(wèi)表示n幀捕獲中成功捕獲到目標的幀數(shù)，pcc（i）為n幀捕獲中有i幀成功捕獲到目標的累積捕獲概率.本文仿真試驗中取m=1，則有

pcc（l≥1）=∑ni=1（n

i）·pic·（1-pc）n-i=1-（1-pd·pi）n.（11）

各種方法調(diào)度傳感器觀測目標的累積捕獲概率結(jié)果（200次MonteCarlo實驗平均值）如圖1所示.仿真場景設(shè)置為：傳感器執(zhí)行3×3=9的搜索，各搜索區(qū)域的初始截獲概率為pi（0）=[0.021 7，0.103 9，0.021 7，0.103 8，0.498 0，0.103 9，0.021 6，0.103 8，0.021 7].

圖1信息增益方法與無調(diào)度方法比較

Fig.1Comparison of information gain method and nonscheduling method6種信息增益模型調(diào)度傳感器觀測目標的累積捕獲概率結(jié)果（200次MonteCarlo實驗平均值）如圖2所示，其仿真場景設(shè)置同圖1，且圖2（a）取pd=0.55，pf=0.35，圖2 （d）的Rényi熵α參數(shù)取α=0.9.

（a）α不同取值時Renyi信息增益與其他方法比較 ?（b）全局與局部信息增益比較（Shannon） （c）全局與局部信息增益方法比較（KullbackLeibler） （d）全局與局部信息增益方法比較（Rényi）

圖2基于信息增益模型的搜索調(diào)度方法目標捕獲性能比較

Fig.2Comparision of acquisition performance search scheduling methods based on information gain由圖1和圖2可得如下結(jié)論：

（1） 各種基于信息增益的搜索調(diào)度方法對目標的捕獲性能明顯優(yōu)于無調(diào)度的SQS方法和RDS方法.

（2） 基于Shannon和KullbackLeibler信息增益的搜索調(diào)度方法對目標的捕獲性能差別很小;而基于Rényi信息增益的搜索調(diào)度方法對目標的捕獲性能隨參數(shù)α取值的增大而提高，α→1時性能最優(yōu)，且與基于Shannon和KullbackLeibler信息增益的方法性能相當.

（3） 對于Shannon，KullbackLeibler，Rényi這3種信息測度來說，隨著檢測概率減小（或虛警概率增大），全局信息增益方法在捕獲性能上逐漸表現(xiàn)出優(yōu)勢，這是由于全局信息增益充分考慮了所有搜索區(qū)域信息量變化的緣故.

3結(jié)論

本文針對目標搜索傳感器調(diào)度問題展開研究，首先介紹了Shannon熵、KullbackLeibler熵和Rényi熵3種信息測度以及全局信息增益和局部信息增益的數(shù)學定義;然后基于這3種信息測度和兩種信息增益，建立了6種基于信息增益的目標搜索傳感器調(diào)度模型;最后，通過數(shù)值仿真計算，對比分析了6種基于信息增益的搜索調(diào)度方法與兩種無調(diào)度方法調(diào)度傳感器對目標的捕獲性能.仿真結(jié)果表明，基于信息增益模型的搜索調(diào)度方法的目標捕獲性能明顯優(yōu)于無調(diào)度方法，且基于全局信息增益模型的搜索調(diào)度方法性能更優(yōu).仿真結(jié)果可作為實際工程實踐中優(yōu)選搜索調(diào)度方法的參考.進一步的研究工作可從以下兩方面展開：（1）基于信息增益模型的搜索調(diào)度方法在不同應用領(lǐng)域、不同先驗條件下對目標的搜索捕獲性能研究;（2）不同體制傳感器對同一目標聯(lián)合探測條件下，多種傳感器的聯(lián)合搜索調(diào)度問題.

參考文獻：

[1]MATTHIESEN D J. Optimal search[C]∥Proceedings of the IEEE international symposium on phased array systems and technology. Boston， 2003：259264.

[2]盧建斌. 相控陣雷達資源優(yōu)化管理的理論與方法[D]. 長沙： 國防科技大學， 2007.

[3]DONALD R D， HEMSTETER K P. GRASP multisensor search tactics against evading targets[C]∥Proceedings of MTS/IEEE oceans 02 conference. Biloxi， 2002：5459.

[4]CHRISTOPHER G. Active target search from UAVs in urban environments[C]∥Proceedings of the IEEE international conference on robotics and automation. Pasadena， 2008：23662371.

[5]占紅來. 紅外弱小目標搜索跟蹤算法研究[D]. 北京： 中國工程物理研究院， 2013.

[6]JAMES N E， JAMES R Y. An approximate solution technique for the constrained search path moving target search problem[R]. California， USA： Naval Postgraduate School， 1985.

[7]STONE L D. Theory of optimal search[M]. New York： Academic Press， 1975.

[8]徐斌，楊晨陽，李少洪，等. 相控陣雷達的最優(yōu)分區(qū)搜索算法[J]. 電子學報， 2000，28（12）：6973.

[9]MARK P K， LESLIE M C. Informationbased sensor management in the presence of uncertainty[J]. IEEE TSP， ?2007，55（6）：27312735.

[10]MARK P K， LESLIE M C. Analysis of an informationbased sensor manager applicable to landmine detection[C]∥Proceedings of the IEEE international geosicience and remote sensing symposium. Boston， 2008：521524.

[11]WANG B， LI J， AN W， et al. Information gain based sensor search scheduling for the lowearth orbit constellation[J]. J Syst Eng Electr， 2011，22（6）：926932.

[12]KREUCHER C M， KASTELLA K D， HERO A O. Information based sensor management for multitarget tracking[C]∥Proceedings of the SPIE signal and data processing of small targets. San Diego， 2003：480489.

[13]厲亞，王博，吳洪. 基于高斯誤差橢球的截獲概率仿真[J]. 湖南大學學報：自然科學版， 2013，40（11）：108113.

[14]沈東，魏瑞軒，祁曉明，等. 基于MTPM和DPM的多無人機協(xié)同廣域目標搜索滾動時域決策[J]. 自動化學報， 2014，40（7）：13911403.

[15]毛弋，蔣盈，李寶玉，等.多種通信方式并存的配網(wǎng)自動化通信系統(tǒng)的研究[J].湖南師范大學自然科學學報， 2013，36（4）：3136.