+7 (812) 670-9095
Обратная связьEnglish
Главная → Статьи → Алгоритмическое обеспечение → Реализация алгоритма локального голосования для оптимального планирования загрузки распределенных устройств беспроводной многоузловой сети.
Версия для печати

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

17 июля 2018

Мультиагентное управление, mesh-сети, рандомизированные алгоритмы — область интересов и компетенций «АстроСофт». Мы начинаем публиковать статьи Олега Николаевича Граничина, профессора математико-механического факультета СПбГУ, доктора физико-математических наук, посвященные актуальным вопросам в области мультиагентных технологий: оптимизации распределенного информационного обмена, стратегиям управления в мультиагентных сетях и др.

Представляем первую статью цикла.


Авторы:

Димитриос Вергадос (Dimitrios J. Vergados), Афинский национальный политехнический университет, Греция
Наталия Амелина, Санкт-Петербургский государственный университет, Россия
Юминг Джанг (Yuming Jiang), Норвежский университет естественных наук и технологии, Тронхейм, Норвегия
Катина Кралевска (Katina Kralevska), Норвежский университет естественных наук и технологии, Тронхейм, Норвегия
Олег Граничин, Санкт-Петербургский государственный университет, Россия


Источник: http://www.math.spbu.ru/user/gran/oleg_gr.html




Аннотация.

Для работы беспроводной многоузловой сети важна реализация планирования передачи данных эффективным и справедливым образом. В статье предлагается новый алгоритм планирования загрузки распределенных устройств под называнием Local Voting (локальное голосование). Его задача — распределение загрузки (определяется как отношение длины очереди к количеству выделенных временных интервалов) посредством перераспределения временных интервалов, основанного на локальном обмене информацией. Необходимость алгоритма обуславливается тем, что самое короткое время доставки или задержка достигаются при равномерной загрузке всех устройств сети. Кроме того, будет доказано, что благодаря алгоритму локального голосования работа сети асимптотически сводится к оптимальному планированию. Более того, благодаря широкому спектру практических моделей эффективность алгоритма локального голосования дополнительно исследуется в сравнении с несколькими типичными алгоритмами планирования из литературы. Результаты моделирования показывают, что предлагаемый алгоритм обеспечивает лучшую производительность, чем другие распределенные алгоритмы с точки зрения средней задержки, максимальной задержки и справедливости распределения ресурсов. Несмотря на то, что предлагаемый алгоритм является распределенным, уровень его производительности очень близок к централизованному алгоритму, считающемуся оптимальным.


I. ВВЕДЕНИЕ

Беспроводные многоузловые сети являются парадигмой беспроводной связи, которая успешно используется в различных сетях, включая ad-hoc (одноранговые) сети [1], беспроводные сенсорные сети [2] и mesh-сети [3]. В таких сетях беспроводные устройства могут взаимодействовать друг с другом в режиме одноранговой сети и формировать сеть, где промежуточные беспроводные узлы могут выступать в роли маршрутизаторов и пересылать трафик другим узлам в сети [4].

Благодаря многочисленным практическим преимуществам и широкому применению, было проведено множество исследований на предмет производительности беспроводных многоузловых сетей. Например, возможность подключения к многоузловой сети изучалась в различных моделях каналов связи в [4], [5]. В [6] - [9] предметом аналитического исследования стала пропускная способность. В [10], [11] изучены характеристики устойчивости методов планирования при максимальной пропускной способности в многоузловых сетях. В [12] был предложен централизованный алгоритм планирования, который фокусируется на справедливости распределения ресурсов. В [13] авторы сосредоточились на задаче совместного планирования и маршрутизации при обеспечении сбалансированности нагрузки в многоканальных и многоузловых беспроводных mesh-сетях. Они также разработали межуровневый алгоритм с учетом увеличения пропускной способности при балансировке нагрузки. Алгоритмы совместного управления мощностью, планирования и маршрутизации были введены в [14], [15]. В [16] сформулирована проблема балансировки нагрузки в плотной беспроводной многоскачковой сети, где авторы представили общую структуру для анализа нагрузки трафика, возникающей в результате заданного набора путей и запроса на трафик.

Некоторые более поздние работы включают [17] - [25]. В [17] авторы рассматривают планирование множественного доступа с временным разделением (англ. Time Division Multiple Access, TDMA) для многоузловой сети. В [18] предлагается генетический алгоритм поиска свободных от конфликтов сетей (англ. Genetic Algorithm for finding Collision Free Set, GACFS), который является коэволюционным генетическим алгоритмом, решающим задачу планирования широковещательной рассылки (англ. Broadcast Scheduling Problem, BSP) для оптимизации алгоритма назначения временных интервалов в mesh-сетях WiMAX. Это централизованный подход, и он не учитывает запрос на трафик или загрузку сети. Другое решение для планирования работы mesh-сетей на основе меметического алгоритма, не учитывающего запрос на трафик, представлено в [21]. Улучшенный меметический алгоритм применяется для планирования энергоэффективных датчиков в [26]. Источник [20] исследует задачу планирования мини-интервалов в беспроводных mesh-сетях на основе TDMA и предлагает децентрализованный алгоритм для назначения мини-интервалов узлам в соответствии с запросами на трафик. Авторы [19] предлагают схему планирования для многоадресной связи, где бесконфликтный график создается динамически на основе адресатов каждой передачи. В [22] представлена прозрачная модель вероятностной топологии для многоадресных и широковещательных передач в мобильных ad-hoc сетях. Новизна схемы заключается в том, что вместо того, чтобы гарантировать, что для каждого узла назначается по меньшей мере один бесконфликтный временной интервал, она просто пытается довести вероятность успешной передачи выше порогового значения. В [27] авторы представили повышение производительности при использовании широковещательных запросов. Другой алгоритм прозрачного планирования топологии представлен в [24]. Он не зависит от трафика, а достигнутая пропускная способность ниже оптимальной, главным образом, из-за необходимости в гарантированном интервале для каждого узла. [23] предлагает схему распределенного планирования для беспроводных сенсорных сетей (WSN). Наконец, NP-трудность задачи минимальной задержки в распределенном планировании доказана в [25] в рамках модели SINR (Signal-to-Interference-plus-Noise Ratio, отношение уровня сигнала к уровню шума). В [28] представлено два распределенных детерминированных алгоритма для осуществления широковещательных запросов на основе модели SINR.

Эффективная балансировка загрузки трафика и доступ к каналам необходимы для использования плотного и учащающегося гетерогенного развертывания беспроводной инфраструктуры 5G [29]. При доступе к каналам в сетях 5G возникают проблемы, свойственные нынешним сотовым сетям [30], например, справедливость распределения ресурсов, адаптивный контроль скорости, резервирование ресурсов, поддержка трафика в реальном времени, масштабируемость, пропускная способность и время задержки. К примеру, возможность распределения частот и временных интервалов позволяет использовать более адаптивные и сложные методы управления помехами нескольких доменов [31], [32]. В [32] TDMA используется для смягчения взаимных помех с точки зрения временной области в сверхплотных сетях. Моделирование и оптимизация балансировки загрузки играют решающую роль в распределении ресурсов в сотовых сетях следующего поколения [33].

В этой статье мы остановимся на проблеме планирования работы узлов в беспроводных многоузловых сетях. При планировании работы узлов каждая возможность передачи назначается множеству узлов таким образом, что гарантирует отсутствие помех между любыми передающими узлами. В частности, при планировании двум узлам может быть назначен один и тот же временной интервал (и одновременно передача), если у них нет общих соседей. Вводим алгоритм локального голосования. Идея алгоритма возникла вследствие наблюдения, что общее время доставки в сети может быть сведено к минимуму, если отношение длины очереди к количеству выделенных временных интервалов распределено по всей сети. Назовём это отношение загрузкой каждого узла. Предлагаемый алгоритм позволяет соседним узлам обмениваться временными интервалами таким образом, чтобы в итоге распределить загрузку устройств сети. Количество интервалов, которые обмениваются, определяется соотношением между загрузкой каждого узла и его соседями с учетом ограничений, согласно которым определенные интервалы обмена не возможны из-за конфликта с другими узлами. Предварительные результаты были представлены в [34]. В данной статье представлен новый алгоритм и анализ его эффективности, а также новые результаты моделирования. Результаты имитационного моделирования сравнительного исследования алгоритма локального голосования и других алгоритмов показывают, что локальное голосование достигает кратчайшего сквозного времени доставки и максимальной справедливости по сравнению с другими распределенными алгоритмами в разных по плотности сетях. Мы также демонстрируем, что его производительность очень близка к централизованному алгоритму. Представленный алгоритм является модификацией протокола локального голосования с неубывающим до нуля размером шага, который был предложен в [35]. Он относится к более общему классу децентрализованных алгоритмов стохастической аппроксимации, которые были изучены в [36], [37], с убывающим до нуля размером шага.

Однако изменение параметров трафика приводит к нестабильным настройкам оптимизации. Для подобных случаев полезен алгоритм типа стохастической аппроксимации с константой (или неубывающим до нуля размером шагом) [38], [39].

Структура статьи: в разделе II подробно описывается модель сети. В разделе III представлен предлагаемый алгоритм локального голосования, а в разделе III-B представлен анализ эффективности алгоритма с точки зрения достижения консенсуса. Результаты моделирования в разделе IV сравнивают эффективность предлагаемого алгоритма с другими алгоритмами из литературы. Раздел V — заключение.



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

[1] W. Kiess and M. Mauve, “A survey on real-world implementations of mobile ad-hoc networks,” Ad Hoc Netw., vol. 5, no. 3, pp. 324–339, 2007.

[2] G. J. Pottie, “Wireless sensor networks,” in Proc. IEEE Inf. Theory Workshop, Jun. 1998, pp. 139–140.

[3] I. F. Akyildiz, X. Wang, and W. Wang, “Wireless mesh networks: A survey,” Comput. Netw., vol. 47, no. 4, pp. 445–487, 2005.

[4] C. Bettstetter and C. Hartmann, “Connectivity of wireless multihop networks in a shadow fading environment,” Wireless Netw., vol. 11, no. 5, pp. 571–579, 2005.

[5] P. Gupta and P. R. Kumar, “Critical power for asymptotic connectivity in wireless networks,” in Stochastic Analysis, Control, Optimization and Applications. Boston, MA, USA: Birkhäuser, 1999, pp. 547–566.

[6] P. Gupta and P. R. Kumar, “The capacity of wireless networks,” IEEE Trans. Inf. Theory, vol. 46, no. 2, pp. 388–404, Mar. 2006.

[7] J. Li, C. Blake, D. S. J. De Couto, H. I. Lee, and R. Morris, “Capacity of ad hoc wireless networks,” in Proc. 7th Annu. Int. Conf. Mobile Comput. Netw., 2001, pp. 61–69.

[8] M. Grossglauser and D. N. C. Tse, “Mobility increases the capacity of ad hoc wireless networks,” IEEE/ACM Trans. Netw., vol. 10, no. 4, pp. 477–486, Aug. 2002.

[9] S. Weber, J. G. Andrews, and N. Jindal, “An overview of the transmission capacity of wireless networks,” IEEE Trans. Commun., vol. 58, no. 12, pp. 3593–3604, Dec. 2010.

[10] L. Tassiulas and A. Ephremides, “Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks,” IEEE Trans. Autom. Control, vol. 37, no. 12, pp. 1936–1948, Dec. 1992.

[11] X. Lin and N. B. Shroff, “Joint rate control and scheduling in multihop wireless networks,” in Proc. 43rd IEEE Conf. Decision Control (CDC), vol. 2. Dec. 2004, pp. 1484–1489.

[12] N. Ben Salem and J.-P. Hubaux, “A fair scheduling for wireless mesh networks,” in Proc. IEEE Workshop Wireless Mesh Netw. (WiMesh), Sep. 2005.

[13] Z. Ning, L. Guo, Y. Peng, and X. Wang, “Joint scheduling and routing algorithm with load balancing in wireless mesh network,” Comput. Elect. Eng., vol. 38, no. 3, pp. 533–550, 2012.

[14] Y. Li and A. Ephremides, “A joint scheduling, power control, and routing algorithm for ad hoc wireless networks,” Ad Hoc Netw., vol. 5, no. 7, pp. 959–973, 2007.

[15] R. L. Cruz and A. V. Santhanam, “Optimal routing, link scheduling and power control in multihop wireless networks,” in Proc. 22nd Annu. Joint Conf. IEEE Comput. Commun. (INFOCOM), vol. 1. Mar./Apr. 2003, pp. 702–711.

[16] E. Hyytia and J. Virtamo, “On load balancing in a dense wireless multihop network,” in Proc. 2nd Conf. Next Generat. Internet Design Eng. (NGI), 2006, p. 8.

[17] A. Sgora, D. J. Vergados, and D. D. Vergados, “A survey of TDMA scheduling schemes in wireless multihop networks,” ACM Comput. Surv., vol. 47, no. 3, p. 53, 2015.

[18] R. Gunasekaran, S. Siddharth, P. Krishnaraj, M. Kalaiarasan, and V. R. Uthariaraj, “Efficient algorithms to solve broadcast scheduling problem in WiMAX mesh networks,” Comput. Commun., vol. 33, no. 11, pp. 1325–1333, 2010.

[19] J.-S. Li, K.-H. Liu, and C.-H. Wu, “Efficient group multicast node scheduling schemes in multi-hop wireless networks,” Comput. Commun., vol. 35, no. 10, pp. 1247–1258, 2012.

[20] C.-T. Chiang, H.-C. Chen, W.-H. Liao, and K.-P. Shih, “A decentralized minislot scheduling protocol (DMSP) in TDMA-based wireless mesh networks,” J. Netw. Comput. Appl., vol. 37, pp. 206–215, Jan. 2014.

[21] D. Arivudainambi and D. Rekha, “Heuristic approach for broadcast scheduling, problem in wireless mesh networks,” AEU-Int. J. Electron. Commun., vol. 68, no. 6, pp. 489–495, 2014.

[22] Y. Liu, V. O. K. Li, K.-C. Leung, and L. Zhang, “Topology-transparent distributed multicast and broadcast scheduling in mobile ad hoc networks,” in Proc. IEEE 75th Veh. Technol. Conf. (VTC Spring), May 2012, pp. 1–5.

[23] B. Zeng and Y. Dong, “A collaboration-based distributed TDMA scheduling algorithm for data collection in wireless sensor networks,” J. Netw., vol. 9, no. 9, pp. 2319–2327, 2014.

[24] C. Xu, Y. Xu, Z. Wang, and H. Luo, “A topology-transparent MAC scheduling algorithm with guaranteed QoS for multihop wireless network,” J. Control Theory Appl., vol. 9, no. 1, pp. 106–114, 2011.

[25] N. Lam, M. K. An, D. T. Huynh, and T. Nguyen, “Broadcast scheduling problem in SINR model,” Int. J. Found. Comput. Sci., vol. 25, no. 3, pp. 331–342, 2014.

[26] D. Arivudainambi and S. Balaji, “Improved memetic algorithm for energy efficient sensor scheduling with adjustable sensing range,” Wireless Pers. Commun., vol. 95, no. 2, pp. 1737–1758, 2016.

[27] Y. Liu, V. O. K. Li, K.-C. Leung, and L. Zhang, “Performance improvement of topology-transparent broadcast scheduling in mobile ad hoc networks,” IEEE Trans. Veh. Technol., vol. 63, no. 9, pp. 4594–4605, Nov. 2014.

[28] X. Tian, J. Yu, L. Ma, G. Li, and X. Cheng, “Distributed deterministic broadcasting algorithms under the SINR model,” in Proc. IEEE INFOCOM, Apr. 2016, pp. 1–9.

[29] J. G. Andrews et al., “What will 5G be?” IEEE J. Sel. Areas Commun., vol. 32, no. 6, pp. 1065–1082, Jun. 2014.

[30] N. Panwar, S. Sharma, and A. K. Singh, “A survey on 5g: The next generation of mobile communication,” Phys. Commun., vol. 18, pp. 64–84, Mar. 2016. [Online]. Available: http://www.sciencedirect.com/science/ article/pii/S1874490715000531

[31] J. Li, X. Wu, and R. Laroia, OFDMA Mobile Broadband Communications: A Systems Approach, 1st ed. New York, NY, USA: Cambridge Univ. Press, 2013.

[32] J. Xiao, C. Yang, J. Wang, and H. Dai, “Joint interference management in ultra-dense small cell networks: A multi-dimensional coordination,” in Proc. 8th Int. Conf. Wireless Commun. Signal Process. (WCSP), Oct. 2016, pp. 1–5.

[33] J. Andrews, S. Singh, Q. Ye, X. Lin, and H. Dhillon, “An overview of load balancing in HetNets: Old myths and open problems,” IEEE Wireless. Commun., vol. 21, no. 2, pp. 18–25, Apr. 2014.

[34] D. J. Vergados, N. Amelina, Y. Jiang, K. Kralevska, and O. Granichin, “Local voting: Optimal distributed node scheduling algorithm for multihop wireless networks,” in Proc. INFOCOM Workshop, Atlanta, GA, USA, May 2017, pp. 931–932.

[35] N. Amelina, A. Fradkov, Y. Jiang, and D. J. Vergados, “Approximate consensus in stochastic networks with application to load balancing,” IEEE Trans. Inf. Theory, vol. 61, no. 4, pp. 1739–1752, Apr. 2015.

[36] J. N. Tsitsiklis, D. P. Bertsekas, and M. Athans, “Distributed asynchronous deterministic and stochastic gradient optimization algorithms,” IEEE Trans. Autom. Control, vol. AC-31, no. 9, pp. 803–812, Sep. 1986.

[37] M. Huang, “Stochastic approximation for consensus: A new approach via ergodic backward products,” IEEE Trans. Autom. Control, vol. 57, no. 12, pp. 2994–3008, Dec. 2012.

[38] V. S. Borkar, Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge, U.K.: Cambridge Univ. Press, 2008.

[39] O. Granichin and N. Amelina, “Simultaneous perturbation stochastic approximation for tracking under unknown but bounded disturbances,” IEEE Trans. Autom. Control, vol. 60, no. 6, pp. 1653–1658, Jun. 2015.



Теги: беспроводные многоузловые сети, алгоритм планирования работы узлов, беспроводные mesh-сети, балансировка загрузки