Например, Бобцов

МЕТОД ОЦЕНКИ ТОПОЛОГИИ БЕСПРОВОДНОЙ СЕТИ С ПРИМЕНЕНИЕМ АПРИОРНОЙ ИНФОРМАЦИИ О РАСПОЛОЖЕНИИ УСТРОЙСТВ

БЕСПРОВОДНЫЕ СЕТИ СВЯЗИ

УДК 004.75

Е. А. БАКИН, К. Н. СМИРНОВ
МЕТОД ОЦЕНКИ ТОПОЛОГИИ БЕСПРОВОДНОЙ СЕТИ С ПРИМЕНЕНИЕМ АПРИОРНОЙ ИНФОРМАЦИИ О РАСПОЛОЖЕНИИ УСТРОЙСТВ

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

Ключевые слова: сенсорная сеть, коэффициент передачи канала, максимум апостериорной плотности, RSSI.

Введение. В настоящее время задача контроля параметров объектов, распределенных на

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

контроль подразумевает измерение некоторого набора физических величин, характеризую-

щих состояние объекта, и передачу полученных данных на пункт сбора информации. В реше-

нии этой задачи широко используются так называемые сенсорные сети [1—4].

Сенсорная сеть состоит из множества датчиков, называемых сенсорами, и пункта сбора

информации, называемого базовой станцией (БС). Все устройства сенсорной сети связаны

между собой радиолиниями. Сенсоры предназначены для регистрации измеряемого парамет-

ра и передачи полученной информации на БС. Как правило, каждый сенсор состоит из датчи-

ка, вычислительного устройства и маломощного приемопередатчика [5]. Назначением БС яв-

ляется сбор информации с сенсоров и управление сетью. Для эффективного управления се-

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

кими сенсорами может быть установлена надежная связь [6].

Параметром, характеризующим надежность связи между двумя сенсорами а и b, может

являться коэффициент передачи канала ga,b . В этом случае топология сенсорной сети полно-

стью определяется матрицей коэффициентов передачи

⎡ g1,1 g1,2 … g1,N ⎤

G

=

⎢ ⎢ ⎢

g2,1

g2,2



g2,N

⎥ ⎥,



⎢ ⎢⎣

g

N

,1

gN ,2



g

N

,

N

⎥ ⎦⎥

(1)

где N — число сенсоров в сети.

Топология сенсорной сети, как правило, изменяется во времени. Таким образом, для под-

держания работоспособности сети необходима периодическая оценка текущей топологии.

Обычно с этой целью устройства сети обмениваются набором тестовых сообщений, по которым

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8

Метод оценки топологии беспроводной сети

29

оценивается качество связи между парами устройств [7]. Чем больше тестовых сообщений, тем точней результат оценки, однако тем выше накладные расходы на проведение данной процедуры. В настоящей работе предлагается алгоритм оценки топологии сети, использующий дополнительную информацию о статистической взаимосвязи между координатами устройств и позволяющий повысить точность оценки без увеличения числа тестовых сигналов.
Оценка коэффициентов передачи канала при помощи тестового сигнала. Для оценки коэффициентов передачи, как правило, используется следующая процедура, инициируемая базовой станцией [8]. Каждый сенсор сети по очереди передает в эфир тестовый сигнал с известной структурой, мощностью Pпрд и длительностью τ. Время начала и окончания выхода в эфир
каждого из сенсоров регламентировано и каждый из сенсоров обладает информацией о времени выхода в эфир всех остальных сенсоров сети. Как правило, приемный тракт устройств сенсорной сети включает в себя индикатор мощности входного сигнала — так называемый RSSI [9]. Работу идеализированного устройства RSSI можно описать следующим образом.
Зная время передачи сигнала τ и мощность передатчика Pпрд , можно определить энер-
гию излученного сигнала Eпрд = Pпрдτ . Энергия сигнала на входе приемника будет равна
Eпрм = ga,bEпрд . Тогда если тестовый сигнал является узкополосным, справедливо выражение
Sпрм ( jω) = ga,b Sпрд ( jω) e jω∆t , где Sпрд ( jω) — спектр переданного (излученного) сигнала,

Sпрм ( jω) — спектр принятого сигнала, ∆t — задержка на распространение.
Для максимизации отношения сигнал/шум (ОСШ) при приеме сигнала применяется согла-
сованный фильтр, комплексная частотная характеристика которого равна Kсф ( jω) = kS* ( jω) ,
где * — знак комплексного сопряжения, а k — коэффициент, зависящий от конструктивных осо-
бенностей фильтра, S ( jω) — спектральная функция сигнала, с которым согласован фильтр.

Спектральная функция сигнала на выходе согласованного фильтра будет равна
Sв.сф ( jω) = ga,b Sпрд ( jω) e jω∆tkSп*рд ( jω) = ga,b k Sпрд ( jω) 2 e jω∆t .
Далее для устранения неоднозначности начальной фазы принятого сигнала выделяется модуль его огибающий (например, при помощи квадратурного детектора). Тогда при ∆t t через интервал времени τ после начала приема на выходе квадратурного детектора будет наблюдаться

максимальное значение выходного сигнала оптимального фильтра: smax = ga,b kEпрд .
Так как одновременно с полезным сигналом на согласованный фильтр поступают собственные тепловые шумы приемника, окончательная формула для выходного сигнала в момент времени τ имеет вид sв.сф = smaxe jω∆t + n = ga,b kEпрдe jω∆t + n , где n — комплексная

гауссова случайная величина с нулевым математическим ожиданием и дисперсией Dn , зависящей от коэффициента шума приемника, коэффициента усиления приемного тракта и т. д.

Таким образом, измеряя уровень сигнала в моменты времени tm = t0 + mτ ( m = 1, N , t0 — время начала процедуры), каждый сенсор i может определить коэффициент передачи канала между собой и сенсором m через выражения (2), (3):

ξ

=

sв.сф (tm )
kPпрдτ

=

gi,m e jω∆t + η ,

(2)

gi,m ≈ ξ2 ,

(3)

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8

30 Е. А. Бакин, К. Н. Смирнов

где ξ — нормированный сигнал на выходе детектора, η — гауссова случайная величина с дис-

персией

D=

Dn k 2Eп2рд

.

Для описания предлагаемого алгоритма оценки коэффициента передачи приведем ис-

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

расширенная модель Окумура-Хата [10—12]:

gi, j

=

α diβ, j

,

(4)

где di, j — расстояние между сенсорами i и j, α и β — коэффициенты, характеризующие па-

раметры среды распространения сигнала.

Согласно принятой в работе модели, сенсоры сети случайным образом размещены на

площади S = a2 , так что их координаты являются независимыми случайными величинами (СВ) с равномерно распределенной на интервале [0, a] плотностью вероятности [13].

Оценка коэффициента передачи канала на основе максимума апостериорной плотности вероятности. Для повышения точности оценки коэффициента передачи канала воспользуемся методом максимума апостериорной плотности вероятности. В данном методе учитывается дополнительная информация о взаимном расположении сенсоров.
Поскольку коэффициент передачи канала оценивается по формуле (1), можно вычислить его априорную плотность вероятности. Для этого сначала найдем плотность вероятности (ПВ) расстояния между сенсорами. Расстояние между сенсорами составит

( ) ( )di, j =

xi − x j

2
+

yi − y j

2,

где xi , x j , yi , y j — координаты сенсоров на плоскости.

Найдем поэтапно ПВ расстояния: сначала — закон распределения разности координат, затем — квадрат этой разности; затем — распределение суммы квадратов и наконец — рас-

пределение квадратного корня получившейся случайной величины.

ПВ разности координат ∆x = xi − x j представляет собой известное распределение Симпсона:

f∆x

(

x)

=

⎧ ⎪ ⎪⎪ ⎨ ⎪ ⎪ ⎩⎪

a+x a2 a−x a2 0,

, ,

x ∈[−a, 0);
x ∈[0, a]; x ∉[−a, a].

Найдем распределение СВ ∆x2 . Так как ∆x распределена на интервале [−a, a] , а функ-

ция возведения в квадрат не является монотонной на нем, то необходимо разбить интервал на

участки монотонности [−a, 0) и [0, a] и вычислить ПВ ∆x2 на одном из отрезков. Результи-

рующая ПВ ∆x2 будет равна удвоенному значению ПВ, вычисленной для одного из отрезков

(поскольку y = x2 симметрична относительно оси ординат):

f∆x2

(

x)

=



⎪ ⎨

a





1

− x 0,

1 a2

,

x



⎣⎡0,

a2

⎤ ⎦

;

x



⎡⎣0,

a2

⎤ ⎦

.

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8

Метод оценки топологии беспроводной сети

31

Приведенные выражения справедливы как для координаты x, так и для y. Найдем плотность вероятности суммы ∆x2 + ∆y2 . Поскольку ∆x2 и ∆y2 независимы, то
для нахождения закона распределения их суммы необходимо провести композицию законов

распределения: f∑ ( z) = ∫ f∆x2 ( x) f∆y2 ( z − x) dx . −∞ Плотность вероятности суммы ∆x2 + ∆y2 будет равна

⎧ ⎪ ⎪

z a4



4z a3

+

π a2

,

f∑

(

z

)

=

⎪⎪ ⎨ ⎪ ⎪

2

arcsin

⎛ ⎜⎝⎜

2a2 z
a2



z

⎞ ⎟⎟⎠



3

+

4

z − a2 a3



z − a2 a4

,

⎪ ⎪⎩

0,

z ∈ ⎣⎡0, a2 ⎦⎤ ;
(z ∈ a2, 2a2 ⎦⎤ ;
z ∉ ⎡⎣0, 2a2 ⎤⎦.

И наконец, найдем плотность вероятности расстояния между сенсорами:

⎧ ⎪ ⎪

⎛ ⎜⎜⎝

x2 a4



4x a3

+

π a2

⎞ ⎟⎟⎠

2x,

fd

(

x)

=

⎪⎪⎪⎨⎜⎛⎜ ⎪⎜ ⎪⎜

2

arcsin

⎛ ⎜⎜⎝

2a2 − x2
a2

x2

⎞ ⎟⎟⎠



3

+

4



x2 − a2 a3



x2 − a2 a4



⎟ ⎟

2d

,



⎪⎪⎜⎝ ⎟⎠

⎪ ⎩

0,

x ∈[0, a];
(x ∈ a, 2a⎦⎤ ;
x ∉ ⎡⎣0, 2a⎤⎦.

Теперь, зная значение ПВ для d и выражение, связывающее его с коэффициентом передачи канала (1), можно найти априорную плотность вероятности для коэффициента передачи g:

⎧ ⎪ ⎪⎪2γ ⎪

⎛ ⎜ ⎜ ⎜ ⎜

2

arcsin

⎛ ⎜⎜⎝

2a2
γ a2


2

γ

2

⎞ ⎟⎟⎠



3

+

4



γ2 − a2 a3



γ2 − a2 a4

⎟ ⎟ ⎟ ⎟

ψ′( g )

,



f

(

g

)

=

⎪⎪ ⎨





⎝⎜

⎛ ⎜⎜⎝

2γ3 a4



8γ2 a3

+

2πγ a2

⎞ ⎟⎟⎠

ψ′( g )

,

⎠⎟







⎪ ⎪⎩ 0,

⎡⎤

( )g



⎢ ⎢

⎣⎢

α 2a

β

,

α aβ

⎥ ⎥

;

⎦⎥

g



⎛ ⎝⎜

α aβ

,



⎞ ⎟⎠

;

⎛⎞

( )g



⎜ ⎜

−∞,

⎜⎝

α 2a

β

⎟ ⎟

,

⎟⎠

где

ψ′( g )

=−βα β

−(1+β) gβ

— производная по g от функции, обратной (4), а

γ

=

β

α g

.

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8

32 Е. А. Бакин, К. Н. Смирнов

Используя формулу Бейеса, можно определить апостериорную плотность вероятности

для оцениваемого параметра g как

f

(g

ξ) =

f

(g) f (ξ
f (ξ)

g),

где f (g) — априорная плотность вероятности параметра g; f (ξ g ) — условная плотность

вероятности ξ.
Значение f (ξ g ) подчиняется гауссову закону:

( )f (ξ g) =

1 2πD

⎧ exp ⎨⎪−
⎪⎩

ξ− g 2D

2⎫

⎪ ⎬

.

⎭⎪

Искомая оценка коэффициента передачи канала равна абсциссе максимума апостериорной плотности вероятности (рис. 1):

{ }gˆ = {arg max f ( g ξ)} = arg max ⎣⎡ f ( g ) f (ξ g )⎤⎦ .

(5)

В силу одномодовости апостериорной плотности вероятности ее максимум может быть найден численно.

f(g|ξ)×1018

10 8

6 4 2

0

0,2 0,4 0,6

0,8 g×10–9

Рис. 1

Анализ эффективности предложенного алгоритма. Сравнение приведенных методов

производилось путем имитационного моделирования с использованием работ [14, 15]. При

моделировании были использованы следующие типовые значения параметров: a = 1000 м,

Pпрд = 6 мВт, τ = 1 мс, α = 9, 9 ⋅10−5 (соответствует работе с изотропными антеннами на час-

тоте 2,4 ГГц), β = 3 [16].

Были получены зависимости (1 — стандартный, 2 — предлагаемый алгоритм): относи-

тельной ошибки оценки параметра от длины тестового сигнала (рис. 2), относительной ошибки

оцениваемого параметра от расстояния между сенсорами (рис. 3), зависимость дисперсии полу-

ченной оценки (3) от дисперсии шума на выходе согласованного фильтра (2) (рис. 4).

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8

Метод оценки топологии беспроводной сети
е

2,5

2

1,5 1

0,5 2
0

1 1

е 1
0,8

0,6

2 Рис. 2

3

4 τ, с ×10–3

1

0,4 2
0,2

0 600
Dg, ×10–16 50 3,5 3 2,5 2 1,5 1 0,5

800 Рис. 3

1000

d,

1

2

0

246

8

Рис. 4

1200 d, м 10 Dn, ×10–9

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8

33

34 Е. А. Бакин, К. Н. Смирнов
Заключение. В настоящей работе представлены два способа оценки коэффициента передачи канала g — стандартный по сигналу RSSI и метод оценки по максимуму апостериорной плотности вероятности. Теоретически получены априорные и апостериорные плотности вероятности оцениваемого параметра. Серия вычислительных экспериментов показала, что предложенный метод оценки дает меньшую дисперсию и позволяет существенно снизить относительную ошибку оценки коэффициента передачи канала.

СПИСОК ЛИТЕРАТУРЫ

1. Минеев А. Н., Минеев В. Н., Архипов Д. А., Агеев С. В. Беспроводные сенсорные системы обнаружения пожаров на промышленных предприятиях России // Интернет-журнал „Технологии техносферной безопасности“. 2012. Февраль.

2. Ларцов С. В., Столяров В. Е., Карюк М. В. Применение беспроводной оперативной системы сбора информации на территориально распределенных объектах // Перспективные технологии в средствах передачи информации. 2009. С. 89—93.

3. Вишневский В., Гайкович Г. Беспроводные сенсорные сети в системах промышленной автоматики // Связь и телекоммуникации. 2008. № 1. С. 106—110.

4. Шепета А. П., Евсеев Г. С., Бакин Е. А. Нижняя граница длительности периода сбора информации в сенсорной сети // ИУС. 2011. № 6(55). С. 64—67.

5. Karl H., Willi A. Protocols and architectures for wireless sensor networks. Wiley-Interscience, 2005. 526 р.

6. Labrador M. A., Wightman P. M. Topology Control in Wireless Sensor Networks. Springer, 2009. 412 р.

7. Andrews J. G., Ghosh A., Muhamed R. Fundamentals of WiMAX: Understanding Broadband Wireless Networking. Prentice Hall PTR, 2007. 530 р.

8. Santi P. Topology control in wireless ad hoc and sensor networks. Wiley-Interscience, 2005. 280 р.

9. CC1111F32: True System-on-Chip with Low Power RF Transceiver and 8051 MCU. 110 р.

10. Bose A., Foh C. H. A Practical Path Loss Model For Indoor WiFi Positioning Enhancement // Proc. of ICICS'07. 2007.

11. Somarriba O. Evaluation of heuristic algorithms for scheduling, routing and power allocation in traffic sensitive spatial TDMA wireless ad hoc networks // 6th Intern. ICST Symp. on Modeling and Optimization. 2008. Р. 566—571.

12. Christophides F., Friderikos V. Iterative hybrid graph and interference aware scheduling algorithm for STDMA networks // Electronic letters. 2008. Vol. 44. Р. 558—559.

13. Onat F. A., Stojmenovic I., Yanikomeroglu H. Generating grandom graphs for simulation of wireless adhoc, actuator, sensor, and wireless networks // Pervasive and Mobile Computing. 2008. Vol. 4. P. 597—615.

14. Levenberg K. A method for the solution of certain problems in least squares // Quart. Appl. Math. 1944. Vol. 2. P. 164—168.

15. Marquardt D. An algorithm for least — squares estimation of nonlinear parameters // SIAM J. Appl. Math. 1963. Vol. 11. P. 431—441.

16. Lee W. C. Y. Mobile cellular telecommunications, Analog and Digital systems. NY: McGraw-Hill, 1995. 664 р.

Сведения об авторах

Евгений Александрович Бакин

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

ского приборостроения, кафедра моделирования вычислительных и

электронных систем; ассистент; E-mail: jenyb@vu.spb.ru

Константин Николаевич Смирнов — аспирант; Санкт-Петербургский государственный университет аэро-

космического приборостроения, кафедра моделирования вычисли-

тельных и электронных систем; E-mail: kossmir@gmail.com

Рекомендована кафедрой № 51 безопасности информационных систем

Поступила в редакцию 01.02.13 г.

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8