Clustering method of chaotic particle swarm optimization sensor networks based on multi-factor conflict.pdf Введение Прогресс микроэлектромеханических систем (MEMS), беспроводной связи и технологий микроэлектроники позволяет разрабатывать маломощные, многофункциональные микродатчики, имеющие небольшие размеры и выполняющие функции сенсорики, обработки данных и коммуникационных компонентов. Можно полагать, что в ближайшие годы появятся SOC-чипы, которые объединяют беспроводную связь, микропроцессор и чувствительные приводы MEMS на одном чипе. Многие датчики (или исполнительные механизмы), обладающие коммуникационными и вычислительными возможностями, соединяются в беспроводном режиме, взаимодействуют друг с другом, совместно выполняют прикладные задачи и становятся сенсорными сетями [1]. Протокол кластеризации делит узлы сети на несколько кластеров в соответствии с определенными правилами, каждый из которых включает головные узлы и узлы-члены [2]. Узлы-члены отвечают за обнаружение, сбор целевой информации и ее отправку головным узлам, которые получают информацию, обрабатывают и передают базовым станциям. Только при точном выборе головных и входящих узлов кластера жизненный цикл сети может быть максимизирован. В настоящее время предложены многие виды алгоритмов кластеризации. В [3] используется оптимизация муравьиной колонии для завершения кластеризации беспроводных сенсорных сетей, но этот алгоритм не подходит для крупномасштабных сетей. В [4] используется оптимизация роя частиц-PSO для кластеризации и рассматривается оптимальное количество кластеров, но проблема конфликта факторов с несколькими узлами не учитывается. На оптимизацию выбора головного узла и продление жизненного цикла сети направлена работа [5], она решает проблему многофакторного конфликта в процессе выбора, но не учитывает проблему энергетического баланса, влияющую на срок службы сети. Поэтому в данной работе исследуется метод кластеризации при оптимизации роя хаотических частиц для сенсорных сетей. Метод направлен на решение многофакторного конфликта узлов, оптимизации выбора головного узла кластера и продление жизненного цикла сети. Стандартное отклонение остаточной энергии узлов в рабочей зоне используется для измерения индекса энергетического баланса сети [6]. Также рассматриваются проблемы энергопотребления и энергетического баланса, которые препятствуют кластеризации сенсорных сетей и влияют на срок службы сети. Модель метода кластеризации в сенсорных сетях Сетевая модель Рис. 1. Топология сети Принята топология сети иерархической кластеризации, как показано на рис. 1. Сеть состоит из узлов-членов кластера, головных и узлов-приемников. Алгоритм делит узлы на несколько кластеров, каждый из которых содержит один головной узел и несколько узлов-членов, которые передают собранные данные головным узлам. Эти узлы помимо сбора данных получают информацию от других узлов-членов. Отправленные данные сливаются и результат обработки отправляется в узел приемника, который имеет достаточно энергии, возможности обработки, хранения и сильные связи. Он играет роль соединения беспроводного датчика и внешней сети [7]. К модели сетевого узла приемника предъявляются следующие требования: A. Узлы принадлежат к изоморфным узлам с одинаковой начальной энергией, способностью обработки информации, радиусом обнаружения и радиусом связи, причем радиус связи намного больше радиуса обнаружения. Б. Мощность передачи можно регулировать в пределах допустимого диапазона. В. Местоположение узла фиксировано, известна его собственная информация о местоположении, которая может быть получена с помощью GPS-оборудования или алгоритма самонастройки узла. В данном случае проблема самолокализации узлов WSN не обсуждается. Г. Узел приемника только один, его местоположение фиксировано. Расстояние между каждым узлом и узлом приемника известно, оно определяется из обмена информацией между ними. Из-за различий в потреблении энергии, скорости, местоположении, жизненном цикле, остаточной энергии, мощности передачи и др. факторов многофакторный конфликт между узлами будет препятствовать кластеризации сенсорных сетей, поэтому для плавной группировки необходимо решить проблему выбора головного узла кластера. Модель энергопотребления Энергопотребление узлов связано, в основном, с отправкой, приемом и обработкой данных. По сравнению с этим потребление энергии в состоянии прослушивания и сна незначительно. Так как потребление энергии является одним из факторов конфликта, необходимо рассмотреть его снижение при передаче и обработке данных. Для сравнения с методом Лича используем ту же модель беспроводной связи [8]. Энергопотребление участка при передаче данных узлами сети составляет (1) Необходимая узлу энергия для получения данных (2) энергия для обработки данных (3) где энергопотребление: - передающей и приемной цепей; - обработки данных; и - усилителей мощности в моделях свободного пространства и многолучевого затухания соответственно, что является порогом дальности передачи и определяет режим затухания [9]. Оптимизация роя хаотических частиц с адаптивным инерционным весом Алгоритм глобальной оптимизации роя частиц PSO основан на скорости поиска популяции. Он случайным образом инициализирует группу частиц. Каждая частица является возможным решением задачи оптимизации, а значение пригодности определяется целевой функцией. Каждая частица динамически регулирует скорость полета в пространстве поиска в соответствии со своим собственным опытом и опытом группы и находит оптимальное решение путем итерации. Выражение обновления скорости и положения частиц выглядит следующим образом: ; (4) (5) где - текущее положение частицы; - ее текущая скорость; - оптимальное положение частицы в текущий момент времени; - оптимальное положение популяции в текущий момент времени; и - распределенные в интервале [0,1] случайные числа; и - константы ускорения (обычно 2); - инерционный вес, используемый для балансировки глобальной и текущей способности поиска частиц (меньший имеет лучшую локальную способность поиска, что может эффективно повысить точность решения, а больший имеет лучшую глобальную способность поиска и может избежать ограничения локальным оптимумом [10]). В данной работе рассматривается использование адаптивного инерционного веса. Адаптивный инерционный вес Инерционный вес является одним из наиболее важных параметров в алгоритме PSO. Он, в основном, контролирует влияние исторического момента на текущее состояние, может сбалансировать способность глобального и локального поиска, регулируя инерционный вес. В большинстве улучшенных алгоритмов PSO используется метод линейного убывания. На начальном этапе берется большое значение, которое выгодно для глобального поиска, но сопутствующие затраты алгоритма слишком велики, а эффективность поиска низкая. Этот метод не подходит для беспроводных сенсорных сетей с высокими требованиями к энергии. На более позднем этапе принимается меньшее значение инерционного веса. Глобальное оптимальное решение не может быть найдено точно из-за попадания в локальный оптимум. Таким образом, в данном случае функция пригодности строится для определения значения инерционного веса через функцию пригодности в соответствии с текущим адаптивным значением частицы и соотношением между адаптивным значением предыдущего момента [11] с учетом энергетического баланса сети. В процессе кластеризации отслеживание потребления энергии концентрируется на головном узле и узлах в пределах диапазона обнаружения цели (т.е. рабочей области) в последний момент. Поэтому в данном случае используется стандартное отклонение остаточной энергии узлов в рабочей зоне для измерения степени энергетического баланса сети, а срок ее службы продлевается за счет обеспечения энергобаланса. Во-первых, ближайший к цели узел выбирается в качестве начального головного узла кластера и кластера-кандидата , , - головной узел кластера , является набором узлов-членов кластера . В рабочей области потребление энергии узлом происходит от головного узла кластера , отправляющего значение оценки целевого состояния и дисперсию следующему головному узлу кластера . Узлы-члены распознают цель и отправляют измеренное значение в головной узел кластера . Руководитель кластера определяет цель и получает отправленное значение оценки состояния цели и отклонение . В то же время он получает измеренное значение, отправленное . Согласно модели энергопотребления датчика, энергопотребления , и соответствено равны: ; (6) ; (7) . (8) В приведенном выражении , и - постоянные [12]; и сконфигурированы отправителем и -получателем; - энергия, потребляемая данными блока датчиков; и - отправленные биты данных; и - измеренные значения, полученные и соответственно; - функция расстояния между двумя точками, поэтому общая потребляемая энергия кластера . (9) Затем с помощью метода внутреннего поиска определяется оптимальный головной узел кластера и узел альянса в кластере-кандидате . Так как , то выражение можно записать в виде ; (10) . (11) Потребление энергии соответствующими узлами равно , и , тогда выражение для остаточной энергии каждого узла задачи обновляется как ; (12) ; (13) . (14) В результате формула стандартного отклонения остаточной энергии узла в рабочей области временного шага может быть выражена так: . (15) Здесь - функция стандартного отклонения. Вводится новый энергетический индекс, который выражается в виде , (16) где - взвешенный параметр для компромисса общего энергопотребления и энергетического баланса. Среднеквадратичная оценка ошибки состояния цели может быть выражена в форме , (17) где - след ковариационной матрицы оценки состояния цели, которая представляет точность отслеживания цели в кластеризации. Точность отслеживания, соответствующая кластеру-кандидату , может быть выражена следующим образом: . (18) В процессе отслеживания целей WSNs [13] основным критерием кластеризации является обеспечение хорошего энергетического баланса и высокой точности отслеживания, поэтому функцией пригодности оптимального механизма кластеризации на основе алгоритма BPSO является взвешивание и : (19) Здесь - весовой параметр; - коэффициент соответствия энергии, который делает индекс энергетического баланса таким же по порядку величины, как и точность отслеживания. Выражение (19) используется для получения текущей степени адаптации частиц, а связь между степенью адаптации и предыдущим моментом используется для определения инерционного веса. Формирование значения инерционного веса выглядит следующим образом: (20) ; (21) , (22) где t - номер текущей итерации; и - максимальный и минимальный инерционный вес соответственно. Согласно многим экспериментам, = 0.9 и = 0.4. Оптимизация роя хаотических частиц Из формул обновления положения и скорости частицы видно, что если текущее положение, текущее оптимальное значение и оптимальное значение популяции согласованы, то частица будет далеко от оптимального положения, поскольку коэффициент ускорения и инерции не равен нулю. В результате алгоритм не может сходиться. Если скорость будет очень близка к нулю, частица достигнет оптимального положения текущей популяции, т.е. разнообразие популяции будет потеряно, частицы перестанут двигаться [14]. Следовательно, они будут в застойном состоянии, что приведет к преждевременной зрелости. Если скорость частиц остается инициализированной на протяжении всего итерационного процесса, то «самопознание» и «социальное обучение» частиц потерпят неудачу, глобальный минимум не будет найден, и адаптивность алгоритма будет снижена. Чтобы избежать преждевременности и повысить адаптивность алгоритма, вводится хаос в оптимизацию роя частиц (PSO). Хаос - это форма случайного движения в нелинейных системах, которая широко наблюдается в природных и социальных явлениях и имеет три характеристики: случайность, эргодичность и регулярность. Идея хаоса добавлена в PSO для повышения скорости конвергенции и получения широкого спектра возможностей поиска. В [13] показано, что тентовое отображение имеет лучшую эргодическую однородность, чем логистическое отображение, поэтому тентовое отображение используется в качестве генератора хаотических возмущений: (23) Идея оптимизации хаотического роя частиц заключается в следующем: A. Положение и скорость частиц инициализируются хаотической последовательностью, которая не только сохраняет случайность инициализации оптимизации роя частиц [15], но также улучшает разнообразие популяции и эргодичность поиска. Б. При достижении заданного числа операций оптимальные положения отдельных представителей и групп оптимизируются хаосом, который сопоставляется с хаотической последовательностью, генерируемой итерацией уравнения. Затем хаотическая переменная последовательность возвращается в исходное пространство решений обратного отображения: . (24) Положение и скорость частиц в узле являются одним из факторов конфликта узлов, поэтому случайным образом инициализируется положение и скорость группы частиц в узле, строится функция пригодности в соответствии с текущим и предыдущим адаптивными значениями, определяется значение инерционного веса с помощью этой функции. Путем итерации получают все значения. В соответствии со значением инерционного веса и глобальным оптимальным значением локальное оптимальное значение может обновить положение и скорость частиц в узле и решить конфликт между этими факторами - скоростью и положением узла. Алгоритм кластеризации на основе AWCPSO Блок-схема алгоритма AWCPSO показана на рис. 2. Протокол кластеризации следует принципам: А. Классический метод выщелачивания не учитывает большую остаточную энергию головных узлов кластера. Если энергии выбранного головного узла кластера недостаточно, время обслуживания организации кластера будет сокращено, а задача не может быть выполнена. Рис. 2. Блок-схема алгоритма AWCPSO Б. Расстояние между головным узлом кластера и узлом приемника относительно мало. Головной узел выполняет предварительную обработку сообщаемой узлами-членами информации. Если головной узел находится слишком далеко от узла приемника [16], то передача сигнала будет потреблять много энергии и головной узел скоро умрет. В. Диапазон активации головного узла кластера должен быть соответствующим. Так называемая уместность означает, что размер кластера не может быть слишком большим, так как это приведет к слишком большим расстояниям между граничными и головным элементами. Кроме того, слишком большое количество узлов-членов и взаимодействие с информацией может привести к ненужным конфликтам данных. Размер кластера не может быть слишком маленьким. По мере уменьшения объема операций количество активных узлов становится недостаточным для выполнения задачи. Поэтому необходимо ограничить область действия кластера [17] принудительными средствами, чтобы обеспечить его локальность. Поэтому задается пригодность алгоритма оптимизации роя хаотических частиц разумно, чтобы удовлетворить принципу В, а затем устанавливается пороговый уровень принимаемого сигнала. Основываясь на приведенном анализе, рассматривается оставшаяся энергия узлов, расстояние между узлами и базовыми станциями и количество раз, когда узлы становятся головными узлами кластера в процессе выбора. Формула фитнеса выглядит следующим образом: ; (25) ; (26) ; (27) , (28) где α, β и γ являются влияющими факторами, которые используются для корректировки в соответствии с требованием α+β+γ = 1; - остаточная энергия узла в сети; - текущее значение остаточной энергии головного узла выбранного кластера; - коэффициент оценки энергии, представляющий отношение остаточной энергии головного узла выбранного кластера к общей остаточной энергии сети [18]; - расстояние между узлом и базовой станцией; - расстояние между головным узлом выбранного кластера и базовой станцией; - коэффициент оценки расстояния, который представляет собой отношение суммы расстояния между всеми узлами и базовой станцией сети к расстоянию между головным узлом выбранного кластера и базовой станцией; - общее количество раз, когда глава кластера был успешно избран в соответствии с текущим состоянием головным узлом выбранного кластера; является фактором вероятности. Чем больше остаточная энергия узлов, чем ближе к базовой станции и чем меньше раз они были раньше головными, тем больше вероятность, что они станут головными. Из-за многоуровневости и гетерогенности сети в ней имеется небольшое количество узлов с различной энергией [19]. Агрегирующие узлы могут напрямую выбирать головные узлы кластеров в соответствии с алгоритмом AWCPSO. Согласно [20], оптимальное количество головных узлов кластеров K определяется как , (29) где N - число выживших узлов; D - длина края области сети; l - расстояние от головного узла до базовой станции; , и - как описано выше. Рис. 3. Блок-схема кластера AWCPSO Этапы алгоритма выбора головного узла кластера на основе AWCPSO показаны на рис. 3. После определения головного узла кластера добавляются узлы связи, а сеть кластеризуется. Используется режим TDMA для передачи данных [21]. Моделирование метода и оценка производительности Для оценки эффективности предлагаемого метода кластеризации в качестве области моделирования взята сенсорная сетевая система энергетической компании в городе А, размер которой составляет 200×200 м. При тех же условиях проводится имитационное сравнение предлагаемого метода с методом выщелачивания. Координаты региональных вершин - (0, 0), (200, 0), (200, 200), (0, 200). Количество случайно развернутых узлов составляет 200. Расположение узла приемника (100 300). Согласно (29), число головного узла кластера K = 6, = 2 Дж, = 50 нДж/бит, = = 10 ПДж/бит/м2, = 0.0013 ПДж/бит/м4, = 75 м, = 5 ПДж/бит, а данные равны 2000. Параметры CPSO задаются следующим образом: число исходных частиц 20, а эмпирические значения , , и максимальная скорость определяются многими экспериментами в заданном диапазоне [22, 23]. Их значения = 0.7298, = 1.4962, . Максимальное количество итераций устанавливается 1000, а хаотический поиск добавляется после 600 операций. При определении весовых факторов и следует учесть следующее. Во-первых, у узла должно быть достаточно энергии, что является предпосылкой его бесперебойной работы. Если энергии недостаточно, его не следует выбирать в качестве головного узла кластера, даже если он находится близко к узлу приемника. Во-вторых, если вес расстояния слишком велик, это неизбежно приведет к выбору головного узла кластера. Это не способствует выполнению таких задач, как отслеживание цели, поскольку оно сосредоточено в небольшой области близко к узлу приемника. На основе анализа экспериментальных данных и выбраны 0.7 и 0.3 соответственно. Для оценки производительности системы выбираются два показателя жизненного цикла сети и энергопотребления. Оценка жизненного цикла описывается тремя способами: первый узел умирает (FND), половина узлов умирает (HND) и умирает последний узел (LND). Потребление энергии выражается в терминах времени, затраченного с момента запуска сети до исчерпания энергии всеми узлами. Результаты моделирования получены в среднем по 10 запускам (табл. 1). Таблица 1 Сравнение жизненного цикла сети Метод кластеризации Время моделирования/цикл FND HND LND Метод выщелачивания (LEACH) 180 410 510 Предлагаемый метод 330 550 730 По сравнению с методом выщелачивания время FND, HND и LND предлагаемым методом увеличивается на 83.33, 34.14 и 43.14% соответственно. Очевидно, что жизненный цикл сети продлевается, особенно сильно задерживается время появления первого мертвого узла. Кластеризованная сенсорная сеть может сбалансировать энергопотребление, избежать быстрой гибели отдельных узлов, решить вызванную коротким жизненным циклом или несбалансированным энергопотреблением сети проблему конфликта, причем процесс кластеризации проходит гладко. Рис. 4. Сравнение энергопотребления Энергопотребление кластерных использующих метод выщелачивания сенсорных сетей полностью исчерпывается после 600 раундов работы (рис. 4), поэтому в течение 700 и 800 раундов энергопотребление не изменяется. Кластеризация сетей с использованием предлагаемого метода потребляет всю энергию после 800 циклов работы. Сети, использующие метод выщелачивания, в начале потребляют больше энергии, чем использующие предлагаемый метод сети. Общий уровень потребления энергии у использующих метод выщелачивания сетей выше, чем у использующих предлагаемый метод [24]. Это связано с существованием головных узлов в разное время. Энергопотребление кластерных сенсорных сетей намного ниже, чем у LEACH. Это указывает на то, что выбор головных узлов кластера более разумен. Видно, что энергопотребление сенсорных сетей кластеризации с использованием предлагаемого метода лучше, чем метод выщелачивания. Рис. 5. Стандартное отклонение остаточной энергии узлов в рабочей зоне при различных механизмах кластеризации Стандартное отклонение остаточной энергии узлов в рабочей области на каждом временном шаге при различных методах кластеризации показано на рис. 5. Для обеспечения энергетического баланса предлагаемый метод может выбирать узлы при планировании [25]. Метод выщелачивания планирует меньшее количество и более близкие узлы для снижения энергопотребления. Некоторые узлы, такие, как 6#, 12#, 29#, будут запланированы. Из-за многократного планирования стандартное отклонение остаточной энергии беспроводных кластеризованных методом выщелачивания сенсорных сетей выше, чем у предлагаемого метода. Результаты показывают, что по сравнению с методом LEACH кластеризованные предлагаемым методом сети могут обеспечить лучшее отслеживание нелинейных движущихся объектов. Остаточная энергия узлов при двух методах после завершения отслеживания цели приведена на рис. 6. В табл. 2 показано общее потребление энергии, общая остаточная энергия и срок службы всей сети при различных методах кластеризации. В кластеризованных беспроводных сенсорных сетях LEACH остаточной энергии узла 6# недостаточно для отслеживания. Результаты показывают, что предлагаемый метод кластеризации позволяет продлить срок службы беспроводных сенсорных сетей и снизить стандартное отклонение остаточной энергии узлов в рабочей зоне при условии обеспечения энергетического баланса. Он решает проблему конфликта узлов, вызванного высоким стандартным отклонением остаточной энергии и коротким сроком службы сети, и способствует эффекту кластеризации. Рис. 6. Сравнение остаточной энергии узлов при различных методах Таблица 2 Общее потребление энергии, общая остаточная энергия и срок службы всей сети Метод кластеризации Общее потребление энергии, Дж Общее потребление оставшейся энергии, Дж Срок службы сети, шаг по времени Метод выщелачивания (LEACH) 2.2534 21.5466 17 Предлагаемый метод 2.4123 21.3877 > 50 Обсуждение A. В процессе кластеризации выбираются два показателя жизненного цикла сети и энергопотребления для оценки эффективности. По сравнению с методом выщелачивания используемые в предлагаемом методе для оценки жизненного цикла три времени FND, HND и LND увеличиваются на 83.33, 34.14 и 43.14% соответственно, т.е. увеличивается жизненный цикл сети [26]. Наиболее очевидным является то, что жизненный цикл мертвого узла задерживается в момент его появления, показывая, что предлагаемый метод помогает сбалансировать потребление сети и позволяет избежать быстрой смерти отдельных узлов Энергопотребление использующих метод выщелачивания сетей полностью исчерпывается после 600 раундов работы, а энергопотребление использующих предлагаемый метод сетей исчерпывается в течение 800 раундов, т.е. уровень энергопотребления сети в процессе кластеризации низок. Можно сделать вывод, что предлагаемый метод позволяет не только продлить жизненный цикл сети, но и снизить энергопотребление, а также решить многофакторный конфликт узлов в процессе кластеризации сенсорных сетей. B. При решении проблемы конфликта узлов для сравнения берется стандартное отклонение остаточной энергии узлов в рабочей области на разных временных шагах при различных методах кластеризации. Учитывая энергетический баланс, использующие метод выщелачивания кластеризованные сенсорные сети будут выбирать для планирования узлы с большим расстоянием, но и с большей остаточной энергией [27]. Для снижения потребления энергии сети будут планировать узлы с коротким расстоянием, но с меньшим потреблением остаточной энергии. Стандартное отклонение остаточной энергии будет вызвано повторным планированием этих узлов. Поэтому при сопоставлении сравнивается общее потребление энергии, общая остаточная энергия и срок службы всей сети при различных методах кластеризации. Установлено, что энергопотребление отдельных узлов в беспроводных сенсорных сетях, кластеризованных методом выщелачивания, исчерпывается до завершения задачи отслеживания и не может быть завершено [28]. Задача непрерывного отслеживания значительно сокращает срок службы сети, но кластеризованные сенсорные сети редко планируют узлы с меньшей остаточной энергией, чтобы избежать гибели узлов. Поэтому срок службы таких сетей составляет более 50 временных шагов. Можно сделать вывод, что кластеризация сенсорной сети на основе предлагаемого метода может обеспечить лучшее отслеживание нелинейных движущихся объектов, а также решить проблему конфликта узлов при условии обеспечения баланса, продления срока службы и реализации кластеризации сенсорных сетей. Выводы Исследована оптимизация хаотического роя частиц (CPSO), основанная на многофакторном конфликте. Метод сочетает хаотическую теорию с адаптивной оптимизацией роя частиц с инерционным весом (AIWPSO) для оптимизации задачи кластеризации на основе разрешения многофакторного конфликта узлов. В процессе выбора головного узла кластера учитывается многофакторный конфликт между узлами. Всесторонне рассматриваются остаточная энергия, энергетические балансы, расстояние между узлами и базовыми станциями, а также вероятность запуска для головного узла. Учитывая множество факторов, в качестве головного узла выбирается оптимальный узел, который уравновешивает энергопотребление сети, позволяет избежать дисбаланса сетевой энергии, продлевает жизненный цикл, решает проблему многофакторного конфликта узлов и реализует кластеризацию сенсорных сетей.

Скачать электронную версию публикации