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

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

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

中圖分類號TN9111文獻(xiàn)標(biāo)識碼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

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

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

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

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

對于預(yù)先編排好的n個搜索區(qū)域，任意區(qū)域k，k=1，2，…，n的狀態(tài)Hk為二元，即有目標(biāo)或無目標(biāo)，可表示為Hk=1、Hk=0.假定傳感器也是二元觀測，即“目標(biāo)存在”或“目標(biāo)不存在”，t時刻對第k個區(qū)域的觀測結(jié)果記為zk（t），則zk（t）∈{0，1}，而檢測概率pd，虛警概率pf分別為pd=P（zk=1|Hk=1）， pf=P（zk=1|Hk=0）.基于上述假定，傳感器搜索目標(biāo)本質(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次觀測前后目標(biāo)出現(xiàn)在第k個搜索區(qū)域內(nèi)的概率，即截獲概率[1315]，也稱為搜索區(qū)域的先驗(yàn)和后驗(yàn)狀態(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）

當(dāng)Hk，zk取不同值時，對于式（4）P（zk（t+1）|Hk）項(xiàng)有

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）

信息增益實(shí)際上是t時刻傳感器搜索前后的目標(biāo)位置不確定性減少量的反映，常作為傳感器搜索調(diào)度的準(zhǔn)則.定義t時刻選擇的搜索區(qū)域?yàn)閗（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é)果，可由下式預(yù)測

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

文獻(xiàn)[2]經(jīng)分析還提出一種全局信息增益EG，反映了目標(biāo)檢測結(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）

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

在信息增益準(zhǔn)則下，通過信息增益最大化選擇區(qū)域進(jìn)行搜索.引入傳感器觀測能力約束和捕獲時效性約束，可建立如下搜索調(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表示目標(biāo)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)度方法對目標(biāo)捕獲性能提高的程度，需要比較搜索調(diào)度方法和無調(diào)度方法的性能.在現(xiàn)有研究中，主要有兩種無調(diào)度方法，即順序搜索（SQS， Sequential Search）和隨意搜索（RDS， Random Search）[10，11].對于SQS方法，傳感器按照各搜索區(qū)域的編號依次搜索，搜索完最后一個區(qū)域時，重新從第一個區(qū)域開始順次搜索;對于RDS方法，傳感器每次觀測都隨意選擇一個區(qū)域進(jìn)行搜索，且以同等概率選擇任一區(qū)域.

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

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

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

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

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

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

各種方法調(diào)度傳感器觀測目標(biāo)的累積捕獲概率結(jié)果（200次MonteCarlo實(shí)驗(yàn)平均值）如圖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)度傳感器觀測目標(biāo)的累積捕獲概率結(jié)果（200次MonteCarlo實(shí)驗(yàn)平均值）如圖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)度方法目標(biāo)捕獲性能比較

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

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

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

（3） 對于Shannon，KullbackLeibler，Rényi這3種信息測度來說，隨著檢測概率減?。ɑ蛱摼怕试龃螅中畔⒃鲆娣椒ㄔ诓东@性能上逐漸表現(xiàn)出優(yōu)勢，這是由于全局信息增益充分考慮了所有搜索區(qū)域信息量變化的緣故.

3結(jié)論

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

參考文獻(xiàn)：

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

[2]盧建斌. 相控陣?yán)走_(dá)資源優(yōu)化管理的理論與方法[D]. 長沙： 國防科技大學(xué)， 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]占紅來. 紅外弱小目標(biāo)搜索跟蹤算法研究[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án)走_(dá)的最優(yōu)分區(qū)搜索算法[J]. 電子學(xué)報(bào)， 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]. 湖南大學(xué)學(xué)報(bào)：自然科學(xué)版， 2013，40（11）：108113.

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

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