Диссертация (1150919), страница 8
Текст из файла (страница 8)
. . , n или θ j ∈ Rd— подвектор вектора θ = col(θ 1 , . . . , θ n ) соответственно. В первом случае решение задачи оптимизации θ ? ищется для каждого из наблюдателей (сенсоров) j на основе доступной ему локальной информации припредположении, что все функции fwj (·) имеют одинаковые точки минимума. Во втором случае каждый наблюдатель j связан с некоторой ча?стью θ j глобального оптимального решения θ ? . Далее при возможностисвязей между наблюдателями полученные локальные решения тем илииным способом агрегируются. Например, при достаточно общих условиях на топологию связей между наблюдателями для агрегации результатов можно воспользоваться описанным в [39] протоколом локальногоголосования, работоспособным в условиях помех и задержек в каналахсвязей.Задача (2.3) в распределенном виде переформулируется следующимобразом: найти “дрейфующую” точку минимума θ t функции(2.7)F̄t (θ) = EFt−1nXfwj t (θ j )j=1=nXj=1Ftj (θ j ) → min .θпри линейных ограниченияхH j θj = qjt−1с задаваемыми матрицей H j размерности l × d и векторами qjt−1 ∈ Rl ,0 ≤ l < d.47i,jОпределим матрицу смежности Bt = [bi,jt ], где bt > 0, если сенсор jнаблюдает за объектом i, и bi,jt = 0 — в противном случае.
Аналогичноj,kвведем матрицу взаимодействия Ct = [cj,k> 0, если сенсор jt ], где ctможет обмениваться данными с сенсором k ∈ N , и cj,kt = 0 — в противномслучае. Обозначим через Ntj = {j : cj,kt > 0} ⊂ N множество “соседей”jсенсора j и через |Nt | — количество “соседей” у сенсора j. Обозначимчерез Mtj ⊂ M множество целей сенсора j, за которыми он или самнаблюдает в момент времени t, или о которых он может получить данныеот своих соседей.Будем рассматривать два вида ограничений на функционированиесенсорной сети. Первое ограничение состоит в том, что каждый сенсорможет обмениваться данными только с определенным количеством “соседей”, т.
е. будем считать, что заданы ограничения(2.8)|Ntj | ≤ njmax .В реальной среде функционирования эти ограничения могут быть связаны с тем, что заданы ограничения на количество выделенных каналов связи, или с невозможностью отправки данных на расстояние болеенекоторого максимального. Второе ограничение относится к максимально допустимому в момент времени t количеству целей(2.9)|Mtj | ≤ mjmax ,информацию о которых сенсор j имеет возможность получить от своих“соседей” или в процессе самостоятельного наблюдения. В свою очередьэта величина может быть связана с ограниченностью полосы пропускания канала связи. Также отметим, что формирование подмножеств Mtjдостигается за счет варьирования коэффициентами матрицы смежности Bt .Пусть матрицы Bt и Ct удовлетворяют условиям (2.8) и (2.9).
С учетом введенных обозначений функционал (2.5) можно переписать в виде48(2.7) c(2.10)jftj (θbt )K X −1 j i,j=kϕ (st , zt ) − brit k2 /(σti,j )2 ,2nji∈Mtт. к. можно считать, что (σti,j )2 = ∞, если в момент времени t наблюдатель j не получает никакой информации об объекте i.2.1.4Доверительные эллипсоидыРассмотрим наблюдение одного сенсора j за одним объектом i. Будемсчитать, что помехи являются независимыми гауссовскими одинаковораспределенными величинами. В [100] показано, что при задании уровнядостоверности p доверительный эллипсоид, содержащий истинное значение параметра с вероятностью p, вокруг точки результата наблюденияη i,j = ϕ−1 (sjt , zi,jt ) задается формулой:(2.11)−1 ii,j2E i,j = {ri : (ri − η i,j )T (Ξi,jt ) (r − η ) ≤ χp,d },где χ2p,d — p-квантиль распределения χ2 с d степенями свободы.Л е м м а 2.
Пусть имеется n эллипсоидов {E 1 , . . . , E n }, каждый изкоторых является доверительным эллипсоидом с уровнем достоверности p, тогда множество пересечения этих эллипсоидов с вероятностью не менее чем 1 − (n + 1)p содержит вектор истинного значенияпараметров.Доказательство. Рассмотрим частный случай, а именно пересечениедвух эллипсоидов E 1 и E 2 . Возьмем некоторую точку x соответствующейэллипсоидам размерности и введем следующие вероятностные события:• точка x не принадлежит эллипсоиду E 1 , т. е. A1 = {x ∈/ E 1 };• точка x не принадлежит эллипсоиду E 2 , т.
е. A2 = {x ∈/ E 2 };49• точка x не принадлежит пересечению E 1TE 1 E 2 }.TE 2 , т. е. A = {x ∈/Оценим вероятность P (A):P (A) = P (A1 Ā2 + Ā1 A2 + A1 A2 ) ≤ P (A1 Ā2 ) + P (Ā1 A2 ) + P (A1 A2 ).Так как вероятность пересечения не превышает вероятностей каждого из множеств, получаем, чтоP (A) ≤ 3P (A1 ) или P (A) ≤ 3p.Обобщим на случай n эллипсоидов:P (A) ≤ (n + 1)P (A1 ) или P (A) ≤ (n + 1)p,с соответствующими событиями A, A1 , . . . , An .Исходя из полученных соотношений, вероятность того, что точка xсодержится во множестве пересечения, т.
е. P (Ā) равна 1 − (n + 1)p.В соответствии с Леммой 2 если за объектом i наблюдает n сенсоров, то вектор истинного значения параметров с вероятностью не менее чем 1 − (n + 1)p принадлежит множеству пересечения эллипсоидов{E i,1 , . . . , E i,n }.Будем считать, что множество пересечения возможно аппроксимировать эллипсоидом E i :(2.12)iE ⊇n\E i,j .j=1Приведенные рассуждения показывают целесообразность замены задачи о минимизации суммы (2.5) на задачу о минимизации суммы объемов эллипсоидов, содержащих множества пересечений.
Для представления задачи в новом виде в первую очередь рассмотрим некоторые спосо50бы задания эллипсоида E. Формы эллипсоида, описанные ниже, являются общими и будут использоваться для всех последующих эллипсоидов,встречающихся в работе.Прежде всего, эллипсоид можно описать как образ единичного шарапри афинном отображении:(2.13)E = {x ∈ Rν : x = Rq + xc , q ∈ Rr , kqk < 1},где R ∈ Rν×r — прямоугольная матрица, xc — центр эллипсоида.Если матрица R максимального строчного ранга, то представлению(2.13) можно придать вид(2.14)E = {x ∈ Rν : (x − xc )T P −1 (x − xc ) ≤ 1}, P = RRT .При представлении эллипсоида E i в виде (2.14) его объем вычисля√ется по формуле cν det P i , где cν — объем единичного шара в ν-мерномпространстве, det — определитель матрицы.
С учетом введенных обозначений запишем задачу о минимизации суммы объемов эллипсоидовÊ = {E 1 , . . . , E m }, содержащих множества пересечений, в следующем виде:(2.15)Φ(Ê) =X√cν det P i → min .Êi∈MОчевидно, что наилучшая аппроксимация множества пересечения эллипсоидов достигается при использовании наблюдений всех сенсоров обобъекте i. Однако, такой подход противоречит введенным в работе ограничениям (2.8)-(2.9). Для удовлетворения этих ограничений предлагается искать компромиссное решение между получаемой точностью оценивания и использованием ресурсов сенсоров.
Для этого необходимо строить эллипсоиды, содержащие множества пересечений, по измерениям техсенсоров, которые вносят наибольший вклад в точность оценивания. Вобщем случае задача такого рода является трудной, так как ее решение51приводит к комбинаторному перебору со значительным числом комбинаций при больших значениях m и n.В работе [31] для решения подобных проблем предлагается воспользоваться “овыпуклением” задачи, основанном на использовании специальных матричных форм, и получить субоптимальное разреженное решение.
Математическая задача в этом случае сводится к минимизации суммы ненулевых компонент вектора, определяемого l0 -“нормой”. Посколькуl0 -“норма” невупукла, вместо нее используется векторная l1 -норма. Минимум l1 -нормы на множестве, образованном выпуклыми ограничениями, в соответствии с Леммой 1 из подраздела 1.1.3 главы 1 также будетявляться хорошей аппроксимацией разреженного решения.Переформулируем задачу, рассматриваемую в работе, на основе l1подхода. Для этого введем матрицу распределения ресурсов Gt = [gti,j ],где gti,j > 0, если сенсор j участвует в формировании оценки для i-го объекта, и gti,j = 0 — в противном случае.
Пусть необходимо найти такуюматрицу Gt , распределяющую сенсоры между объектами слежения, которая минимизирует функционал (2.15) и при этом оптимизирует числоиспользуемых для слежения сенсоров путем сокращения числа ненулевых компонент, тогда задача (2.15) примет вид:(2.16)Φ̄(Gt ) = Φ(Ê) +XkGi,·t k0 +i∈MXj∈NkG·,jt k0 → min,Gtгде для каждого эллипсоида E i ∈ Ê учитываются только те эллипсоидыE i,j , для которых gti,j > 0, Gi,·t — i-ая строка матрицы Gt (множествосенсоров, оценивающих траекторию объекта i) и G·,jt — j-ый столбецматрицы Gt (множество объектов, назначенных сенсору j).Заметим, что по полученной матрице Gt естественным образом строятся матрицы Bt и Ct .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
