close

Вход

Забыли?

вход по аккаунту

?

Передача данных при утечке информации.

код для вставкиСкачать
ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА
Сер. 10. 2011. Вып. 2
УДК 519.7
М. А. Золотухин, А. Ю. Гарнаев, В. В. Захаров
ПЕРЕДАЧА ДАННЫХ ПРИ УТЕЧКЕ ИНФОРМАЦИИ
1. Введение. Безопасность передачи данных – один из ключевых вопросов функционирования беспроводных сетей. Хотя большинство работ по безопасности передачи
данных фокусируются на криптографических аспектах проблемы, которые, без сомнения, являются ключевыми, в настоящее время появилось большое число публикаций,
которые, кроме того, учитывают такую специфику передачи информации в беспроводных сетях как их многочастотность и многоканальность, а также эффект затухания
и искажения передаваемого сигнала по этим каналам [1–5]. Такие исследования [6–10]
служат приложением теории информации, которая предоставляет математический аппарат, введенный в пионерских работах К. Шеннона [9, 11] и позволяющий оценить
качество передаваемого сигнала с учетом и без учета возможного присутствия в сети
прослушивающего агента. В связи с повсеместным распространением беспроводных сетей необходимость решения задач, связанных с безопасностью передачи информации,
за последние годы постоянно увеличивается. В настоящее время исследования в данном
направлении ведутся во многих крупных университетах и исследовательских институтах США (Принстонский университет [5], Bell Laboratories [6]) и Западной Европы
(INRIA ([2, 12], Швейцарский федеральный технологический институт [8]).
Цель данной работы – обобщение результатов работы [7] на случай, когда процесс передачи данных происходит не одномоментно, а за нескольких временных слотов. Кроме
того, исследуется фактор влияния тарифов использования сети на поведение пользователей, а именно: выведены условия на тарифы, при которых пользователь вообще
отказывается от сети, при которых он ограничивает себя в объеме использования сети
и применяет сеть в полном объеме.
Золотухин Михаил Анатольевич – аспирант кафедры компьютерного моделирования и многопроцессорных систем факультета прикладной математики–процессов управления Санкт-Петербургского государственного университета. Научный руководитель: доктор физико-математических
наук, проф. А. Ю. Гарнаев. Количество опубликованных работ: 7. Научные направления: исследование операций, теория игр, беспроводные сети, информационная безопасность в сетях. E-mail:
mikeaz87@gmail.com.
Гарнаев Андрей Юрьевич – доктор физико-математических наук, профессор кафедры компьютерного моделирования и многопроцессорных систем факультета прикладной математики–процессов
управления Санкт-Петербургского государственного университета. Количество опубликованных работ: 181. Научные направления: алгоритмы поиска подвижных и неподвижных объектов, моделирование конфликтно-управляемых систем, обучающиеся системы, экспертные системы, беспроводные сети,
задачи оптимизации в сетях и распределенных системах. E-mail: garnaev@yahoo.com.
Захаров Виктор Васильевич – доктор физико-математических наук, профессор, заведующий кафедрой математического моделирования энергетических систем факультета прикладной математики–
процессов управления Санкт-Петербургского государственного университета. Количество опубликованных работ: 232. Научные направления: оптимальное управление, теория игр и приложения, исследование операций. E-mail: mcvictor@mail.ru.
c М. А. Золотухин, А. Ю. Гарнаев, В. В. Захаров, 2011
40
Статья имеет следующую структуру. В п. 2 приводится постановка задачи, в п. 3
дается конструктивное решение задачи и доказывается его единственность, в п. 4
рассмотрены модификации основной модели, а в п. 5 продемонстрированы результаты численного моделирования.
2. Постановка задачи. Рассмотрим модель, являющуюся обобщением модели [7]
передачи данных в беспроводной сети при наличии прослушивающего агента на случай, когда процесс передачи данных происходит не одномоментно, а за нескольких
временных слотов с учетом влияния тарифов использования сети на поведение пользователя. Итак, пользователь пытается осуществлять передачу информации в течение
нескольких временных слотов T по N каналам. При этом в сети, кроме пользователя,
передающего информацию, находится пассивный агент, который осуществляет прослушивание по своим специальным каналам. Предположим, что все рассматриваемые каналы являются каналами с аддитивным белым гауссовским шумом (АБГШ). АБГШ –
вид мешающего воздействия в канале передачи информации, который характеризуется
равномерной спектральной плотностью, нормально распределенным значением амплитуды и аддитивным способом воздействия на сигнал. Это наиболее распространенный
вид шума, используемый для расчета и моделирования систем радиосвязи.
Каждый рассматриваемый канал характеризуется коэффициентом затухания hM
l =
M
M
(hl1 , hM
,
.
.
.
,
h
),
который
является
вектором
значений
дискретной
случайной
велиl2
lnM
чины, т. е. коэффициент затухания l-го канала передачи данных равен hM
li с вероятностью μM
li (i ∈ [1, nM ]). Аналогично коэффициент затухания l-го канала для прослуE
шивания равен hE
lj с вероятностью μlj (j ∈ [1, nE ]). Считается, что рассматриваемые
случайные величины независимые [7]. Опишем случай, когда пользователь обладает
полной информацией о состоянии всех каналов передачи, ему известно распределение
E
hM
l и hl для каждого l.
В работах [13, 14] доказано, что в случае АБГШ каналов связи минимальная верхняя оценка скорости передачи данных, при которой конфиденциальная информация
идеально скрыта от прослушивающего агента, определяется следующим обобщением
формулы Шеннона:
E
Cs = log(1 + hM
l Pl ) − log(1 + hl Pl ),
где Pl – мощность сигнала, переданного по l-му каналу. В этом выражении Cs представляет собой разность между пропускной способностью каналов передачи и пропускной
способностью каналов для прослушивания.
При передаче информации за T временных слотов будем полагать, что ценность
информации, переданной во временной слот t, изменяется в соответствии с дисконтирующим фактором δ t ∈ (0, 1]. Это побуждает пользователя передавать большую часть
информации либо в начале сеанса связи, либо, наоборот, в его конце.
Важным параметром при оценке полезности использования сети является цена, которую пользователь платит за мощность при передаче. Учет стоимости передачи сигнала, а следовательно, и существующего тарифа в сети важен, так как в зависимости
от этого тарифа существенно может измениться поведение пользователя: от абсолютного отказа от сети до использования ее в полном объеме.
Таким образом, определим функцию выигрыша пользователя как ожидаемую величину обобщенной пропускной способности Шеннона Cs с учетом дисконтирующего
фактора и затрат:
υ(P ) =
T
t=1
δ
t
nM
N l=1 i=1
μM
li
nE
j=1
M t
E t
μE
lj (log(1+hli Plij )−log(1+hlj Plij ))−C
nM
N l=1 i=1
μM
li
nE
t
μE
lj Plij
. (1)
j=1
41
E t
t
Мощность сигнала P = {P (hM
li , hlj , δ )} = {Plij } измеряется в децибелах (дБ); C есть
некоторый коэффициент стоимости, который находится как C = Crt · Ccnv . Здесь
Crt – тариф за используемую мощность – измеряется в рублях за децибел (руб./дБ),
а Ccnv – некоторый переводной коэффициент, подобранный таким образом, чтобы C
изменялся от 0 до 1 (измеряется в нат/руб.). Таким образом, единицами измерения
целевой функции υ являются наты (нат).
t
} с неотрицательными
Стратегиями пользователей являются функции P = {Plij
t
компонентами: Plij 0, l = 1, . . . , N, i = 1, . . . , nM , j = 1, . . . , nE , t = 1, . . . , T , которые удовлетворяют ограничениям как на среднюю мощность передаваемого сигнала
в каждый временной слот, так и на общую среднюю мощность:
nM
T N μM
li
t=1 l=1 i=1
nM
N t
μE
lj Plij P̄ ,
j=1
μM
li
l=1 i=1
nE
nE
t
t
μE
lj Plij P̄ .
j=1
Предположим, что пропускная способность каналов позволяет передать весь сигнал
пользователю, а именно, выполнено неравенство
T
P̄ t > P̄ .
(2)
t=1
Следуя [7], считаем, что пользователю имеет смысл передавать сигнал только при условии
E
hM
l = 1, . . . , N, i = 1, . . . , nM , j = 1, . . . , nE .
(3)
li > hlj ,
3. Решение задачи. При выполнении (2) функция υ(P ) вогнута относительно P =
t
}, поскольку гессиан функции (1) есть отрицательно полуопределенная матрица.
{Plij
t
Из теоремы Куна–Таккера следует, что P = {Plij
} является оптимальным распределением передаваемого сигнала тогда и только тогда, когда существуют неотрицательные λ и ω 1 , ω 2 , . . . , ω T (множители Лагранжа) такие, что выполняются соотношения
$%
t
hE
> 0,
hM
= λ + ω t , Plij
lj
t
li
(4)
−
−C
δ
M
t
E
t
t
t
1 + hli Plij
1 + hlj Plij
= 0,
λ + ω , Plij
где
ω
λ
t
⎧
⎪
⎪
⎨ 0,
если
⎪
⎪
⎩= 0,
если
N n
l=1 i=1
N n
μli
μli
l=1 i=1
⎧
⎪
⎪
⎨ 0,
если
⎪
⎪
⎩= 0,
если
N T n
t=1 l=1 i=1
N T n
t=1 l=1 i=1
n
j=1
n
j=1
μli
μli
t
μlj Plij
= P̄ t ,
t
μlj Plij
< P̄ t ,
n
j=1
n
j=1
(5)
t
μlj Plij
= P̄ ,
t
μlj Plij
< P̄ .
Выведем общий вид оптимальных решений задачи как функций от множителей
Лагранжа.
42
Лемма 1. Все оптимальные решения в задаче передачи сигнала с полной информацией имеют следующий вид:
⎧
0, l, i, j, t ∈ I0 (λ, ω 1 , ω 2 , . . . , ω T ),
⎪
⎪
*
⎪
2
⎪
⎪
⎪
⎨1
4
1 − 1
1 − 1
+
−
t
Plij
(λ, ω t ) = 2
C + (λ + ω t )/δ t hE
hE
hM
hM
lj
li
lj
li
$
⎪
⎪
⎪
⎪
⎪
1 + 1
⎪
, l, i, j, t ∈ I1 (λ, ω 1 , ω 2 , . . . , ω T ),
⎩−
E
M
hlj
hli
(6)
где
E
t
t
I0 (λ, ω 1 , ω 2 , . . . , ω T ) = {l ∈ [1, N ], i, j ∈ [1, n], t ∈ [1, T ] : hM
li − hlj (ω + λ)/δ + C},
E
t
t
I1 (λ, ω 1 , ω 2 , . . . , ω T ) = {l ∈ [1, N ], i, j ∈ [1, n], t ∈ [1, T ] : hM
li − hlj > (ω + λ)/δ + C},
причем выполняются соотношения (5).
t
} – оптимальная стратегия пользоД о к а з а т е л ь с т в о. Пусть P = {Plij
t
E
t
t
вателя. Если Plij = 0, то из соотношений (4) следует, что hM
li − hlj (ω + λ)/δ + C,
t
т. е. (l, i, j, t) ∈ I0 . Если Plij
> 0, тогда из (4) вытекает, что
δt
hE
hM
lj
li
−
−C
t
EP t
1 + hM
P
1
+
h
li lij
lj lij
$
= λ + ωt.
t
Решив это уравнение относительно Plij
, получим решение в виде второй строки (6),
что завершает доказательство леммы.
Данная лемма указывает на важное свойство оптимального решения: оно монотонно убывает как функция относительно множителей Лагранжа. Теперь перейдем
к нахождению оптимальных значений множителей Лагранжа. С этой целью введем
вспомогательные обозначения
E
(lo , io , j o ) := argmaxl∈[1,N ], i,j∈[1,n] (hM
li − hlj ),
W t (λ, ω t ) :=
n
N μli
l=1 i=1
1
2
T
H(λ; ω , ω , . . . , ω ) :=
n
t
μlj Plij
(λ, ω t ),
j=1
T N n
t=1 l=1 i=1
μli
n
t
μlj Plij
(λ, ω t )
j=1
=
T
$
t
t
W (λ, ω ) .
t=1
Используя лемму 1, докажем следующую теорему, в которой приведена оптимальная стратегия и доказана ее единственность для задачи передачи сигнала при наличии
слушателя в случае полной информации о состоянии каналов.
Теорема 1. В случае полной информации о состоянии каналов в задаче имеется
t
(λ, ω t )}, причем,
единственное оптимальное решение P = {Plij
(a) если
E
C hM
(7)
lo io − hlo j o ,
t
то P = {Plij
} = 0 c выигрышем, равным 0;
(b) если
E
C < hM
lo io − hlo j o
(8)
43
и
(b1) если
1
T
H(0; ω+
, . . . , ω+
) P̄ ,
(9)
t
t
(0, ω+
)}, где
то P = {Plij
%
= 0, если W t (0, 0) < P̄ t ,
t
ω+
корень уравнения W t (0, ω t ) = P t , если W t (0, 0) P̄ t ;
(b2) если
то P =
1
T
, . . . , ω+
) > P̄ ,
H(0; ω+
t
(λ∗ , ω t (λ∗ )),
{Plij
%
ω t (λ)
(10)
(11)
где
= 0, если W t (λ, 0) < P̄ t ,
корень уравнения W t (λ, ω t ) = P̄ t , если W t (λ, 0) P̄ t ,
(12)
а λ∗ является единственным корнем уравнения
H̄(λ∗ ) = P̄ ,
где H̄(λ) = H(λ; ω 1 (λ), . . . , ω T (λ)).
Д о к а з а т е л ь с т в о. По лемме 1 P является оптимальной стратегией
t
(λ, ω t )} из (6), причем λ, ω 1 , . . . , ω T
тогда и только тогда, когда она имеет вид P = {Plij
удовлетворяют следующим соотношениям:
%
0,
ω
= 0,
t
%
λ
0,
= 0,
если W t (λ, ω t ) = P̄ t
если W t (λ, ω t ) < P̄ t
,
t ∈ [1, T ],
если H(λ; ω 1 , ω 2 , . . . , ω T ) = P̄ ,
если H(λ; ω 1 , ω 2 , . . . , ω T ) < P̄ .
(13)
(14)
Таким образом, надо найти λ; ω 1 , ω 2 , . . . , ω T , удовлетворяющие (13) и (14), для того
чтобы построить оптимальную стратегию. Ниже мы не только конструктивным образом определяем такие λ; ω 1 , ω 2 , . . . , ω T , но и доказываем их единственность по единой
схеме для подслучаев (a), (b1) и (b2), описывающих все возможные альтернативы.
Первоначально отметим, что функции H(λ; ω 1 , ω 2 , . . . , ω T ) и W t (λ, ω t ), t ∈ [1, T ], монотонно убывают при возрастании одного из множителей Лагранжа при фиксированных
остальных.
t
(λ, ω t )} – оптимальное решение, тогда
(a) Пусть выполняется (7) и P = {Plij
1
2
T
1
2
I1 (λ, ω , ω , . . . , ω ) = ∅ для любых λ, ω , ω , . . . , ω T . Поэтому P = 0. Для такой стратегии H(λ; ω 1 , ω 2 , . . . , ω T ) = 0 и W t (λ, ω t ) = 0 для любого t. Поэтому, в силу (13) и (14),
единственными возможными значениями лагранжевых множителей являются нулевые:
λ = 0, ω 1 = 0, ω 2 = 0, . . . , ω T = 0. Таким образом, если оптимальное решение сущестt
вует, то оно должно быть равно P = {Plij
(0, 0)}, которое, очевидно, удовлетворяет (13)
и (14) при выполнении условия (7), а следовательно, и является оптимальным.
t
(λ, ω t )} – оптимальное решение, тогда
(b) Пусть выполняется (8) и P = {Plij
I1 (λ, ω 1 , ω 2 , . . . , ω T ) = ∅. Кроме того, в силу монотонного убывания функций W t (0, ω t )
44
t∗
по аргументу ω t , ω+
определяются (10) единственным образом. Перейдем к нахождению оптимальных множителей Лагранжа λ и ω t в двух подслучаях.
(b1) Пусть выполнено (9). Тогда, в силу монотонного убывания функции
1
T
, . . . , ω+
) по λ и соотношений (14), оптимальное λ должно равняться нулю.
H(λ; ω+
Для такого λ соотношения (13) примут вид
%
если W t (0, ω t ) = P̄ t
t 0,
ω
, t ∈ [1, T ],
= 0, если W t (0, ω t ) < P̄ t
и, в силу монотонного убывания функций W t (0, ω t ) по аргументу ω t , имеют единственt
ное решение ω t = ω+
, определенное в (10). Таким образом, если оптимальное решение
t
t
(0, ω+
)}, которое, в силу приведенных
существует, то оно должно быть равно P = {Plij
рассуждений, очевидно, удовлетворяет (13) и (14) при выполнении условий (8) и (9),
а следовательно, является оптимальным.
(b2) В силу строгого монотонного убывания W t (λ, ω t ) по ω t при фиксированном λ,
пока W t (λ, ω t ) > 0, множитель Лагранжа ω t однозначным образом определяется из (13)
соотношением (12). Кроме того, полученные таким образом функции ω t (λ) непрерывные и строго монотонно убывают по λ, пока они положительны. Оптимальное λ находится как решение задачи
%
0, если H̄(λ) = P̄ ,
λ
(15)
= 0, если H̄(λ) < P̄ ,
1
T
где H̄(λ) = H(λ; ω 1 (λ), . . . , ω T (λ)). В силу (11), H̄(0) = H(0; ω+
, . . . , ω+
) > P̄ . Тогда
1
2
T
по строгому монотонному убыванию функции H(λ; ω , ω , . . . , ω ) по λ и соотношений (14) оптимальный множитель Лагранжа λ должен быть положительным. Функции
ω t (λ) удовлетворяют соотношениям (13) для любого λ. Функцию H̄(λ) можно представить в следующем виде:
H̄(λ) =
W t (λ, ω t (λ)) +
W t (λ, 0) =
t:ω t (λ)>0
=
t:ω t (λ)>0
t:ω t (λ)=0
t
P̄ +
W t (λ, 0).
t:ω t (λ)=0
Предположим, что оптимальное λ таково, что ω t (λ) > 0 для всех t. Тогда
H̄(λ) = (по (17)) =
T
P̄ t > (по (1)) > P̄ ,
t=1
а это противоречит (15) и показывает, что оптимальное λ таково, что существуют t,
для которых ω t (λ) = 0, причем с увеличением λ возрастает и количество слагаемых
в сумме, где ω t (λ) = 0. Функции W t (λ, 0) являются монотонно убывающими по λ, следовательно, функция H̄(λ) также будет монотонно убывать по λ. Кроме того, функция H̄(λ) непрерывна по λ, в силу непрерывности функции ω t (λ) и вида функции
H(λ; ω 1 , ω 2 , . . . , ω T ). По (6) H̄(λ) = 0 при достаточно больших значениях λ. Таким
образом, существует некоторое λ∗ такое, что H̄(λ∗ ) = P̄ . По определению λ∗ и вида функций ω t (λ) полученные множители Лагранжа λ∗ , ω 1 (λ∗ ), . . . , ω T (λ∗ ) удовлетворяют (13) и (14). Таким образом, если оптимальное решение существует, то оно должно
t
(λ∗ , ω t (λ∗ )}, которое, в силу приведенных рассуждений, очевидно,
быть равно P = {Plij
45
удовлетворяет (13) и (14) при выполнении условий (8) и (11), а следовательно, и является оптимальным.
Тот факт, что рассмотренные случаи охватывают все возможные альтернативы,
завершает доказательство теоремы.
4. Обсуждение возможных моделей передачи сигнала. Произведем исследование других возможных моделей передачи данных пользователем в беспроводной
сети при наличии прослушивающего агента. Когда в каждый временной слот наложены
ограничения на среднюю мощность сигнала, рассмотрим следующие случаи: 1) пользователь, передающий информацию, знает информацию о состоянии только каналов
для передачи; 2) пользователь, передающий информацию, использует двухопционную
(вкл/выкл) стратегию. Кроме того, рассмотрим модель, когда на процесс передачи сигнала наложены только ограничения на общую среднюю мощность сигнала. В данных
задачах с помощью рассуждений, аналогичных приведенным в п. 2, были получены
оптимальные стратегии и произведено доказательство теорем об их единственности.
Рассмотрим случай, когда пользователю доступна не вся информация, а лишь
информация о состоянии каналов для передачи. В этом случае функция распределения мощностей не зависит от коэффициентов затухания каналов прослушивания
t
t
P = {P (hM
li , δ )} = {Pli }. Таким образом, имеем следующую оптимизационную задачу:
max υ(P ) = max
P
P
T
t=1
δt
N n
l=1 i=1
μli
n
t
E t
μlj (log(1 + hM
li Pli ) − log(1 + hlj Pli )) − C
j=1
N n
μli Plit .
l=1 i=1
Будем по-прежнему предполагать, что компоненты стратегий пользователя Plit неотрицательны и удовлетворяют граничным условиям
n
N μli Plit P̄ t ,
(16)
l=1 i=1
T N n
μli Plit P̄ .
(17)
t=1 l=1 i=1
Предположим, что выполнены условия (1) и (2). Тогда, воспользовавшись теоремой
Куна–Таккера и вводя множитель Лагранжа λ, соответствующий условию (17), и множители Лагранжа ω t для ограничений вида (16), получим, что P = {Plit } является
оптимальным распределением передаваемого сигнала тогда и только тогда, когда существуют неотрицательные λ и ω 1 , ω 2 , . . . , ω T такие, что выполняются соотношения
⎛
⎞%
$
n
E
M
h
= λ + ω t , Plit > 0,
hli
lj
δt ⎝
μlj
−
− C⎠
M
t
E
t
1 + hli Pli
1 + hlj Pli
λ + ω t , Plit = 0,
j=1
где
ω
t
⎧
⎪
⎪
⎨ 0,
если
⎪
⎪
⎩= 0,
если
N n
l=1 i=1
N n
l=1 i=1
46
μli Plit = P̄ t ,
(18)
μli Plit < P̄ t ;
λ
⎧
⎪
⎪
⎨ 0,
если
⎪
⎪
⎩= 0,
если
N T n
t=1 l=1 i=1
N T n
t=1 l=1 i=1
μli Plit = P̄ ,
μli Plit < P̄ .
Следующая лемма описывает тот вид, который имеют оптимальные стратегии.
Лемма 2. Оптимальные стратегии пользователя в задаче передачи сигнала с информацией о состоянии только каналов передачи имеют вид
%
0, l, i, t ∈ I0 ,
t
t
Pli (λ, ω ) =
Pli∗t (λ, ω t ), l, i, t ∈ I1 ,
где
I0 (λ) = {l ∈ [1, N ], i ∈ [1; n], t ∈ [1, T ] :
I1 (λ) = {l ∈ [1, N ], i ∈ [1; n], t ∈ [1, T ] :
n
j=1
n
E
μlj (hM
li − hlj ) λ
ωt
+ t + C},
t
δ
δ
E
μlj (hM
li − hlj ) >
λ
ωt
+
+ C},
δt
δt
j=1
причем выполняются соотношения (18), а Pli∗t (λ, ω t ) есть функция
n
hM
раметров λ и ω t , неявно заданная уравнением δ t ( j=1 μlj 1+hMli P ∗t
li li
t
относительно па−
hE
lj
∗t
1+hE
lj Pli
−C) =
λ+ω .
Аналогично теореме 1, применяя лемму 2, можно доказать приведенную ниже теорему 2 (о единственности оптимальной стратегии в случае обладания пользователем
информации о состоянии только каналов передачи), использующую следующие вспомогательные обозначения:
n
E
μlj (hM
(lo , io ) := argmaxl∈[1,N ], i∈[1,n]
li − hlj ) ,
j=1
H(λ; ω 1 , ω 2 , . . . , ω T ) :=
T N n
μli Plit (λ, ω t ),
t=1 l=1 i=1
W t (λ, ω t ) :=
n
N μli Plit (λ, ω t ).
l=1 i=1
Теорема 2. В случае, когда пользователь обладает информацией о состоянии
только каналов передачи, задача имеет единственное оптимальное решение P , причем P = {Plit (λ, ω t )} и
n
E
t
μl0 j (hM
(a) если C i0 − hl0 j ), то P = {Pli } = 0 с выигрышем, равным 0;
j=1
n
E
μlo j (hM
io − hlo j )
j=1
1
T
H(0; ω+
, . . . , ω+
) P̄ ,
(b) если C <
и
t
(b1) если
то P = {Plit (0, ω+
)}, где
%
= 0, если W t (0, 0) < P̄ t ,
t
ω+
единственный корень уравнения W t (0, ω t ) = P̄ t , если W t (0, 0) P̄ t ;
47
1
T
(b2) если H(0; ω+
, . . . , ω+
) > P̄ , то P = {Plit (λ∗ , ω t (λ∗ ))}, где
%
= 0, если W t (λ, 0) < P̄ t ,
ω t (λ)
единственный корень уравнения W t (λ, ω t ) = P̄ t , если W t (λ, 0) P̄ t ,
а λ∗ является единственным корнем уравнения
H̄(λ∗ ) = P̄ ,
где H̄(λ) = H(λ; ω 1 (λ), . . . , ω T (λ)).
Далее рассмотрим применение пользователем двухопционных стратегий, а именно
таких, при которых он посылает сигнал по l-му каналу в t-й момент времени лишь
в том случае, если коэффициент затухания l-го канала передачи hM
li больше некоторого
порогового значения τ . Причем мощность этого сигнала одинакова для всех состояний
l-го канала и равна Plt . Не умаляя общности, можно считать, что для каждого канала
M
M
M
l коэффициенты затухания hM
li расположены в порядке возрастания: hl1 , hl2 , . . . , hln .
M
Пусть kl ∈ [1, n] таково, что hM
l,kl −1 τ < hl,kl . Тогда в случае, если канал l находится
в состоянии i1 (где i1 kl − 1), значение передаваемого сигнала Plit будет равно 0, а
в случае нахождения в состоянии i2 (где i2 > kl ) – некоторой постоянной величине Plt ,
независящей от i. В результате получим такую оптимизационную задачу:
max υ(P ) = max
P
Pl
T
t=1
δ
t
n
N μli
l=1 i=kl
n
μlj (log(1 +
hM
li Pl )
− log(1 +
hE
lj Pl ))
−C
n
T N μli Pl
t=1 l=1 i=kl
j=1
при условии, что
Plt 0,
n
T N μli Plt P̄ ,
(19)
t=1 l=1 i=kl
N n
μli Plt P̄ t .
(20)
l=1 i=kl
Пусть выполнены условия (1) и (2). Из следствия к теореме Куна–Таккера имеем
для определения оптимальной стратегии пользователя следующую систему:
⎛
⎞%
$
n
n
n
E
M
h
= λ + ω t , Plt > 0,
hli
lj
−C
δt ⎝
μli
μlj
−
μli ⎠
M
t
E
t
1 + hli Pl
1 + hlj Pl
λ + ω t , Plt = 0,
j=1
i=k
i=k
l
l
где
ω
λ
t
⎧
⎪
⎪
⎨ 0,
если
⎪
⎪
⎩= 0,
если
N n
l=1 i=kl
N n
l=1 i=kl
⎧
⎪
⎪
⎨ 0,
если
⎪
⎪
⎩= 0,
если
μli Plt = P̄ t ,
μli Plt < P̄ t ;
N T n
t=1 l=1 i=kl
N T n
t=1 l=1 i=kl
(21)
μli Plt
= P̄ ,
μli Plt < P̄ .
Здесь λ и ω t – множители Лагранжа, соответствующие соответственно ограничениям
(19) и (20).
48
Лемма 3. Оптимальные стратегии пользователя в случае применения им двухопционных (вкл/выкл) стратегий имеют вид
⎧
n
n
n
⎪
λ
ωt
E
⎪
μli
μlj (hM
μli ,
⎨0,
li − hlj ) δ t + δ t + C
j=1
i=kl
i=kl
t
t
Pl (λ, ω ) =
n
n
n
⎪
λ
ωt
t∗
t
E
⎪
μli
μlj (hM
μli ,
⎩Pl (λ, ω ),
li − hlj ) > δ t + δ t + C
j=1
i=kl
i=k
1
T
причем для множителей Лагранжа λ, ω , . . . , ω выполнены соотношения (21), а
Plt∗ (λ, ω t ) – функция от параметров λ и ω t , неявно заданная уравнением
⎛
⎞
n
n
n
E
M
h
h
lj
li
μli
μlj (
−
)−C
μli ⎠ = λ + ω t .
δt ⎝
M P t∗
E P t∗
1
+
h
1
+
h
li l
lj l
j=1
i=k
i=k
l
Аналогично теореме 1, применяя лемму 3, можно доказать приведенную ниже теорему 3 (о единственности оптимальной двухопционной стратегии), использующую вспомогательные обозначения
n
n
E
μli
μlj (hM
li − hlj )
lo := argmaxl∈[1,N ]
j=1
n
i=kl
,
μli
i=kl
H(λ; ω 1 , ω 2 , . . . , ω T ) :=
T N
n
μli Plt (λ, ω t ),
t=1 l=1 i=kl
W t (λ, ω t ) :=
N
n
μli Plt (λ, ω t ).
l=1 i=kl
Теорема 3. Задача с двухопционными (вкл/выкл) стратегиями пользователя
имеет единственное оптимальное решение P = {Plt }, причем,
(a) если
n
n
E
μlo i
μlo j (hM
lo i − h lo j )
C
j=1
n
i=klo
,
μlo i
i=klo
то P =
{Plt }
= 0 с выигрышем, равным 0;
(b) если
n
C<
i=kl0
μl0 i
n
E
μl0 j (hM
l0 i − h l0 j )
j=1
n
μl0 i
i=kl0
и
1
T
t
, . . . , ω+
) P̄ , то P = {Plt (0, ω+
)}, где
(b1) если H(0; ω+
49
%
t
ω+
= 0, если W t (0, 0) < P̄ t ,
единственный корень уравнения W t (0, ω t ) = P̄ t , если W t (0, 0) P̄ t ;
1
T
, . . . , ω+
) > P̄ , то P = {Plt (λ∗ , ω t (λ∗ ))}, где
(b2) если H(0; ω+
%
= 0, если W t (λ, 0) < P̄ t ,
t
ω (λ)
единственный корень уравнения W t (λ, ω t ) = P̄ t , если W t (λ, 0) P̄ t ,
а λ∗ – единственный корень уравнения
H̄(λ∗ ) = P̄ ,
где H̄(λ) = H(λ; ω 1 (λ), . . . , ω T (λ)).
Теперь рассмотрим ситуацию, когда при передаче сигнала пользователем накладывается условие только на общую среднюю мощность передаваемого сигнала. Данная
модель отличается от указанных выше лишь отсутствием ограничений на среднюю
мощность в каждый временной слот. Как и ранее, возможно рассмотрение следующих
случаев: 1) пользователь обладает полной информацией о состоянии каналов передачи;
2) пользователь обладает информацией о состоянии только каналов передачи; 3) пользователь использует двухопционную (вкл/выкл) стратегию. Рассмотрим постановку задачи на примере случая полной информации. Будем искать оптимальную функцию расE t
t
пределения мощности P = {P (hM
li , hlj , δ )} = {Plij }, возвращающей максимум функции
пропускной способности, которая определяется как
υ(P ) =
T
t=1
δ
t
n
N μli
l=1 i=1
n
μlj (log(1 +
t
hM
li Plij )
− log(1 +
t
hE
lj Plij ))
−C
j=1
n
N l=1 i=1
μli
n
t
μlj Plij
,
j=1
t
где стратегии пользователя P = {Plij
} удовлетворяют условиям
t
Plij
0,
n
T N μli
t=1 l=1 i=1
n
t
μlj Plij
P̄ .
j=1
Предположим выполнение условия (2). Из следствия к теореме Куна–Таккера найдем
необходимые и достаточные условия, которым должны удовлетворять функции расt
, возвращающие максимум для функции υ(P ):
пределения передаваемого сигнала Plij
δt
hE
hM
lj
li
−
−C
t
EP t
1 + hM
P
1
+
h
li lij
lj lij
$%
= λ,
λ,
t
Plij
> 0,
t
Plij
= 0,
где
λ
⎧
⎪
⎪
⎨ 0,
если
⎪
⎪
⎩= 0,
если
N T n
t=1 l=1 i=1
N T n
t=1 l=1 i=1
μli
μli
n
j=1
n
j=1
t
μlj Plij
= P̄ ,
(22)
t
μlj Plij
< P̄ .
Как и ранее, сформулируем лемму о виде оптимальных стратегий пользователя.
50
Лемма 4. Оптимальные стратегии для задачи полной информации в случае ограничений только на общую среднюю мощность имеют вид
⎧
⎪
⎨0, *l, i, j, t ∈ I0 ,
2
t
Plij (λ) = 1
1
1
⎪
− hM
+
⎩2(
hE
lj
li
4
C+ λt
δ
1
hE
lj
−
1
hM
li
−
1
hE
lj
+
1
hM
li
),
l, i, j, t ∈ I1 ,
где
λ
+ C},
δt
λ
− hE
lj > t + C},
δ
E
I0 (λ) = {l ∈ [1, N ], i, j ∈ [1; n], t ∈ [1, T ] : hM
li − hlj I1 (λ) = {l ∈ [1, N ], i, j ∈ [1; n], t ∈ [1, T ] : hM
li
причем для λ выполнены соотношения (22).
Аналогично теореме 1, применяя лемму 4, можно доказать приведенную ниже теорему 4 о единственности оптимальной стратегии для задачи передачи сигнала при наличии слушателя в случае полной информации о состоянии каналов передачи с ограничениями только на общую среднюю мощность, причем в этой теореме используются
следующие вспомогательные обозначения:
E
(lo , io , j o ) := argmaxl∈[1,N ], i,j∈[1,n] (hM
li − hlj ),
H(λ) :=
N T t=1 l=1 i=1
μli
t
μlj Plij
(λ).
j=1
Теорема 4. В случае наличия ограничений только на общую среднюю мощность
передаваемого сигнала и обладания пользователем полной информации о состоянии
каналов в задаче имеется единственное оптимальное решение:
(a) если
E
C hM
l0 i0 − hl0 j 0 ,
t
} = 0 с выигрышем, равным 0;
то P = {Plij
(b) если
E
C < hM
l0 i0 − hl0 j 0 ,
t
(λ∗ )} и выигрыш равен υ(P (λ∗ )), где
то стратегия P (λ∗ ) = {Plij
%
∗
λ =
0,
единственый корень уравнения H(λ) = P̄ ,
если H(0) P̄ ,
если H(0) > P̄ .
5. Численное моделирование. Приведем два примера численного моделирования. В первом из них (рис. 1) демонстрируется, как меняются выигрыши пользователя в следующих различных случаях: 1) с полной информацией о состоянии каналов; 2) с информацией только о состоянии каналов передачи; 3) когда используется двухопционная стратегия. Будем считать, что передача осуществляется мгновенно по одному каналу, в котором имеется пять различных состояний, вероятности нахождения в которых равны μ = [0.2; 0.2; 0.2; 0.2; 0.2]. Коэффициенты затухания будут равны соответственно hM = [0.7; 0.8; 0.9; 1.0; 1.1] для главного канала
51
Рис. 1. Зависимость выигрыша от коэффициента
стоимости передачи сигнала в трех различных случаях
1 – полная информация о состоянии каналов передачи; 2 – информация только
о состоянии каналов передачи; 3 – применение пользователем двухопционной стратегии.
и hE = [0.2; 0.3; 0.4; 0.5; 0.6] для прослушивательного. Максимальную среднюю мощность сигнала будем считать равной P̄ = 1.0, а параметр τ = 0.1. Издержки передачи
сигнала меняются от 0 до 1, и вычисляется значение выигрыша пользователя в трех
рассмотренных случаях. Из рис. 1 видно, что при малых издержках способ передачи данных пользователем при применении им двухопционной стратегии практически
не уступает по эффективности случаю, когда известна лишь информация о главном
канале. Но с возрастанием издержек применение двухопционной стратегии становится
менее эффективным. Вместе с тем выигрыш в случае полной информации о каналах
при средних значениях издержек приближается к величине выигрыша в случае, когда
известна информация лишь о состоянии каналов передачи. При больших уровнях издержек выигрыш во всех случаях стремится к нулю, так как теряется смысл вообще
передавать сигнал какой-либо мощности.
Во втором примере (рис. 2) показывается, как зависят от времени передачи сигнала (T ∈ [1, 30]) выигрыши пользователя в таких различных случаях: 1) с полной информацией о состоянии каналов; 2) с информацией только о состоянии каналов передачи; 3) когда применяется двухопционная стратегия (считаем, что мощность сигнала будет изменяться с течением времени для каждого канала). Будем рассматривать процесс передачи сигнала по одному каналу, который может находиться в одном из пяти различных состояний. Вероятности нахождения в этих состояниях равны μ = [0.2; 0.2; 0.2; 0.2; 0.2]; коэффициенты затухания – соответственно
hM = [0.7; 0.7; 0.8; 0.9; 1.0] для главного канала и hE = [0.1; 0.2; 0.3; 0.4; 0.5]
52
Рис. 2. Зависимость выигрыша от времени, затраченного на передачу
Обозначения см. рис. 1.
для прослушивательного. Максимальную среднюю мощность сигнала примем равной
P̄ = 1.0, а параметр τ = 0.1. Стоимость передачи сигнала равна 0.1, а коэффициент
обесценивания в каждый момент времени считаем равным 0.7. Примем, что ограничения наложены только на общую среднюю мощность.
6. Заключение. В работе изучалась задача оптимальной передачи сигнала пользователем при прослушивании в беспроводной сети. Функцией выигрыша пользователя является критерий Шеннона. Обобщены результаты работы [7] на случай, когда
на процесс трансляции сигнала накладывается условие в виде стоимости за передачу информации, а также на случай, когда сам процесс передачи может происходить
не одномоментно, а на протяжении определенного количества временных слотов. Исследовалась модель передачи данных, когда в каждый временной слот наложены ограничения на среднюю мощность сигнала, и были рассмотрены следующие три случая:
пользователь, передающий сигнал, обладает полной информацией о состоянии каналов;
пользователь знает только информацию о состоянии каналов передачи; пользователь
применяет двухопционную (вкл/выкл) стратегию передачи сигнала. Также была исследована модель, когда на процесс передачи сигнала наложены только ограничения
на общую среднюю мощность сигнала. Для каждого из приведенных случаев конструктивным способом доказана единственность оптимальной стратегии, что позволило разработать алгоритмы ее построения и провести численное моделирование.
Литература
1. Bennett C., Brassard G., Crepeau C., Maurer U. M. Generalized privacy amplification // IEEE
Trans. on Information Theory. 1995. Vol. 41. P. 1915–1923.
53
2. Garnaev A., Trappe W. An eavesdropping game with SINR as an objective function // Lecture
Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering. 2009.
Vol. 19. P. 142–162.
3. Hero A. E. Secure Space-Time Communication // IEEE Trans. Information Theory. 2003. Vol. 23.
P. 3235–3249.
4. Koorapaty H., Hassan A. A., Chennakeshu S. Secure Information Transmission for Mobile Radio //
IEEE Trans. Wireless Commun. 2003. Vol. 41. P. 52–55.
5. Liang Y., Poor H. V., Shamai S. Secure Communication over Fading Channels // IEEE Transactions
on Information Theory, Special issue on Information Theoretic Security. 2008. Vol. 54, N 6. P. 2470–2492.
6. Wyner A. The wire-tap channel // Bell. Syst. Tech. J. 1975. Vol. 54, N 8. P. 1355–1387.
7. Gopala P. K., Lai L., El Gamal H. On the Secrecy Capacity of Fading Channels // IEEE Trans. on
Information Theory. 2008. Vol. 54, N 10. P. 4687–4698.
8. Maurer Ueli M., Wolf Stefan. Information-theoretic key agreement: From weak to strong secrecy for
free // EUROCRYPT. 2000. P. 351–368.
9. Shannon C. E. A Mathematical Theory of Communication // Bell System Tech. Journal. 1948. Vol. 27.
P. 379–423, 623–656.
10. Вишневский В. М., Ляхов А. И., Портной С. Л., Шахнович И. В. Широкополосные беспроводные сети передачи информации. М.: Техносфера, 2005. 592 с.
11. Shannon C. E. Communication theory of secrecy systems // Bell System Tech. Journal. 1949. Vol. 28.
P. 656–715.
12. Altman E., Avrachenkov K., Garnaev A. A jamming game in wireless networks with transmission
cost // Lecture Notes in Computer Science. 2007. Vol. 4465. P. 1–12.
13. Leung-Yan-Cheong S. K., Hellman M. E. The Gaussian Wire-Tap Channel // IEEE Trans. on
Information Theory. 1978. Vol. 24. P. 451–456.
14. Liang Y., Poor H. V. Generalized multiple access channels with confidential messages // IEEE
Trans. on Information Theory. 2007. P. 112–122.
Статья рекомендована к печати проф. Л. А. Петросяном.
Статья принята к печати 16 декабря 2010 г.
Документ
Категория
Без категории
Просмотров
4
Размер файла
432 Кб
Теги
данных, передача, утечки, информация
1/--страниц
Пожаловаться на содержимое документа