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

ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА

Сер. 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.

© М. А. Золотухин, А. Ю. Гарнаев, В. В. Захаров, 2011

Статья имеет следующую структуру. В п. 2 приводится постановка задачи, в п. 3 дается конструктивное решение задачи и доказывается его единственность, в п. 4 рассмотрены модификации основной модели, а в п. 5 продемонстрированы результаты численного моделирования.

2. Постановка задачи. Рассмотрим модель, являющуюся обобщением модели [7] передачи данных в беспроводной сети при наличии прослушивающего агента на случай, когда процесс передачи данных происходит не одномоментно, а за нескольких временных слотов с учетом влияния тарифов использования сети на поведение пользователя. Итак, пользователь пытается осуществлять передачу информации в течение нескольких временных слотов Т по N каналам. При этом в сети, кроме пользователя, передающего информацию, находится пассивный агент, который осуществляет прослушивание по своим специальным каналам. Предположим, что все рассматриваемые каналы являются каналами с аддитивным белым гауссовским шумом (АБГШ). АБГШ -вид мешающего воздействия в канале передачи информации, который характеризуется равномерной спектральной плотностью, нормально распределенным значением амплитуды и аддитивным способом воздействия на сигнал. Это наиболее распространенный вид шума, используемый для расчета и моделирования систем радиосвязи.

Каждый рассматриваемый канал характеризуется коэффициентом затухания Нм = (Нм, Н^,..., НПМ), который является вектором значений дискретной случайной величины, т. е. коэффициент затухания 1-го канала передачи данных равен Н^ с вероятностью ¡л^ (I € [1,пм]). Аналогично коэффициент затухания 1-го канала для прослушивания равен с вероятностью ¡Е (з € [1,пе]). Считается, что рассматриваемые случайные величины независимые [7]. Опишем случай, когда пользователь обладает полной информацией о состоянии всех каналов передачи, ему известно распределение Ьм и НЕ для каждого I.

В работах [13, 14] доказано, что в случае АБГШ каналов связи минимальная верхняя оценка скорости передачи данных, при которой конфиденциальная информация идеально скрыта от прослушивающего агента, определяется следующим обобщением формулы Шеннона:

С = 1о^1 + НМР) - 1о^1 + НЕ Р),

где Р - мощность сигнала, переданного по 1-му каналу. В этом выражении Са представляет собой разность между пропускной способностью каналов передачи и пропускной способностью каналов для прослушивания.

При передаче информации за Т временных слотов будем полагать, что ценность информации, переданной во временной слот Ь, изменяется в соответствии с дисконтирующим фактором 5г € (0,1]. Это побуждает пользователя передавать большую часть информации либо в начале сеанса связи, либо, наоборот, в его конце.

Важным параметром при оценке полезности использования сети является цена, которую пользователь платит за мощность при передаче. Учет стоимости передачи сигнала, а следовательно, и существующего тарифа в сети важен, так как в зависимости от этого тарифа существенно может измениться поведение пользователя: от абсолютного отказа от сети до использования ее в полном объеме.

Таким образом, определим функцию выигрыша пользователя как ожидаемую величину обобщенной пропускной способности Шеннона Са с учетом дисконтирующего фактора и затрат:

КР )=£

N пм пЕ N пм пЕ

£ £ ^'Н £ Vе (^(1+Ни Риз) - к^(1 +Риз Vе Рщ

I = 1 ¿=1 з = 1 I = 1 ¿=1 з = 1

Мощность сигнала Р — {Р(Нм,НЕ,3*)} = {Р^} измеряется в децибелах (дБ); С есть некоторый коэффициент стоимости, который находится как С — Сг* • Сспь. Здесь Сг* - тариф за используемую мощность - измеряется в рублях за децибел (руб./дБ), а Сспу - некоторый переводной коэффициент, подобранный таким образом, чтобы С изменялся от 0 до 1 (измеряется в нат/руб.). Таким образом, единицами измерения целевой функции и являются наты (нат).

Стратегиями пользователей являются функции Р — {Р^} с неотрицательными компонентами: Р^ ^ 0, I — 1,...,М, г — 1,..., пм, 3 — 1пЕ, Ь — 1,...,Т, которые удовлетворяют ограничениям как на среднюю мощность передаваемого сигнала в каждый временной слот, так и на общую среднюю мощность:

Т N пм пЕ

££5>м Е мЕ Р^ < Р,

*=1 1 = 1 М=1 3=1 N пм пЕ

ИЦмМТ. 4 Р3 < р •

1 = 1 М=1 3 = 1

Предположим, что пропускная способность каналов позволяет передать весь сигнал пользователю, а именно, выполнено неравенство

]Тр* >Р.

*=1

Следуя [7], считаем, что пользователю имеет смысл передавать сигнал только при условии

нМ >Не, I — 1,...,м,

1, . . . , им, 3 — 1,..., ПЕ.

3. Решение задачи. При выполнении (2) функция и(Р) вогнута относительно Р — {Рщ }, поскольку гессиан функции (1) есть отрицательно полуопределенная матрица.

Из теоремы Куна-Таккера следует, что Р — {Рщ } является оптимальным распределением передаваемого сигнала тогда и только тогда, когда существуют неотрицательные Л и и!1,и2,... ,иТ (множители Лагранжа) такие, что выполняются соотношения

3*

нм

н М

1 + НМ Р*М3

нЕ

н 3

1 + нЕ РМз

С

Л + и*, РМз > 0,

< Л + и*

Р *

Р1 Мз

где

N п

> 0, 0,

^ 0, 0,

если

если

если

если

ЕЕм I м Е м I з РМ

р*

I = 1 М=1 N п

I = 1 М=1 Т N п

3 = 1 п

Е I

3=1

Е Е мм Е Р[м3 < р

м Е М13 Р1г3 — р,

*=1 I = 1 М=1 Т N п

3=1

£ £ £ мк £ М3Р[м3 < Р.

*=1I= 1м=1

3=1

Выведем общий вид оптимальных решений задачи как функций от множителей Лагранжа.

г

и

Л

Лемма 1. Все оптимальные решения в задаче передачи сигнала с полной информацией имеют следующий вид:

'0, 1,1,з,г е 10(А,ш1,ш2,...,шТ),

Рщ (А

2 V \Ш~Ш) + а+ \

Н% НП) С +

Н % п щ ) I

где

10{А,ш1,ш2,...,шТ) = {I е [1,Ж], 1,3 е [1,п], г е [1,Т] : нММ - < (Ш + А)/5г + с}, Р(А,ш1,ш2,...,шТ) = {I е [1,Ж] , 1,3 е [1,п], г е [1,Т] : нМ - нЕ% > (ш + А)/51 + с},

причем выполняются соотношения (5).

Доказательство. Пусть Р = {Р*ч } - оптимальная стратегия пользователя. Если Р^ = 0, то из соотношений (4) следует, что Н^ — Н^ ^ ("* + А)/6* + С, т. е. (1,1,],1) € 10. Если Р^ > 0, тогда из (4) вытекает, что

Решив это уравнение относительно Рщ, получим решение в виде второй строки (6), что завершает доказательство леммы.

Данная лемма указывает на важное свойство оптимального решения: оно монотонно убывает как функция относительно множителей Лагранжа. Теперь перейдем к нахождению оптимальных значений множителей Лагранжа. С этой целью введем вспомогательные обозначения

(Г^0,3°) := а^тах,^е[1М(Ни — Щ),

N п п

Ш*(А,ш4) := ££ щ Р1Ц (А,ш4),

I =1 г=1 ¿=1

Т N п п / Т \

Н (А; ш1,ш2,...,шТ) := £ £ гЦ ЩЧ Р.% (А, "*) = £ Ш '(А, ш*) .

1=1 1 = 1 г=1 ¿=1 V 4=1 )

Используя лемму 1, докажем следующую теорему, в которой приведена оптимальная стратегия и доказана ее единственность для задачи передачи сигнала при наличии слушателя в случае полной информации о состоянии каналов.

Теорема 1. В случае полной информации о состоянии каналов в задаче имеется единственное оптимальное решение Р = {Р[ч (А, ш4)}, причем,

(a) если

С ^ Н1°г° НЕ¿о ,

то Р = {Р[ч} = 0 c выигрышем, равным 0;

(b) если

С < Н1°г° — НЕ°3°

Р = [Р^ (0, ш+)} где

Н(0;^,...,ш+) < Р,

( = 0, если Ш *(0, 0) < Р

\ корень уравнения Ш*(0,ш*) = Р*, если Ш* (0,0) > Р*;

Н (0; ^ ,...,ш+) >Р,

то Р = [Р* (Х*,шг(Х*)), где

ш^)

0, если Ш0) < Р*

корень уравнения Шг(\,иг) = Р*, если Шг(Х, 0) ^ Р* а X* является единственным корнем уравнения

Н(Х*) =Р,

где Н(Х) = Н(X; ш1^),..., шТ(X)).

Доказательство. По лемме 1 Р является оптимальной стратегией и

удовлетворяют следующим соотношениям:

тогда и только тогда, когда она имеет вид Р = [Р*з (X, ш*)} из (6), причем X, ш1, . ..,шТ

> 0, если Шt(X,шt)=Pt = 0, если Шt(X,шt) < Р*

, ь е [1,Т],

X

^ 0, если Н (X; ш ,ш ,...,ш

Р,

0, если Н (X; ш1, ш2 ,...,шТ) < Р.

Таким образом, надо найти X;ш1,ш2,...,шТ, удовлетворяющие (13) и (14), для того чтобы построить оптимальную стратегию. Ниже мы не только конструктивным обра-

1 2 Т

зом определяем такие X; ш1, ш2 ,...,шТ, но и доказываем их единственность по единой схеме для подслучаев (а), (Ь1) и (Ь2), описывающих все возможные альтернативы. Первоначально отметим, что функции Н(X; ш1, ш2,..., шТ) и Шш*), Ь е [1, Т], монотонно убывают при возрастании одного из множителей Лагранжа при фиксированных остальных.

(a) Пусть выполняется (7) и Р = [Р^ (X, ш*)} - оптимальное решение, тогда 11(X, ш1, ш2,..., шТ) = 0 для любых X, ш1, ш2,..., шТ. Поэтому Р = 0. Для такой стратегии Н(X; ш1,ш2,..., шТ) =0 и Шш*) = 0 для любого Ь. Поэтому, в силу (13) и (14), единственными возможными значениями лагранжевых множителей являются нулевые: X = 0, ш1 = 0, ш2 = 0,... ,шТ = 0. Таким образом, если оптимальное решение существует, то оно должно быть равно Р = [РЩ (0,0)}, которое, очевидно, удовлетворяет (13) и (14) при выполнении условия (7), а следовательно, и является оптимальным.

и

то

ш

+

ш

по аргументу и4, и+ определяются (10) единственным образом. Перейдем к нахождению оптимальных множителей Лагранжа А и и1 в двух подслучаях.

(Ъ1) Пусть выполнено (9). Тогда, в силу монотонного убывания функции Н (А; и+ ,...,и+) по А и соотношений (14), оптимальное А должно равняться нулю. Для такого А соотношения (13) примут вид

> 0, если W4(0,и4) = Р4

и < ., ъ Е \1,1 I,

' 0, если W4(0,и4) <Р4 1 -1

и, в силу монотонного убывания функций W4(0, и4) по аргументу и4, имеют единственное решение и4 = и+, определенное в (10). Таким образом, если оптимальное решение существует, то оно должно быть равно Р = {Р^(0,и+)}, которое, в силу приведенных рассуждений, очевидно, удовлетворяет (13) и (14) при выполнении условий (8) и (9), а следовательно, является оптимальным.

(Ъ2) В силу строгого монотонного убывания W4(А,и4) по и1 при фиксированном А, пока W4(А, и4) > 0, множитель Лагранжа и4 однозначным образом определяется из (13) соотношением (12). Кроме того, полученные таким образом функции и4(А) непрерывные и строго монотонно убывают по А, пока они положительны. Оптимальное А находится как решение задачи

Г > 0, если Н(А) = Р,

\ = 0, если Н

где Н(А) = Н (А; и1(А),...,ит (А)). В силу (11), Н(0) = Н (0; и+ ,...,и+) > Р. Тогда по строгому монотонному убыванию функции Н (А; и1,и2,...,ит) по А и соотношений (14) оптимальный множитель Лагранжа А должен быть положительным. Функции и4(А) удовлетворяют соотношениям (13) для любого А. Функцию Н(А) можно представить в следующем виде:

Н(А)= Е W*(А,и*(А)) + Е W4(А, 0) =

Р.ш*(Х)>0 Р.ш*(Х) = 0

= Е рг + Е w4(а, 0).

Р.ш*(Х)>0 г-.ш*(Х) = 0

Предположим, что оптимальное А таково, что и4(А) > 0 для всех Ъ. Тогда

т

Н(А) = (по (17)) = ^Р4 > (по (1)) >Р,

г=1

а это противоречит (15) и показывает, что оптимальное А таково, что существуют Ъ, для которых и4 (А) = 0, причем с увеличением А возрастает и количество слагаемых в сумме, где и4(А) = 0. Функции W4(А, 0) являются монотонно убывающими по А, следовательно, функция Н(А) также будет монотонно убывать по А. Кроме того, функция Н(А) непрерывна по А, в силу непрерывности функции и4 (А) и вида функции Н (А; и1 ,и2,... ,ит). По (6) Н(А) = 0 при достаточно больших значениях А. Таким образом, существует некоторое А* такое, что Н(А*) = Р. По определению А* и вида функций и4(А) полученные множители Лагранжа А*,и1(А*),... ,ит(А*) удовлетворяют (13) и (14). Таким образом, если оптимальное решение существует, то оно должно быть равно Р = {Рщ (А* ,и4(А*)}, которое, в силу приведенных рассуждений, очевидно,

удовлетворяет (13) и (14) при выполнении условий (8) и (11), а следовательно, и является оптимальным.

Тот факт, что рассмотренные случаи охватывают все возможные альтернативы, завершает доказательство теоремы.

4. Обсуждение возможных моделей передачи сигнала. Произведем исследование других возможных моделей передачи данных пользователем в беспроводной сети при наличии прослушивающего агента. Когда в каждый временной слот наложены ограничения на среднюю мощность сигнала, рассмотрим следующие случаи: 1) пользователь, передающий информацию, знает информацию о состоянии только каналов для передачи; 2) пользователь, передающий информацию, использует двухопционную (вкл/выкл) стратегию. Кроме того, рассмотрим модель, когда на процесс передачи сигнала наложены только ограничения на общую среднюю мощность сигнала. В данных задачах с помощью рассуждений, аналогичных приведенным в п. 2, были получены оптимальные стратегии и произведено доказательство теорем об их единственности.

Рассмотрим случай, когда пользователю доступна не вся информация, а лишь информация о состоянии каналов для передачи. В этом случае функция распределения мощностей не зависит от коэффициентов затухания каналов прослушивания P = {P(hff, ¿l)} = {Pli}. Таким образом, имеем следующую оптимизационную задачу:

max v(P) = max 5l

l ii

N

t=1

£ !>Ii £ m Ij(iog(i + htf Pli) - iog(i + hEPli)) - m IiPli

l=1

Будем по-прежнему предполагать, что компоненты стратегий пользователя Р^ неотрицательны и удовлетворяют граничным условиям

N

££/iPi < pl,

l = 1 i=l T N n

££5>iPti < p

/l iP1

t=1 l = 1 i=1

Предположим, что выполнены условия (1) и (2). Тогда, воспользовавшись теоремой Куна-Таккера и вводя множитель Лагранжа А, соответствующий условию (17), и множители Лагранжа и4 для ограничений вида (16), получим, что Р = {Р^} является оптимальным распределением передаваемого сигнала тогда и только тогда, когда су-

л 1 2 Т

ществуют неотрицательные А и и1 ,и2, ...,иТ такие, что выполняются соотношения

4

è + i + щп) JlOW, p*= o,

где

Ш

N n

> 0, если £ E /IiPli = P

t ) l = 1 i=1 N n

0, если £ £ /iiPli < P

i=1 i=1

Т N п

> 0, если £ £ £ щ.Р. = Р,

г=1I= 1.=1 Т N п

0, если £ £ £ щ.Р*. < Р.

4=1 I =1 г=1

Следующая лемма описывает тот вид, который имеют оптимальные стратегии.

Лемма 2. Оптимальные стратегии пользователя в задаче передачи сигнала с информацией о состоянии только каналов передачи имеют вид

где

п

_ П г И ЛГ1 ~ и. 1 -А,— и т . .. п1н _ ^ _ _

А

/о(А) = {1е [1, N1 г е [1; п], t € [1, Т] : Е-«У ~ Щ) < ^ + ж + С},

А (А) = {1е [1, N1 г е [1; п],* € [1, Т] : ~ Щ) > ^ + ж + С},

3=1

А ^

<7г ~ + ¿Г

3=1

причем выполняются соотношения (18), а Р*.г(А,иг) есть функция относительно параметров А и и>1, неявно заданная уравнением <54(£™=1 ~ 1) ~~ С) = А + и4.

Аналогично теореме 1, применяя лемму 2, можно доказать приведенную ниже теорему 2 (о единственности оптимальной стратегии в случае обладания пользователем информации о состоянии только каналов передачи), использующую следующие вспомогательные обозначения:

п

3=1

Т N

Н(А; и1,и2,...,иТ):=ЕЕ ЕЩР(А, ^),

г=1 1=1 г=1

N п

W*(А,и*) :=ЕЕЩ.Р.(А,и*).

=1 .=1

Теорема 2. В случае, когда пользователь обладает информацией о состоянии только каналов передачи, задача имеет единственное оптимальное решение Р, причем Р = {Р.(\,иг)} и

п

(a) если С ^ £ що3(Нм — Н^О ), то Р = {Р*} = 0 с выигрышем, равным 0;

3=1 . 3 .

п

(b) если С < £ щ 1 о3 (Н™ — НЕ,3) и

3=1 . 3

(Ь1) если Н (0; ,...,иТ) < Р, то Р = {Р.(0,и*+)}, где

4 \= 0, если W4(0, 0) < Р\ и + \ — —

I единственный корень уравнения W4(0,и4) = Ресли W4(0,0) ^ Рг;

А

Н (0; и+ ,...,и+) >Р, то Р = {Р[М(А* ,и4(А*))}, где

{= 0, е°Ли Ш4(А, 0) < Р^

1 единственный корень уравнения Ш 4(А,и4) = Р4, если Ш 4(А, 0) ^ Р а А* является единственным корнем уравнения

Н(А*) =Р,

где Н(А) = Н(А; их(А),..., иТ(А)).

Далее рассмотрим применение пользователем двухопционных стратегий, а именно таких, при которых он посылает сигнал по 1-му каналу в ¿-й момент времени лишь в том случае, если коэффициент затухания 1-го канала передачи Нм больше некоторого порогового значения т. Причем мощность этого сигнала одинакова для всех состояний 1-го канала и равна Р[. Не умаляя общности, можно считать, что для каждого канала I коэффициенты затухания Нм расположены в порядке возрастания: , Нм,..., . Пусть к € [1, п] таково, что НМк _ 1 ^ т < Нм . Тогда в случае, если канал I находится

в состоянии ¿1 (где г1 ^ к — 1), значение передаваемого сигнала Р[М будет равно 0, а в случае нахождения в состоянии ¿2 (где ¿2 > кI) - некоторой постоянной величине Р[, независящей от г. В результате получим такую оптимизационную задачу:

т

4 = 1

при условии, что

тах и(Р) = тах

' N п п Т N п

Е Е»1 ; Е ^ 11 (1оё(!+нМ р ) - м1+НЕ Р )) - ^Е Е Е»1 Р

.1 = 1 г=к1 1=1

4 = 1 I =1 г=к,

Р[ > 0,

Т N п

ИИИ^ Р < р,

4=1 I =1 г=к1 N п

Р < р4

1 = 1 г=к\

Пусть выполнены условия (1) и (2). Из следствия к теореме Куна-Таккера имеем для определения оптимальной стратегии пользователя следующую систему:

6г

1 ^ щ I з

3 = 1

Нм пн

НЕ У

^ М=к

1 + нМр14 1 + НЕ3Р4

где

з

N

—

М=к,

= А + и4, < А + и4,

Р* > 0,

Р4

р

> 0, если £ Е №мРг

1 = 1 г=к\ N п

если £ Е №IгР1 < Р4;

1 = 1 М=к[ Т N п

> 0, если £ £ Е № гР1 = Р,

А

4=11 = 1 М=к1 Т N п

0,

если £ £ Е №мР4 < Р.

4=1 1 = 1 М=к1

Здесь А и и4 - множители Лагранжа, соответствующие соответственно ограничениям (19) и (20).

и

Лемма 3. Оптимальные стратегии пользователя в случае применения им двух-опционных (вкл/выкл) стратегий имеют вид

пп

Р*(А,и )=< г=к1 3=1п п *=к' п

£ № £ + + с £

г=к 3=1 г=к

причем для множителей Лагранжа А,и1,..., иТ выполнены соотношения (21), а Р[*(А,и4) - функция от параметров А и и4, неявно заданная уравнением

пп

. Нм не п 1

* (5> £(ттш^ ~ гт№) - с 5>) =А+•

{г=к1 3 = 1 1 3 1 г=к

Аналогично теореме 1, применяя лемму 3, можно доказать приведенную ниже теорему 3 (о единственности оптимальной двухопционной стратегии), использующую вспомогательные обозначения

пп

£ щи £

° ъ=к\ 3 = 1

I := а^тах^^дг]---,

щ .

г=к\ Т N п

Н (А; и1,и2,...,иТ ):=ЕЕ Е Щ * и*),

Ь=1 1 = 1 г=кч

N п

W4(А, и4) :=ЕЕ Щ,Р(А,и4).

1 = 1 г=к\

Теорема 3. Задача с двухопционными (вкл/выкл) стратегиями пользователя имеет единственное оптимальное решение Р = {Р[}, причем, (а) если

С >

£ ЩIЩIо3

г=кхо 3 = 1

£ Щ°г

г=к\о

то Р = {Р[} = 0 с выигрышем, равным 0; (Ь) если

£ щ£ що3

.=к о 3=1

с< —-—-

щ о.

г=к1о

(Ь1) если Н (0; ,...,иТ) < Р, то Р = {Р[(0,и\_)}, где

и

I 1 = 0, если Ш4(0, 0) < Р4, \ — — 1 единственный корень уравнения Шг(0,иг) = Ресли Ш 4(0,0) ^ Р4;

(Ь2) если Н (0; ,...,ш"Т) > Р, то Р = {Р[(А* ,^(А*))}, где

1= 0, если Ш4(А, 0) < Р

I единственный корень уравнения Ш г(А,шг) = Р4, если Ш 4(А, 0) ^ Р4

а А* - единственный корень уравнения

Н(А*) =Р,

где Н(А) = Н (А; ^1(А),..., шТ (А)).

Теперь рассмотрим ситуацию, когда при передаче сигнала пользователем накладывается условие только на общую среднюю мощность передаваемого сигнала. Данная модель отличается от указанных выше лишь отсутствием ограничений на среднюю мощность в каждый временной слот. Как и ранее, возможно рассмотрение следующих случаев: 1) пользователь обладает полной информацией о состоянии каналов передачи; 2) пользователь обладает информацией о состоянии только каналов передачи; 3) пользователь использует двухопционную (вкл/выкл) стратегию. Рассмотрим постановку задачи на примере случая полной информации. Будем искать оптимальную функцию распределения мощности Р = {Р(Нм, НЕ= {Р^у }, возвращающей максимум функции пропускной способности, которая определяется как

т

г

>(р ) = £ *

£ £ МI* £ М1з (1°ё(! + Ьи Риз) - 1ое(1 + НЕ Риз)) - С £ МI* £ М1з Рь%

_1 = 1 ¿=1 3=1 I = 1 ¿=1 3 = 1

где стратегии пользователя Р = {Р[у } удовлетворяют условиям

Т N п п

> 0 ЕЕЕмI<£м у< р.

4=1 I =1 г=1 у=1

Предположим выполнение условия (2). Из следствия к теореме Куна-Таккера найдем необходимые и достаточные условия, которым должны удовлетворять функции распределения передаваемого сигнала Р[у, возвращающие максимум для функции и(Р):

А^___1__с\1=х> р^>0'

+ 1 + Крн3 До, п3 = о,

где

Т N п п

> 0, если £ £ Е м* Е = p,

4=11 =1 г=1 у=1

Т N п п

° если £ £ £ № £ МИРШ < р.

4=11 =1 г=1 у=1

Как и ранее, сформулируем лемму о виде оптимальных стратегий пользователя. 50

Лемма 4. Оптимальные стратегии для задачи полной информации в случае ограничений только на общую среднюю мощность имеют вид

0, I, г, ], Ь е 1о,

Р{ц (А) =

где

причем для X выполнены соотношения (22).

Аналогично теореме 1, применяя лемму 4, можно доказать приведенную ниже теорему 4 о единственности оптимальной стратегии для задачи передачи сигнала при наличии слушателя в случае полной информации о состоянии каналов передачи с ограничениями только на общую среднюю мощность, причем в этой теореме используются следующие вспомогательные обозначения:

(Г^0,]°) := а^тах,^^^-^]^ - ^),

Т N

Н (X) :=ЕЕ Е^Е р1% (X)•

*=1 1=1 Щ=1 1=1

Теорема 4. В случае наличия ограничений только на общую среднюю мощность передаваемого сигнала и обладания пользователем полной информации о состоянии каналов в задаче имеется единственное оптимальное решение:

(a) если

Г>ьм ЬЕ

то Р = {Рщ* } = 0 с выигрышем, равным 0;

(b) если

Г < 'М 'Е

Г < II,0щ0 — ',01*0 ,

то стратегия Р(X*) = {РЩ(X*)} и выигрыш равен и(Р(X*)), где

„ _ ¡0, если Н(0) < Р,

1 единственый корень уравнения Н(X) = Р, если Н(0) > Р.

5. Численное моделирование. Приведем два примера численного моделирования. В первом из них (рис. 1) демонстрируется, как меняются выигрыши пользователя в следующих различных случаях: 1) с полной информацией о состоянии каналов; 2) с информацией только о состоянии каналов передачи; 3) когда используется двухопционная стратегия. Будем считать, что передача осуществляется мгновенно по одному каналу, в котором имеется пять различных состояний, вероятности нахождения в которых равны л = [0.2; 0.2; 0.2; 0.2; 0.2]. Коэффициенты затухания будут равны соответственно Iм = [0.7; 0.8; 0.9; 1.0; 1.1] для главного канала

2

Выигрыш, нат

0.35

0.3

-7

••2 -3

0.25

0.2

0.15

0.1

0.05

0

О

0.2

0.4 0.6 0.8 1

1

Коэффициент стоимости, нат/дБ

Рис. 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 G [1,30]) выигрыши пользователя в таких различных случаях: 1) с полной информацией о состоянии каналов; 2) с информацией только о состоянии каналов передачи; 3) когда применяется двухопционная стратегия (считаем, что мощность сигнала будет изменяться с течением времени для каждого канала). Будем рассматривать процесс передачи сигнала по одному каналу, который может находиться в одном из пяти различных состояний. Вероятности нахождения в этих состояниях равны ¡1 = [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]

Выигрыш, нат 0.5 г

0.45 .

0.4

0.35

0.3

0.25 0.2

_I_I_I_I_I_I

5 10 15 20 25 30

Число временных слотов

Рис. 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.

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 г.