Анализ алгоритмов распространения тревожного сообщения с глобальным знанием в беспроводных сетях передачи данных с линейной топологией

кодирование и передача информации X

УДК 004.7

анализ алгоритмов распространения тревожного сообщения c глобальным знанием в беспроводных сетях передачи данных с линейной топологией

А. В. Винель,

канд. техн. наук, старший научный сотрудник Санкт-Петербургский институт информатики и автоматизации РАН А. Н. Дудин,

доктор физ.-мат. наук, профессор Белорусский государственный университет С. Д. Андреев,

канд. техн. наук, научный сотрудник

Санкт-Петербургский институт информатики и автоматизации РАН А. М. Тюрликов,

канд. техн. наук, доцент

Санкт-Петербургский государственный университет аэрокосмического приборостроения

Рассматриваются алгоритмы распространения тревожного сообщения от некоторого узла-инициатора ко всем узлам сети передачи данных, расположенных в некоторой географической области. Разрабатываются аналитические методы расчета вероятностно-временных характеристик таких алгоритмов для случая линейной топологии сети и фиксированной вероятности успеха одношаговой передачи. Обсуждается применимость полученных результатов к исследованию спонтанных автомобильных сетей.

Ключевые слова — спонтанные автомобильные сети, активная дорожная безопасность, многошаговая передача, распространение тревожного сообщения, ретрансляция.

Введение

Интеллектуальные транспортные системы (ИТС) будущего призваны решить широкий спектр задач, среди которых одной из основных является обеспечение безопасности дорожного движения. В настоящее время Институт инженеров по электротехнике и электронике (Institute of Electrical and Electronics Engineers — IEEE) и Европейский институт по стандартизации в области телекоммуникаций (European Telecommunications Standards Institute — ETSI) осуществляют стандартизацию в области ИТС в Северной Америке и Европе соответственно. Согласно предлагаемым ими концепциям, для успешного функционирования приложений безопасности используемая телекоммуникационная технология связи между автомобилями должна обеспечивать два основных режима работы [1, 2]. Первый ре-

жим состоит в периодической широковещательной одношаговой рассылке каждым транспортным средством сообщений-маячков, содержащих информацию, в частности, о его координатах и скорости. Это необходимо для того, чтобы все участники движения постоянно имели актуальную информацию о происходящем в непосредственной близости с ними. Второй режим, который и рассматривается нами в данной статье, состоит в экстренной многошаговой рассылке информации о критичном событии (например, срабатывании подушек безопасности при столкновении) тем транспортным средствам, которые находятся в опасной зоне (например, приближаются к месту аварии). При реализации второго режима первый используется как его составная часть, т. е. экстренное распространение тревожного сообщения осуществляется серией специальным образом организованных широковещательных

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

В литературе к настоящему моменту предложено большое число алгоритмов распространения критичной информации в заданной географической области. Наиболее широкую известность как в академической среде, так и среди специалистов автомобильной промышленности получило решение Торрент-Морено и Хартенштай-на «Распространение тревожного сообщения для автомобильных сред» (Emergency Message Dissemination for Vehicular Environments — EMDV) [3]. В EMDV доступ к каналу узлами-ретрансляторами осуществляется на конкурентной основе, а время задержки их выхода в канал обратно пропорционально расстоянию от узла-инициатора. Актуальный обзор других алгоритмов распространения тревожного сообщения содержится в работе Филали [4].

Из работ [3, 4] можно сделать следующие выводы. Во-первых, в подавляющем большинстве случаев предлагаемые алгоритмы исследуются их авторами посредством имитационного моделирования. Во-вторых, поскольку различными исследователями используются разные среды моделирования, допущения имитационной модели, множества входных параметров, то сравнительный анализ предлагаемых алгоритмов, а также исследование их свойств сильно затруднены. Именно поэтому важно провести анализ различных подходов к решению задачи распространения тревожных сообщений в рамках некоторой базовой (пусть и упрощенной) модели системы. Нам представляется, что в качестве такой модели может выступить модель Реста и Санти [5], которая основана на допущениях о линейной топологии сети, равном расстоянии между ее узлами и постоянной вероятности успеха одношаговой передачи. В работе [5] рассмотрены три алгоритма распространения критичной информации и приведены аналитические методы для расчета их вероятностно-временных характеристик. Обратим внимание, что вопрос связности сети в такой системе не рассматривается, так как считается, что радиус передачи всегда превосходит расстояние между узлами. Аналитические методы анализа распространения критичной информации в контексте проблемы связности рассматриваются в работе [6].

Несмотря на свою простоту модель Реста и Санти [5] отражает наиболее характерные особенности многошаговой передачи и позволяет исследовать свойства различных алгоритмов распространения тревожных сообщений. Далее мы

развиваем их идеи, предлагаем новые (более простые) методы расчета вероятностно-временных характеристик алгоритмов из работы [5]. Предварительные обсуждения предлагаемого подхода проводились на семинаре ON-MOVE-2009 [7].

Определения и модель системы

Сформулируем допущения используемой модели и введем необходимые определения.

Допущение 1 (линейная топология). Узлы сети расположены на прямой линии на равном расстоянии друг от друга, которое принято за единицу длины. Число узлов, которым необходимо доставить тревожное сообщение, равно п.

Для удобства будем считать, что узлы размещены на горизонтальной оси с инициатором передачи, расположенным в начале координат, и остальными узлами — в точках 1, 2, ..., п.

Данное допущение отражает случай движения потока автомобилей по автомагистрали с постоянной скоростью и отсутствием встречного движения. Кроме того, переход к одномерной линейной топологии адекватен реальности, если удвоенный радиус передачи превосходит ширину дороги.

Допущение 2 (радиус передачи). Все узлы имеют радиус передачи, равный г единиц, т. е. узел с номером I может передавать сообщение только узлам с номерами из диапазона [тах(0, I - г), тт(£ + г, п)].

Концепция радиуса передачи широко используется в литературе и вводится как для детерминированных, так и для случайных моделей распространения радиосигнала [3].

Допущение 3 (вероятность успешного приема). При передаче (в широковещательном режиме) некоторым узлом I сети сообщения его с одинаковой вероятностью р получает каждый из узлов-получателей в радиусе передачи узла I при условии отсутствия интерференции на узле-получателе. Интерференция на некотором узле-получателе j возникает, если одновременно в радиусе его передачи передают два и более узла.

Это ключевое допущение введено в целях возможности аналитического описания системы. В реальной системе можно ожидать, что вероятность успешного приема падает по мере удаления от передатчика. В целях упрощения модели мы не рассматриваем так называемый радиус интерференции, влияние которого на передачу сообщения учитывается в работе [5], хотя наш подход применим и к такому более общему случаю.

Допущение 4 (синхронизация). Все узлы сети могут начинать передачу сообщения только синхронно в моменты г = 1, 2, ..., называемые шагами. В нулевой момент времени (на нулевом шаге) сообщение всегда передает узел-инициатор.

В реальной спонтанной автомобильной сети всегда предполагается, что у каждого узла имеется доступ к глобальной системе позиционирования и часам, что обеспечивает возможность практической реализации некоторого вида синхронизации.

Определение 1. Узел называется 0-узлом в момент времени г, если к этому моменту времени он не был проинформирован, т. е. не получил тревожного сообщения. Узел называется 1-узлом в момент времени г, если к этому моменту времени он уже получил тревожное сообщение. Таким образом, функционирование системы описывается последовательностью двоичных векторов длиной п: X = (х1, х2, ..., хп), где х1 = 0, если в момент времени г узел I является 0-узлом, и х1 = 1 — в противном случае. Заметим, что К0 = (1, 0, 0, ..., 0).

Иллюстрация допущений моделей и используемой терминологии выполнена на рис. 1.

Определение 2. Алгоритмом распространения тревожного сообщения (далее — алгоритмом) называется правило, согласно которому в каждый момент времени г = 1, 1 + h, 1 + 2h, ... из множества 1-узлов на основе вектора X выбираются подмножества узлов-ретрансляторов Rt, Rt + 1, ..., Rt + п _ 1, т. е. узлов, которые будут передавать сообщение в моменты времени г, г + 1, ..., г + h _ 1. Алгоритм заканчивает свою работу в тот момент, когда все п узлов будут проинформированы. Величину h будем называть количеством этапов алгоритма.

Несмотря на то что в реальности векторы X неизвестны узлам сети, введенное определение позволяет исследовать наилучшие алгоритмы, которые используют данную «глобальную» информацию.

Для каждого алгоритма А введем в рассмотрение вероятность GA(t, d) того, что узел, располагающийся на расстоянии d от инициатора, будет проинформирован на г-м шаге функционирования системы.

Согласно допущению 4, на первом шаге всегда передает узел-инициатор, т. е. для любого алго-ритмаА

GA(0, 0) = 1, GA(0, d > 0) = 0, GA(t > 0, 0) = 0, GA(1, 0 < d < г) = р, GA(1, d > г) = 0,

а дальнейшие (для г >1) значения функции О определяются правилами работы алгоритма A.

0 1 2 3 4

Инициатор Расстояние

1-узел 0-узел

Рис. 1. Иллюстрация к используемой модели

Средняя задержка информирования узла d при использовании алгоритма A, рассчитываемая как

ТО

DA (<*) =Е *°А (*• *)>

г=0

будет являться для нас основным показателем эффективности алгоритма.

Алгоритмы распространения тревожного сообщения

Определение 3. В некоторый момент времени г узел I называется внутренним, если существует 1-узел на позиции j, большей, чем I (другими словами, располагающийся правее данного). В противном случае узел I называется внешним.

С учетом определения 1 можно различить: внутренние 0-узлы, внешние 0-узлы, внутренние 1-узлы и внешний 1-узел. Последний является самым удаленным от узла-инициатора из уже проинформированных узлов (см. рис. 1).

Алгоритм 0 («оптимальный»). Заметим, что никакой алгоритм не может обеспечить более быстрое распространение тревожного сообщения, чем случайный процесс, который на каждом шаге:

а) переводит с вероятностями р каждый внутренний 0-узел в 1-узел;

б) переводит с вероятностями каждый внешний 0-узел на интервале [£ + 1, £ + г] в 1-узел, где £ — номер внешнего 1-узла.

Заметим, что обеспечение условий а) и б) одновременно возможно не для всех векторов Например, если на некотором шаге имеется

X =

и г = 3, то для выполнения условия б) должен передавать 5-й узел (внешний 1-узел), что не позволяет выполнить условие а), поскольку при передаче как 0-го узла, так и 2-го узла (внутренние 1-узлы) возникнет интерференция, которая не позволит осуществить прием либо на 3-м, либо на 3-м и 4-м узлах. Именно поэтому корректнее называть рассматриваемый подход не оптимальным алгоритмом, а случайным процессом, не уступающим по скорости распространения сообщения любому из возможных алгоритмов. Средняя задержка информирования, обеспечиваемая таким процессом, дает нижнюю границу задержки для всех возможных алгоритмов:

ТО

Do (6) = £ tGo (г, й).

г=0

Для данного случайного процесса можно выписать оценки для вероятностей God) (обозначенные g0(t, d)) для г > 2 (предполагается, что h = 1) [7]:

go(t,d) = (1 -p)go(t-1,di),di e(0,(t l)r]; go(t,d2) = p,d2 e((t 1)r,tr]; go(t, do) = 0, dQ > tr.

Отсюда видно, что

TO TO

Do(d) = ^ tGo (t, d) > do (d) = ^ tg0 (t, d), t=o t=o

поскольку при расчете g0(t, d) подразумевается, что узел tr всегда становится 1-узлом за t шагов, что не соответствует действительности (в реальности может потребоваться больше времени).

Вероятность G0(t, d) можно рассчитать следующим образом. При 1 < d < r, t > 1 имеем G0(t, d) = = (1 -p)t - 1p. Теперь, пусть d > r. Введем в рассмотрение вероятность A(), 0 < j < d - r - 1, t > 1 — вероятность того, что если оповещение стартует из узла j, то на t-м шаге впервые будет проинформирован узел с номером из множества d - r,..., d - 1 (до этого были оповещены только узлы с номерами, меньшими d - r).

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

Aj (t) = ((1 - p)r )t-1 (1 -- (1 -- p)2r-d+j+1) +

+ ((1-p)r )m Zj Aj+i(t-1-m) p(1-p)r~l;

m=0 l=1

d - 2r < j < d - r -1;

Aj W= X1 ((!-P)Г)m 2>/+i(t-1-m)p(1-Р)Г-,

m=0 l=1

0 < j < d - 2r -1.

В итоге получаем

Go(t,d) = Aq(m)(1-p)t-m-1 p.

m=1

Алгоритм 1 («GLOBAL» [5]). Алгоритм работает в два этапа: h = 2. На первом этапе в качестве узлов-ретрансляторов выбираются внешний 1-узел, а также (при просмотре компонент вектора Xt слева направо), возможно, какие-то из внутренних 1-узлов. Причем узлы выбираются таким образом, чтобы избежать интерференции. В конце первого этапа узлы помечаются как покрытые, если они находятся на расстоянии, не превосходящем r от какого-либо из узлов-ретрансляторов. На втором этапе слева направо просматриваются все не покрытые узлы и из их непрерывных последовательностей формируются множества. Затем из каждого множества выбирается в качестве узла ретранслятора самый

левый 1-узел или, если 1-узлов во множестве не оказалось, — ближайший 1-узел слева от множества. Более формально указанную процедуру можно записать следующим образом.

Пусть Щ — внешний 1-узел в момент времени г = 1, 3, 5... .

Этап 1.

1. Все узлы помечаются как не покрытые:

2. Я( — к;

3. i — к - 2г - 1;

Пока i > 0 делать

{ Пока Х(^) = 0 делать {/ — i - 1}:

Добавить в узел ; i — '! - 2г - 1;

}

4. Каждый узел из Ир а также узлы, находящиеся от них на расстоянии, не больше г, помечаются как покрытые.

Этап 2.

1. z — 1, иг — пустое множество, i = 0;

2. Пока i < к делать

{ Если i не покрыт, то

{Включить i в иг 1 — 1;

Пока узел i + \ не покрыт делать {Включить i + \ в иг.

1—1 + 1;

}

z — z + 1;

иг — пустое множество;

i—i+1;

}

в противном случае {—i + 1;

}

}

3. +1 — пустое множество;

Для каждой группы иг делать

{Если в иг существует хотя бы один 1-узел, то {добавить в + 1 самый левый из них} в противном случае

{добавить в + 1 ближайший к самому левому 0-узлу в иг 1-узел }

}

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

Утверждение 1. Для любого алгоритма A, на любом шаге г если Щ — внешний 1-узел, то на интервале [0, Щ] число подряд идущих 0-узлов (другими словами, подряд идущих нулевых компонент в векторе ^г) не превосходит г _ 1.

Теперь несложно доказать следующее утверждение.

Утверждение 2. Для алгоритма 1 на шаге г = 1, 3, 5. после выполнения этапа 2 мощность полученных множеств и,, не превосходит г _ 1.

Доказательство: Рассмотрим вектор X на некотором произвольном шаге г = 1, 3, 5, . ; пусть выполнен этап 1 алгоритма и пусть I и j ( < j) — номера некоторой произвольно выбранной пары

соседних узлов из Яг Тогда в множество иг (с соответствующим номером г) попадают все узлы с номерами из интервала [і + г + 1, j - г - 1]. Количество таких узлов х = j - і - 2г - 1.

Предположим, что х > г - 1 (рис. 2). Тогда х - г + 1 не покрытых узлов, расположенных справа от і + г + 1, должны быть 0-узлами, иначе бы они были выбраны вместо і в качестве ретрансляторов на этапе 1 алгоритма 1. То же самое касается г - 1 покрытых узлов справа от і. Таким образом, получили последовательность 0-узлов длиной х > г - 1, что противоречит утверждению 1.

Утверждение 3. Для алгоритма 1 на шаге і = 1,

3, 5... если в каком-то множестве иг нет 1-узлов, то слева от узлов этого множества всегда найдется 1-узел, который находится на расстоянии, не менее г от всех узлов иг.

Доказательство: Справедливость доказываемого утверждения следует непосредственно из утверждения 1.

Таким образом, из утверждений 2 и 3 следует, что за два шага алгоритм 1 обеспечивает как минимум те же самые характеристики, что и алгоритм 0 за один шаг, а именно:

а) переводит с вероятностями р каждый внутренний 0-узел в 1-узел (для некоторых узлов такая вероятность может оказаться больше, а именно: 1 - (1 - р)2, если узел получает сообщение и на этапе 1, и на этапе 2 алгоритма);

б) переводит с вероятностями каждый внешний 0-узел на интервале [£ + 1, £ + г] в 1-узел (на этапе 1), где £ — номер внешнего 1-узла в момент времени і = 1, 3, 5..

Таким образом, можно получить оценки для вероятностей G1(t, d) для алгоритма 1, используя

Литература

1. Festag A., Hess S. ETSI technical committee ITS: news from European standardization for intelligent transport systems (ITS) // IEEE Communications Magazine [Global communications newsletter]. June 2009. Vol. 47. N 6. P. 1-4.

2. Kosch T. et al. Communication architecture for cooperative systems in Europe // IEEE Communications Magazine [Automotive networking series]. May 2009. Vol. 47. N 5. P. 116-125.

3. Torrent-Moreno M., Mittag J., Santi P., Hartenstein H. Vehicle-to-Vehicle Communication: Fair Transmit Power Control for Safety-Critical Information // IEEE Transactions on Vehicular Technology. Sept. 2009. Vol. 58. N 7. P. 3684-3703.

4. Hrizi F., Filali F. On Congestion-Aware Broadcasting in V2X Networks // Proc. of ICUMT-2009 Conf. and

Покрытые х не покрытых Покрытые

узлы узлов узлы

1 О О О О О О О О |

-Е—он&~(><>то~о~о~о~с5)£• * * ♦ •3

" " ' -Iі—т-! j

vv

r 1 х r + 1 I r - 1 узлов О-узлов О-узлов

Расстояние

Рис. 2. Иллюстрация к доказательству утверждения 2

те же самые выражения, что и для алгоритма 0. Для четных г > 2 верно О1(г, d) = 0 для всех d (считаем, что эффект от передач этапов 1 и 2 проявляется только после этапа 2), а для нечетных г > 2 верно

ад d) = О0 (*-1

d

и D(d) = ^ tG3) есть верхняя граница сред-

f=0

ней задержки информирования, обеспечиваемая алгоритмом 1.

Заключение

Рассмотрена модель передачи тревожного сообщения в беспроводных сетях с линейной топологией. Получена нижняя граница средней задержки информирования узла в такой сети и верхняя граница средней задержки информирования при использовании алгоритма с глобальным знанием.

Работа выполнена при финансовой поддержке РФФИ по проектам № 10-08-01071-а (рук. А. В. Ви-нель) и № 08-08-00403-а (рук. М. Ю. Охтилев).

Workshop. (Nets4Cars-2009 workshop), St.-Peters-burg, Oct. 2009. P. 1-8.

5. Resta G., Santi P., Simon J. Analysis of Multi-Hop Emergency Message Propagation in Vehicular Ad Hoc Networks // Proc. of The ACM Intern. Symp. on Mobile Ad Hoc Networking and Computing (MobiHoc-2007), Montreal, Quebec, Canada, Sept. 2007. P. 140-149.

6. Fracchia R., Meo M. Analysis and design of warning delivery service in intervehicular networks // IEEE Transactions on Mobile Computing. July 2008. Vol. 7. N 7. P. 832-845.

7. Vinel A., Koucheryavy Y. On the delay lower bound for the emergency message dissemination in vehicular ad-hoc networks // Proc. of The 3rd IEEE LCN Workshop On User MObility and VEhicular Networks (ON-MOVE), Zurich, Switzerland, Oct. 2009. P. 652-654.