27 40 2016

Информационные процессы, Том 16, № 1, 2016, стр. 27–40. c 2016 Банков, Хоров, Ляхов. ÏÅÐÅÄÀ×À ÈÍÔÎÐÌÀÖÈÈ Â ÊÎÌÏÜÞÒÅÐÍÛÕ ÑÅÒßÕ Èññëåäîâàíèå ïðîòîêîëà öåíòðàëèçîâàííîãî óïðàâëåíèÿ ïðîöåññîì ïðèñîåäèíåíèÿ óñòðîéñòâ â ñåòÿõ IEEE 802.11ah 1 Ä. Â. Áàíêîâ, Å. Ì. Õîðîâ, À. È. Ëÿõîâ Институт проблем передачи информации им. А. А. Харкевича РАН, Москва, Россия Ïîñòóïèëà â ðåäêîëëåãèþ 04.02.2016 Аннотация—Во многих практических сценариях рассматривается группа мобильных и автономных устройств, одновременно пытающихся подключиться к беспроводной сети. Если размер группы большой, для установки соединения, включающей в себя обмен сообщениями для аутентификации и ассоциации, может потребоваться длительное время из-за конкуренции устройств за доступ к каналу. В данной работе исследуется способ ускорить процесс присоединения устройств в сетях Wi-Fi нового поколения. В частности, исследован протокол централизованного управления присоединением, представленный в дополнении к стандарту IEEE 802.11ah. В работе описан способ адаптивного выбора его параметров. В работе также представлен способ понижения конкуренции при установке соединения, эффективный даже при наличии станций, работающих согласно старому стандарту сетей Wi-Fi. С помощью имитационногом моделирования проверена эффективность предложенных способов и показано, что среднее время установки соединения можно понизить на два порядка по сравнению со старым методом присоединения. ÊËÞ×ÅÂÛÅ ÑËÎÂÀ: íîâêà ñîåäèíåíèÿ. Èíòåðíåò Âåùåé, IEEE 802.11ah, àóòåíòèôèêàöèÿ, áûñòðàÿ óñòà- 1. ÂÂÅÄÅÍÈÅ Ïîòðåáíîñòü îáùåñòâåííîñòè â ñêîðîñòíîì áåñïðîâîäíîì äîñòóïå ê ñåòè Èíòåðíåò íåïðåðûâíî ðàñò¼ò, ÷òî ñòàâèò ìíîæåñòâî çàäà÷ äëÿ ðàçðàáîò÷èêîâ è èññëåäîâàòåëåé ñåòåâûõ ïðîòîêîëîâ. Ïîìèìî ðàñòóùåãî îáú¼ìà òðàôèêà, ýêñïîíåíöèàëüíî ðàñò¼ò ÷èñëî áåñïðîâîäíûõ óñòðîéñòâ [1,2], ÷òî îáóñëîâëåíî íå òîëüêî ðàñïðîñòðàíåíèåì ìîáèëüíûõ óñòðîéñòâ, íî è ïîïóëÿðèçàöèåé èäåè Èíòåðíåòà Âåùåé. Îäíîé èç íàèáîëåå ðàñïðîñòðàí¼ííûõ áåñïðîâîäíûõ òåõíîëîãèé ïåðåäà÷è äàííûõ ÿâëÿåòñÿ Wi-Fi. Áîëüøèíñòâî ñîâðåìåííûõ íîóòáóêîâ è ìîáèëüíûõ òåëåôîíîâ îáîðóäîâàíû Wi-Fièíòåðôåéñîì. Ñîãëàñíî ðåçóëüòàòàì ýêñïåðèìåíòîâ [3], â áîëüøèõ ãîðîäàõ ïîëüçîâàòåëè 70% âðåìåíè ïðîâîäÿò â çîíàõ ïîêðûòèÿ Wi-Fi. Ê ñîæàëåíèþ, îäíîâðåìåííîå ïîäêëþ÷åíèå áîëüøîãî ÷èñëà ïîëüçîâàòåëåé ê îäíîé òî÷êå äîñòóïà Wi-Fi ñîïðÿæåíî ñ ðÿäîì ïðîáëåì.  êà÷åñòâå ïðèìåðà ðàññìîòðèì ñåòü Wi-Fi â ìåòðî. Ïîñëå ïðèáûòèÿ ïîåçäà íà ñòàíöèþ, ñîòíè ïàññàæèðîâ ïîêèäàþò ïîåçä. Ïîêà ïàññàæèðû èäóò ïî ïëàòôîðìå, èõ ìîáèëüíûå óñòðîéñòâà ïûòàþòñÿ ïîäêëþ÷èòüñÿ ê áëèæàéøåé òî÷êå äîñòóïà. Íåèçáåæíàÿ êîíêóðåíöèÿ çà äîñòóï ê áåñïðîâîäíîìó êàíàëó ïðèâîäèò ê êîëëèçèÿì êàäðîâ-çàïðîñîâ íà ïîäêëþ÷åíèå, ÷òî ðåçêî óâåëè÷èâàåò âðåìÿ óñòàíîâêè ñîåäèíåíèÿ.  ðåçóëüòàòå ïàññàæèðû ïîêèäàþò ïëàòôîðìó äî óñòàíîâêè ñîåäèíåíèÿ. Ðàññìîòðèì åù¼ îäèí ïðèìåð, ñâÿçàííûé ñ îãðîìíûì ÷èñëîì óñòðîéñòâ â ñöåíàðèÿõ Èíòåðíåòà Âåùåé. Íîâîå äîïîëíåíèå ê ñòàíäàðòó Wi-Fi [4], IEEE 802.11ah [5], äîïóñêàåò ïîäêëþ÷åíèå 1 Èññëåäîâàíèå âûïîëíåíî ïðè ôèíàíñîâîé ïîääåðæêå ÐÔÔÈ â ðàìêàõ íàó÷íîãî ïðîåêòà  15-07-09350 à.  28 БАНКОВ, ХОРОВ, ЛЯХОВ äî 8192 ñòàíöèé (STA) ê îäíîé òî÷êå äîñòóïà.  ñöåíàðèÿõ Èíòåðíåòà Âåùåé ñòàíöèè ïåðèîäè÷åñêè ïåðåäàþò äàííûå íåáîëüøîãî îáú¼ìà. Áëàãîäàðÿ ìàëîé èíòåíñèâíîñòè ïîòîêîâ äàííûõ ðàáîòà òàêîãî áîëüøîãî ÷èñëà ñòàíöèé â ñåòè íå ïðèâîäèò ê ïåðåãðóçêå òî÷êè äîñòóïà, íî ïðåäïîëîæèì, ÷òî ïðîèçîøëî îòêëþ÷åíèå ïèòàíèÿ èëè òî÷êà äîñòóïà áûëà ïåðåçàãðóæåíà. Ïîñëå âêëþ÷åíèÿ òî÷êè äîñòóïà âñå ðàíåå ïîäêëþ÷åííûå ê íåé ñòàíöèè ïûòàþòñÿ ïîäêëþ÷èòüñÿ ê íåé çàíîâî. Óñòàíîâêà ñîåäèíåíèé ñ áîëüøèì êîëè÷åñòâîì ñòàíöèé òðåáóåò ìíîãî âðåìåíè. Ñîãëàñíî [6], äàæå 100 ñòàíöèé áóäóò ïîäêëþ÷àòüñÿ áîëåå 5 ìèíóò. Áîëåå òîãî, êîëëèçèè êàäðîâ è ïîñëåäóþùèå ïîâòîðíûå ïîïûòêè èõ ïåðåäà÷è ïîâûøàþò ýíåðãîïîòðåáëåíèå óñòðîéñòâ, ÷òî ìîæåò áûòü íåäîïóñòèìûì â ñëó÷àå àâòîíîìíî ðàáîòàþùèõ ñåíñîðîâ. Óïðîù¼ííî ïðîöåäóðà ïðèñîåäèíåíèÿ â ñåòÿõ Wi-Fi ñîñòîèò èç äâóõ øàãîâ: àóòåíòèôèêàöèè è àññîöèàöèè. Ïðè àóòåíòèôèêàöèè ñòàíöèÿ è òî÷êà äîñòóïà îáìåíèâàþòñÿ ñåêðåòíûìè êëþ÷àìè. Äàæå â ñëó÷àå îòêðûòîé (Open System) àóòåíòèôèêàöèè, ò.å. êîãäà íå èñïîëüçóåòñÿ ñåêðåòíûé êëþ÷, ñòàíöèÿ ïîñûëàåò çàïðîñ íà àóòåíòèôèêàöèþ ( ), à òî÷êà äîñòóïà â îòâåò ïîñûëàåò ïîäòâåðæäåíèå àóòåíòèôèêàöèè ( ), â êîòîðîì óêàçûâàåò, ÷òî äàííûé òèï àóòåíòèôèêàöèè ïîääåðæèâàåòñÿ è ðàçðåø¼í. Ïðè àññîöèàöèè  îáìåíå çàïðîñîì è ïîäòâåðæäåíèåì àññîöèàöèè ( è , ñîîòâåòñòâåííî)  ñòàíöèÿ è òî÷êà äîñòóïà îáìåíèâàþòñÿ èíôîðìàöèåé î ïîääåðæèâàåìûõ ñèãíàëüíîêîäîâûõ êîíñòðóêöèÿõ, ÷àñòîòíûõ êàíàëàõ è ò.ä. Êðîìå òîãî, ïðè àññîöèàöèè ñòàíöèè ïðèñâàèâàåòñÿ èäåíòèôèêàòîð Association ID (AID) è çàäàþòñÿ ïàðàìåòðû äîñòóïà ê êàíàëó. Ëèøü ïîñëå àññîöèàöèè ñòàíöèè ðàçðåøåíî îòïðàâëÿòü êàäðû ñ äàííûìè. Ïîñêîëüêó ïåðâûì ïîñûëàåìûì ñòàíöèåé êàäðîì ÿâëÿåòñÿ AuthReq, îãðàíè÷èâàÿ êîëè÷åñòâî ïðèñòóïàþùèõ ê àóòåíòèôèêàöèè ñòàíöèé ìîæíî ñíèçèòü êîíêóðåíöèþ çà äîñòóï ê êàíàëó è òàêèì îáðàçîì óñêîðèòü óñòàíîâêó ñîåäèíåíèÿ â öåëîì. Äàííûé ïîäõîä èñïîëüçóåòñÿ â íîâûõ äîïîëíåíèÿõ ê ñòàíäàðòó Wi-Fi [4, 5, 7].  ÷àñòíîñòè, IEEE 802.11ah îïèñûâàåò ïðîòîêîë öåíòðàëèçîâàííîãî óïðàâëåíèÿ ïðèñîåäèíåíèåì, ïîçâîëÿþùèé òî÷êå äîñòóïà ðåãóëèðîâàòü äîëþ ñòàíöèé, êîòîðûì ðàçðåøåíî çàïðîñèòü àóòåíòèôèêàöèþ. Ýôôåêòèâíîñòü äàííîãî ïðîòîêîëà îïðåäåëÿåòñÿ âûáîðîì åãî ïàðàìåòðîâ, çíà÷åíèÿ êîòîðûõ íåîáõîäèìî èçìåíÿòü â çàâèñèìîñòè îò ñîñòîÿíèÿ êàíàëà è îò ÷èñëà ïðèñîåäèíÿþùèõñÿ ñòàíöèé. Ñòàíäàðò íå ñïåöèôèöèðóåò ïîëèòèêó âûáîðà ïàðàìåòðîâ ïðîòîêîëà, è ïîýòîìó àâòîðàìè äàííîé ñòàòüè ðàçðàáàòûâàþòñÿ íåñêîëüêî àëãîðèòìîâ àäàïòèâíîãî âûáîðà ïàðàìåòðîâ, ïîçâîëÿþùèõ óñêîðèòü óñòàíîâêó ñîåäèíåíèÿ, è ïðèâîäèòñÿ èññëåäîâàíèå ýôôåêòèâíîñòè ýòèõ àëãîðèòìîâ. Äàëüíåéøåå èçëîæåíèå ïîñòðîåíî ñëåäóþùèì îáðàçîì.  ðàçäåëå 2 îïèñàíû ñïîñîáû óñêîðèòü ïðîöåññ óñòàíîâêè ñîåäèíåíèÿ â ñåòÿõ Wi-Fi, ïðåäñòàâëåííûå â ëèòåðàòóðå è â äîïîëíåíèÿõ ê ñòàíäàðòó IEEE 802.11.  ýòîì ðàçäåëå òàêæå ïðåäñòàâëåíà íîâàÿ, íî ïðè ýòîì ñîâìåñòèìàÿ ñ îñíîâíîé âåðñèåé ñòàíäàðòà ñõåìà äîñòóïà ê êàíàëó áåç êîíêóðåíöèè äëÿ ïåðåäà÷è êàäðîâ AuthRep, AReq è ARep.  ðàçäåëå 3 ïðèâåäåíû àëãîðèòìû, ïîçâîëÿþùèå îöåíèòü êîëè÷åñòâî ïîäêëþ÷àþùèõñÿ ñòàíöèé è ñîîòâåòñòâóþùèì îáðàçîì âûáèðàòü ïàðàìåòðû ïðîòîêîëà.  ðàçäåëå 4 ïîêàçàíû ðåçóëüòàòû ñðàâíåíèÿ ïðîèçâîäèòåëüíîñòè ðàçðàáîòàííûõ àëãîðèòìîâ â ðàçëè÷íûõ ñöåíàðèÿõ. Ðàçäåë 5 ñîäåðæèò çàêëþ÷åíèå. AuthReq AuthRep AReq ARep 2. ÑÏÎÑÎÁÛ ÓÑÊÎÐÅÍÈß ÏÐÎÖÅÑÑÀ ÏÐÈÑÎÅÄÈÍÅÍÈß 2.1. Îáçîð ëèòåðàòóðû  òå÷åíèå äëèòåëüíîãî âðåìåíè ïðîöåññ ïðèñîåäèíåíèÿ ñ÷èòàëñÿ äîñòàòî÷íî áûñòðûì â áîëüøèíñòâå ñöåíàðèåâ. Ñíèæåíèå âðåìåíè ïðèñîåäèíåíèÿ áûëî âàæíûì â ñåòÿõ ñ ìóëüòèìåäèéíûì òðàôèêîì ðåàëüíîãî âðåìåíè. Íàïðèìåð, â [8] ðàññìàòðèâàåòñÿ òåõíîëîãèÿ WiMedia âûñîêîñêîðîñòíûõ ïåðñîíàëüíûõ ñåòåé, èñïîëüçóåìûõ â äîìàøíèõ ìóëüòèìåäèéíûõ ñèñòåìàõ. ÈÍÔÎÐÌÀÖÈÎÍÍÛÅ ÏÐÎÖÅÑÑÛ ÒÎÌ 16  1 2016  ПРИСОЕДИНЕНИЕ УСТРОЙСТВ В СЕТЯХ IEEE 802.11AH 29 Èññëåäóåòñÿ ñöåíàðèé, â êîòîðîì ïîñëå íåîæèäàííîãî îáíàðóæåíèÿ åù¼ îäíîé ñóùåñòâóþùåé ïîáëèçîñòè ñåòè (íàïðèìåð, èç-çà òîãî, ÷òî îòêðûëè äâåðü), ñåòü ïåðåêëþ÷àåòñÿ íà äðóãîé êàíàë, è âñå ñòàíöèè äîëæíû çàíîâî ïðèñîåäèíèòüñÿ ê ñåòè â íîâîì êàíàëå. Àâòîðû [8] ðàçðàáîòàëè ìàòåìàòè÷åñêóþ ìîäåëü ïðîöåññà ïðèñîåäèíåíèÿ è ïðåäëîæèëè ñïîñîá ìèíèìèçèðîâàòü âðåìÿ ïðèñîåäèíåíèÿ ãðóïïû ñòàíöèé. Çàäà÷à óñêîðåíèÿ ïðîöåññà ïðèñîåäèíåíèÿ ïðèîáðåòàåò àêòóàëüíîñòü èç-çà âîçðîñøåãî ñïðîñà íà ìîáèëüíûé Èíòåðíåò, â ÷àñòíîñòè, âîçíèêëà íåîáõîäèìîñòü â áûñòðîì ïåðåêëþ÷åíèè ìåæäó ñîòàìè è â áåñøîâíîì ðîóìèíãå.  [9] ðàññìîòðåí ïðîöåññ ïåðåêëþ÷åíèÿ ìåæäó òî÷êàìè äîñòóïà â ñåòÿõ Wi-Fi è ïðåäëîæåíà ñõåìà, ïîçâîëÿþùàÿ ñòàíöèè ïåðåäàâàòü äàííûå â çàùèù¼ííîì ðåæèìå íîâîé òî÷êå äîñòóïà äàæå äî òîãî, êàê ñîåäèíåíèå ñ íåé îêîí÷àòåëüíî óñòàíîâëåíî. Äëÿ ýòîãî ñòàíöèÿ èñïîëüçóåò âðåìåííûé òóííåëü ÷åðåç ïðåäûäóùóþ òî÷êó äîñòóïà, ñ êîòîðîé åù¼ íå ðàçîðâàíî ñîåäèíåíèå. Ñîâðåìåííûé èíòåðåñ ê áûñòðîìó óñòàíîâëåíèþ ñîåäèíåíèÿ â ñåòÿõ Wi-Fi ñâÿçàí ñ âîçíèêàþùèìè ñöåíàðèÿìè, â êîòîðûõ ìíîæåñòâî ñòàíöèé ðàñïîëîæåíû áëèçêî äðóã ê äðóãó. Èõ îäíîâðåìåííûå ïîïûòêè ïðèñîåäèíèòüñÿ ê òî÷êå äîñòóïà ïðèâîäÿò ê ìíîãîêðàòíûì êîëëèçèÿì êàäðîâ è ê áîëüøîìó âðåìåíè ïîäêëþ÷åíèÿ. Îäíî èç ðåøåíèé äàííîé ïðîáëåìû, èçâåñòíîå êàê Fast Initial Link Set-up, ïîäðîáíî ðàññìàòðèâàåòñÿ â äîïîëíåíèè IEEE 802.11ai [10].  ïåðâóþ î÷åðåäü, äàííîå äîïîëíåíèå îïèñûâàåò ñïîñîá óìåíüøèòü âðåìÿ îáíàðóæåíèÿ ñóùåñòâóþùèõ â îáëàñòè ñëûøèìîñòè ñåòåé. Äàííûé ñïîñîá ñîñòîèò â òîì, ÷òî òî÷êà äîñòóïà ðåêëàìèðóåò íå òîëüêî ñâîþ ñåòü, íî è äðóãèå ñåòè, íàõîäÿùèåñÿ ïîáëèçîñòè. Äàëåå äîïîëíåíèå ê ñòàíäàðòó îïèñûâàåò ñïîñîá áûñòðîãî ïîëó÷åíèÿ IP-àäðåñà áëàãîäàðÿ îáìåíó èíôîðìàöèåé âåðõíèõ óðîâíåé ñòåêà ïðîòîêîëîâ, íàïðèìåð, ïðîòîêîëîâ DHCP/IP. Òàêæå îïèñûâàåòñÿ ñïîñîá ñíèçèòü ÷èñëî êîëëèçèé ïðè ïðèñîåäèíåíèè ïóò¼ì óìåíüøåíèÿ êîëè÷åñòâà ñòàíöèé, êîíêóðèðóþùèõ çà äîñòóï ê êàíàëó. Äëÿ ýòîãî òî÷êà äîñòóïà âûäåëÿåò èíòåðâàëû âðåìåíè, â òå÷åíèå êîòîðûõ òîëüêî îïðåäåë¼ííàÿ ïîäãðóïïà ñòàíöèé ìîæåò ïîëó÷àòü äîñòóï ê êàíàëó. Ñòàíöèè äåëÿòñÿ íà ïîäãðóïïû ïî (à) ïðèîðèòåòó òðàôèêà, (á) ñîîòâåòñòâèè àäðåñà íåêîòîðîé ìàñêå ïîäñåòè. Ê ñîæàëåíèþ, îïèñàííûå ïîäõîäû ìîãóò áûòü íåýôôåêòèâíûìè â ïðàêòè÷åñêèõ ñöåíàðèÿõ ïî ñëåäóþùèì ïðè÷èíàì. Ðàçäåëåíèå ñòàíöèé íà ïîäãðóïïû ïî ïðèîðèòåòó òðàôèêà íåýôôåêòèâíî â ñëó÷àå, êîãäà áîëüøèíñòâî ñòàíöèé ïåðåäàþò äàííûå îäíîãî òèïà.  òî æå âðåìÿ ðàçäåëåíèå ïî ìàñêå ïîäñåòè òîæå ìîæåò áûòü íåýôôåêòèâíûì, ïîñêîëüêó àäðåñà íåðàâíîìåðíî ðàñïðåäåëåíû â ïðîñòðàíñòâå àäðåñîâ, èõ ðàñïðåäåëåíèå çàâèñèò îò ðåãèîíà, íàñòðîåê ïðîèçâîäèòåëÿ è ò.ä. Ïî ýòîé ïðè÷èíå â äàííîé ðàáîòå ðàññìàòðèâàåòñÿ äðóãîé ïîäõîä  ïðîòîêîë öåíòðàëèçîâàííîãî óïðàâëåíèÿ ïðèñîåäèíåíèåì, îïèñàííûé â IEEE 802.11ah1 [11],  êîòîðûé îñíîâàí íà ïîõîæèõ èäåÿõ, íî íå îáëàäàåò óïîìÿíóòûìè íåäîñòàòêàìè. 2.2. Ïðîòîêîë öåíòðàëèçîâàííîãî óïðàâëåíèÿ ïðèñîåäèíåíèåì Ïðîòîêîë öåíòðàëèçîâàííîãî óïðàâëåíèÿ ïðèñîåäèíåíèåì ïîçâîëÿåò òî÷êå äîñòóïà ðåãóëèðîâàòü êîëè÷åñòâî ñòàíöèé, îäíîâðåìåííî çàïðàøèâàþùèõ àóòåíòèôèêàöèþ. Äëÿ ýòîãî òî÷êà äîñòóïà øèðîêîâåùàòåëüíî ðàññûëàåò ñïåöèàëüíûå óïðàâëÿþùèå êàäðû  áèêîíû, êîòîðûå óêàçûâàþò îêðóæàþùèì ñòàíöèÿì íà ïðèñóòñòâèå òî÷êè äîñòóïà è ñîäåðæàò â ñåáå ïàðàìåòðû ñåòè. Áèêîíû ðàññûëàþòñÿ ñ ïåðèîäîì BI (Beacon Interval), à âðåìåííîé ïðîìåæóòîê ìåæäó äâóìÿ ïîñëåäîâàòåëüíûìè áèêîíàìè íàçûâàåòñÿ áèêîí-èíòåðâàëîì. Òî÷êà äîñòóïà âêëþ÷àåò â áèêîíû çíà÷åíèå òàê íàçûâàåìîãî ïîðîãà àóòåíòèôèêàöèè (Authentication Control Threshold) θ. Çíà÷åíèå θ ÿâëÿåòñÿ öåëûì ÷èñëîì èç èíòåðâàëà [0, 1023] è âûáèðàåòñÿ òî÷êîé äîñòóïà 1 Ñòðîãî ãîâîðÿ, äîïîëíåíèå IEEE 802.11ah îïðåäåëÿåò ïðîòîêîëû öåíòðàëèçîâàííîãî è ðàñïðåäåë¼ííîãî óïðàâëåíèÿ ïðèñîåäèíåíèåì [5]. Îäíàêî ïîñëåäíèé â äàííîé ðàáîòå íå ðàññìàòðèâàåòñÿ. ÈÍÔÎÐÌÀÖÈÎÍÍÛÅ ÏÐÎÖÅÑÑÛ ÒÎÌ 16  1 2016  30 БАНКОВ, ХОРОВ, ЛЯХОВ ñîãëàñíî íåêîòîðîìó àëãîðèòìó. Ñòàíäàðò íå ñïåöèôèöèðóåò àëãîðèòì âûáîðà ïîðîãà, âîçìîæíûå àëãîðèòìû îïèñàíû è èçó÷åíû â äàííîé ðàáîòå. Ñòàíöèÿ, êîòîðàÿ õî÷åò ïðèñîåäèíèòüñÿ ê òî÷êå äîñòóïà, ñëó÷àéíûì îáðàçîì âûáèðàåò çíà÷åíèå v. Äàííîå çíà÷åíèå ðàâíîâåðîÿòíî âûáèðàåòñÿ èç íàáîðà 0, 1, ..., 1022. Åñëè v ìåíüøå, ÷åì ïðèíÿòîå θ, ñòàíöèÿ ìîæåò ïåðåäàòü çàïðîñ íà àóòåíòèôèêàöèþ â òåêóùåì áèêîí-èíòåðâàëå.  ïðîòèâíîì ñëó÷àå, ñòàíöèÿ æä¼ò ñëåäóþùèé áèêîí è çàíîâî ãåíåðèðóåò ñëó÷àéíîå çíà÷åíèå v.  ðåçóëüòàòå, ÷åì áîëüøå θ, òåì áîëüøå ñòàíöèé ìîãóò çàïðîñèòü àóòåíòèôèêàöèþ â òåêóùåì áèêîí-èíòåðâàëå.  ÷àñòíîñòè, åñëè θ = 1023, òî âñå ñòàíöèè ïûòàþòñÿ óñòàíîâèòü ñîåäèíåíèå. Êîãäà ÷èñëî ñòàíöèé íåâåëèêî, θ äîëæíî áûòü áîëüøèì, ÷òîáû âñå ñòàíöèè ìîãëè ïðèñîåäèíèòüñÿ áåç çàäåðæêè.  ïðîòèâîïîëîæíîì ñëó÷àå, êîãäà ñòàíöèé ìíîãî, θ äîëæíî áûòü ìàëûì, ÷òîáû äîñòóï ê êàíàëó ïîëó÷àëî íåáîëüøîå êîëè÷åñòâî ñòàíöèé è êîíêóðåíöèÿ çà äîñòóï ê êàíàëó áûëà íåâûñîêîé. Èíûìè ñëîâàìè, òî÷êà äîñòóïà äîëæíà âûáèðàòü θ àäàïòèâíî, îñíîâûâàÿñü íà òîì, ñêîëüêî ñòàíöèé õîòÿò ïðèñîåäèíèòüñÿ. Ê ñîæàëåíèþ, òî÷êà äîñòóïà íå çíàåò êîëè÷åñòâî ïîäêëþ÷àþùèõñÿ ñòàíöèé è äîëæíà åãî îöåíèâàòü.  äàííîé ðàáîòå ïðåäëàãàþòñÿ è èññëåäóþñÿ íåñêîëüêî ïîäõîäîâ ê îöåíêå êîëè÷åñòâà ïîäêëþ÷àþùèõñÿ ñòàíöèé è ê âûáîðó çíà÷åíèÿ ïîðîãà. Êîíå÷íîé öåëüþ ÿâëÿåòñÿ ìèíèìèçàöèÿ ñðåäíåãî âðåìåíè ïîäêëþ÷åíèÿ ñòàíöèé. Òàêæå ïðåäëàãàåòñÿ ñõåìà, ïîçâîëÿþùóþ èçáåæàòü êîíêóðåíöèþ ïðè ïåðåäà÷å êàäðîâ AuthRep, AReq and ARep, êîòîðàÿ õîðîøà òåì, ÷òî èñïîëüçóåò òîëüêî ìåõàíèçìû, îïðåäåë¼ííûå â îñíîâíîì ñòàíäàðòå Wi-Fi è òàêèì îáðàçîì íå òðåáóåò ìîäèôèêàöèè ñòàíöèé. 2.3. Ïðåäëàãàåìàÿ ñõåìà äëÿ áåñêîíêóðåíòíîãî äîñòóïà ê êàíàëó Ãëàâíàÿ èäåÿ ïðåäëàãàåìîé ñõåìû ñîñòîèò â òîì, ÷òîáû â ïðîöåññå ïðèñîåäèíåíèÿ ñòàíöèè êîíêóðèðîâàëè òîëüêî ïðè îòïðàâêå êàäðîâ AuthReq. Íà ïåðâûé âçãëÿä, ýòî ìîæíî ñäåëàòü èñïîëüçóÿ ñòàíäàðòèçîâàííûé áåñêîíêóðåíòíûé ìåòîä äîñòóïà ê êàíàëó, íàïðèìåð, îñíîâàííûé íà îïðîñàõ PCF (Point Coordination Function) èëè ãèáðèäíûé ìåòîä äîñòóïà ê êàíàëó HCCA (Hybrid Controlled Channel Access) [4], èëè ìåòîä îêíà îãðàíè÷åííîãî äîñòóïà RAW (Restricted Access Window [11], íåäàâíî ââåä¼ííûé â äîïîëíåíèè .11ah. Îäíàêî äàííûå ìåòîäû íå ìîãóò áûòü èñïîëüçîâàíû, ïîêà òî÷êà äîñòóïà íå óçíàåò âîçìîæíîñòè ñòàíöèè, ÷òî îñóùåñòâëÿåòñÿ ëèøü âî âðåìÿ àññîöèàöèè. È âñ¼ æå ñóùåñòâóåò ñïîñîá ïðåäîñòàâèòü áåñêîíêóðåíòíûé äîñòóï ê êàíàëó ïðè ïåðåäà÷å êàäðîâ AuthRep, AReq è ARep. Åñëè ñòàíöèè ðàçðåøåíî çàïðîñèòü àóòåíòèôèêàöèþ â áèêîí-èíòåðâàëå, îíà ïåðåäà¼ò êàäð AuthReq, èñïîëüçóÿ ìåòîä ñëó÷àéíîãî äîñòóïà Wi-Fi, êîòîðûé ðàáîòàåò ñëåäóþùèì îáðàçîì. Ïåðåä ïåðåäà÷åé êàäðà ñòàíöèÿ èíèöèàëèçèðóåò ñ÷¼ò÷èê îòñðî÷êè ñëó÷àéíûì öåëûì ÷èñëîì, ðàâíîâåðîÿòíî âûáðàííûì èç íàáîðà 0, ..., CWr , ãäå r  çíà÷åíèå ñ÷¼ò÷èêà ïîâòîðíûõ ïîïûòîê ïåðåäà÷è (èçíà÷àëüíî ðàâíîå 0), à ïàðàìåòð CWr íàçûâàåòñÿ êîíêóðåíòíûì îêíîì è îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì: ( CWmin , r = 0, CWr = max {CWmax , 2CWr−1 + 1} r = 6 0, ãäå ìèíèìàëüíîå è ìàêñèìàëüíîå çíà÷åíèÿ êîíêóðåíòíîãî îêíà (CWmin è CWmax, ñîîòâåòñòâåííî) çàäàþòñÿ òî÷êîé äîñòóïà. Ñòàíöèÿ ñëóøàåò êàíàë è óìåíüøàåò ñ÷¼ò÷èê îòñðî÷êè íà åäèíèöó êàæäûé ðàç, êîãäà êàíàë îêàçûâàåòñÿ ñâîáîäíûì â òå÷åíèå âðåìåíè σ. Åñëè êàíàë çàíÿò, ñ÷¼ò÷èê îòñðî÷êè çàìîðàæèâàåòñÿ, ïîêà êàíàë íå îñâîáîäèòñÿ è íå ïðîáóäåò ñâîáîäíûì â òå÷åíèå âðåìåíè DIFS. Êîãäà ñ÷¼ò÷èê îòñðî÷êè äîñòèãàåò íóëÿ, ñòàíöèÿ ïåðåäà¼ò êàäð è æä¼ò ïîäòâåðæäåíèå (ACK) îò ïîëó÷àòåëÿ. Åñëè ïîäòâåðæäåíèå ïîëó÷åíî, ñòàíöèÿ ñ÷èòàåò, ÷òî êàäð ïåðåäàí óñïåøíî. Åñëè ïîäâåðæäåíèå íå ïðèõîäèò â òå÷åíèå èíòåðâàëà âðåìåíè ÈÍÔÎÐÌÀÖÈÎÍÍÛÅ ÏÐÎÖÅÑÑÛ ÒÎÌ 16  1 2016  ПРИСОЕДИНЕНИЕ УСТРОЙСТВ В СЕТЯХ IEEE 802.11AH 31 AckTimeout, òî ñòàíöèÿ ñ÷èòàåò, ÷òî ïðîèçîøëà êîëëèçèÿ êàäðîâ.  ñëó÷àå êîëëèçèè êàäðîâ, åñëè ñ÷¼ò÷èê ïîâòîðíûõ ïîïûòîê ïåðåäà÷è íå äîñòèã îãðàíè÷åíèÿ (RL), ñòàíöèÿ åù¼ ðàç ïûòàåòñÿ ïåðåäàòü êàäð. Åñëè æå äîñòèãíóòî îãðàíè÷åíèå íà ÷èñëî ïîïûòîê ïåðåäà÷è, ñòàíöèÿ ñáðàñûâàåò êàäð èç î÷åðåäè íà ïåðåäà÷ó. Ïåðåä êàæäîé ïîâòîðíîé ïîïûòêîé ïåðåäà÷è, ñ÷¼ò÷èê îòñðî÷êè âûáèðàåòñÿ ñëó÷àéíûì îáðàçîì èç ðàñøèðåííîãî èíòåðâàëà, êàê ïîêàçàíî âûøå. Ïîìèìî ôèçè÷åñêîé çàíÿòîñòè êàíàëà, â ñòàíäàðòå IEEE 802.11 (è â äîïîëíåíèè IEEE 802.11ah) èñïîëüçóåòñÿ ìåõàíèçì âèðòóàëüíîé çàíÿòîñòè êàíàëà, êîòîðûé ðàáîòàåò ñëåäóþùèì îáðàçîì. Ëþáîé êàäð ñîäåðæèò ïîëå Duration, êîòîðîå ïîêàçûâàåò, êàê äîëãî êàíàë áóäåò âèðòóàëüíî çàíÿò ïîñëå îêîí÷àíèÿ êàäðà.  òå÷åíèå óêàçàííîãî âðåìåíè ñòàíöèè íå ìîãóò ïîëó÷èòü äîñòóï ê êàíàëó. Òàêîé ìåõàíèçì âèðòóàëüíîé çàíÿòîñòè ñðåäû íàçûâàåòñÿ NAV. Ñîãëàñíî ïðåäëàãàåìîé ñõåìå, ïîëó÷èâ AuthReq, òî÷êà äîñòóïà îòïðàâëÿåò ïîäòâåðæäåíèå, íî îòêëàäûâàåò îòïðàâêó AuthRep êàê ìèíèìóì äî ñëåäóþùåãî áèêîíà. Óñòàíîâèâ â áèêîíå çíà÷åíèå Duration áîëüøèì, ÷åì DIFS, òî÷êà äîñòóïà ìîæåò ãàðàíòèðîâàííî ïîëó÷èòü äîñòóï ê êàíàëó ïîñëå îòïðàâêè áèêîíà. Òî÷êà äîñòóïà ìîæåò óñòàíîâèòü äëÿ ñåáÿ çíà÷åíèå CW ðàâíûì íóëþ. Òîãäà òî÷êà äîñòóïà ÷åðåç èíòåðâàë âðåìåíè DIFS ïîñëå áèêîíà ñìîæåò ïåðåäàòü AuthRep âûáðàííîé ñòàíöèè, (ñì. ðèñ. 1).  êàäðå AuthRep òî÷êà äîñòóïà óñòàíàâëèâàåò çíà÷åíèå Duration òàêèì, ÷òîáû äðóãèå ñòàíöèè íå ìîãëè ïåðåäàâàòü êàäðû äî òåõ ïîð, ïîêà çàäàííàÿ ñòàíöèÿ íå íà÷í¼ò ïåðåäà÷ó AReq. Çäåñü ñëåäóåò çàìåòèòü äâå îñîáåííîñòè. Âî-ïåðâûõ, ñîãëàñíî ñòàíäàðòó [4, Ðàçäåë 9.3.2.4], ñòàíöèÿ, êîòîðàÿ äîëæíà îòïðàâèòü ACK, íå ó÷èòûâàåò çíà÷åíèå ïîëÿ Duration è íå èñïîëüçóåò NAV. Âî-âòîðûõ, ïðåäîòâðàùåíèÿ êîíêóðåíöèè ïðè ïåðåäà÷å êàäðà AReq, çíà÷åíèå ïîëÿ Duration êàäðà AuthRep äîëæíî âêëþ÷àòü â ñåáÿ CWmin × σ, DIFS è äëèòåëüíîñòü êàäðà ACK. Íà êàäð AReq, îòïðàâëÿåìûé ñòàíöèåé, òî÷êà äîñòóïà îòâå÷àåò ïîäâåðæäåíèåì, ñ òàêèì çíà÷åíèåì ïîëÿ Duration, êîòîðîå ïîçâîëèò òî÷êå äîñòóïà, îò êîòîðîé ðàíåå áûë ïîëó÷åí Authrep, îòïðàâèòü ARep âûáðàííîé ñòàíöèè è â áåñêîíêóðåíòíîì ðåæèìå îòïðàâèòü AuthRep ñëåäóþùåé ñòàíöèè, ðàíåå çàïðîñèâøåé àóòåíòèôèêàöèþ (ñì ðèñ. 1). BI n+1 BI n Ñ÷¼ò÷èê îòñðî÷êè AuthReq STA ACK AP ... AReq ACK Beacon ... AuthRep NAV ACK ACK NAV ARep t AuthRep NAV ... t Ðèñ. 1. Áåñêîíêóðåíòíûé äîñòóï ê êàíàëó ïðè ïåðåäà÷å êàäðîâ AuthRep, AReq è ARep Âîçíèêàåò âîïðîñ âûáîðà áèêîí-èíòåðâàëà äëÿ ïåðåäà÷è AuthRep, AReq è ARep. Âîçìîæíûé, íî íå åäèíñòâåííûé âàðèàíò ñîñòîèò â òîì, ÷òî òî÷êà äîñòóïà âûäåëÿåò áèêîí-èíòåðâàë äëÿ ïåðåäà÷è ïîñëåäîâàòåëüíîñòåé AuthRep-AReq-ARep, åñëè âûïîëíåíî õîòÿ áû îäíî óñëîâèå: 1. Ñóììàðíàÿ äëèòåëüíîñòü îæèäàåìûõ ïîñëåäîâàòåëüíîñòåé AuthRep-AReq-ARep ïðåâûøàåò BI. 2. Òåêóùåå çíà÷åíèå θ ïðåâûøàåò ïîëîâèíó ìàêñèìàëüíîãî çíà÷åíèÿ Θ = 1023. Ýòî îçíà÷àåò, ÷òî òî÷êà äîñòóïà ñ÷èòàåò, ÷òî êîíêóðåíöèÿ ïðè ïåðåäà÷å AuthReq íåâåëèêà, ò.å., êîëè÷åÈÍÔÎÐÌÀÖÈÎÍÍÛÅ ÏÐÎÖÅÑÑÛ ÒÎÌ 16  1 2016  32 БАНКОВ, ХОРОВ, ЛЯХОВ ñòâî ïûòàþùèõñÿ óñòàíîâèòü ñîåäèíåíèå ñòàíöèé ìàëî è íåò ñìûñëà æäàòü åù¼ çàïðîñû íà àóòåíòèôèêàöèþ.  ðàçäåëå 4 ïîêàçàíû ðåçóëüòàòû èìèòàöèîííîãî ìîäåëèðîâàíèÿ äëÿ äàííîãî ñïîñîáà ðàçäåëåíèÿ áèêîí-èíòåðâàëîâ. 3. ÀËÃÎÐÈÒÌÛ ÂÛÁÎÐÀ ÇÍÀ×ÅÍÈß ÏÎÐÎÃÀ  äàííîì ðàçäåëå îïèñàíû àëãîðèòìû, êîòîðûå ìîæíî èñïîëüçîâàòü äëÿ îöåíêè êîëè÷åñòâà ïîäêëþ÷àþùèñÿ ñòàíöèé è äëÿ âûáîðà çíà÷åíèÿ θ ïðè îòïðàâêå áèêîíà. Äàííûå àëãîðèòìû íàïðàâëåíû íà ìèíèìèçàöèþ âðåìåíè óñòàíîâêè ñîåäèíåíèÿ äëÿ âñåõ ñòàíöèé â ñöåíàðèè, êîãäà â íà÷àëüíûé ìîìåíò âðåìåíè îäíîâðåìåííî ïîÿâëÿåòñÿ N0 ñòàíöèé IEEE 802.11ah. Áóäåì ñ÷èòàòü, ÷òî òî÷êà äîñòóïà èñïîëüçóåò ñõåìó, ïðåäëîæåííóþ â ðàçäåëå 2.3, è âñå çàïðîñèâøèå àóòåíòèôèêàöèþ ñòàíöèè óñïåøíî ïðèñîåäèíÿþòñÿ.  ñâÿçè ñ ýòèì â äàëüíåéøåì èçëîæåíèè òåðìèíû ¾çàïðîñèòü àóòåíòèôèêàöèþ¿ è ¾ïîäêëþ÷èòüñÿ¿ áóäåì ñ÷èòàòü òîæäåñòâåííûìè. 3.1. Ïðåäâàðèòåëüíûé àíàëèç Áóäåì ïðåäïîëàãàòü, ÷òî âñå ñòàíöèè íàõîäÿòñÿ â çîíå ñëûøèìîñòè äðóã äðóãà, è ïåðåäà÷à êàäðîâ ìåæäó ñòàíöèåé è òî÷êîé äîñòóïà ïðîèñõîäèò óñïåøíî âñåãäà, êîãäà íå ïðîèçîøëà êîëëèçèÿ êàäðîâ.  òàêîì ñëó÷àå ñòàíöèè áóäóò îòñ÷èòûâàòü ñ÷¼ò÷èêè îòñðî÷êè ñèíõðîííî, ïðè÷¼ì ìîìåíòû îòñ÷¼òà ÿâëÿþòñÿ ãðàíèöåé âèðòóàëüíûõ ñëîòîâ [12], êîòîðûå ìîãóò áûòü òð¼õ òèïîâ: ïóñòûìè, óñïåøíûìè è êîëëèçèîííûìè. Äëèòåëüíîñòè âèðòóàëüíûõ ñëîòîâ è äðóãèå ïàðàìåòðû ñöåíàðèÿ óêàçàíû â òàáëèöå 1. Òàáëèöà 1. Ïàðàìåòðû ìîäåëèðîâàíèÿ Ïàðàìåòð Çíà÷åíèå Äëèòåëüíîñòü ïóñòîãî ñëîòà Te Äëèòåëüíîñòü óñïåøíîãî ñëîòà Äëèòåëüíîñòü êîëëèçèîííîãî ñëîòà Äëèòåëüíîñòü áèêîí-èíòåðâàëà 52 ìêñ 1596 ìêñ 1596 ìêñ 100 ìñ Ts Tc BI CWmin CWmax 15 1023 Ìàêñèìàëüíîå ÷èñëî ïîâòîðíûõ ïîïûòîê ïåðåäà÷è RL 7 Ïóñòü u  âåðîÿòíîñòü òîãî, ÷òî ñòàíöèÿ áóäåò ñîâåðøàòü ïîïûòêó ïîäêëþ÷åíèÿ â ñëåäóþùåì áèêîí-èíòåðâàëå. Äàííàÿ âåðîÿòíîñòü ïîëó÷àåòñÿ, åñëè îòíîðìèðîâàòü çíà÷åíèå ïîðîãà ñëåäóþùèì îáðàçîì: u = Θθ . Ïóñòü N  ñëó÷àéíàÿ âåëè÷èíà, îáîçíà÷àþùàÿ êîëè÷åñòâî íåïðèñîåäèíèâøèõñÿ ñòàíöèé, à K  ñëó÷àéíàÿ âåëè÷èíà, îáîçíà÷àþùàÿ êîëè÷åñòâî ñòàíöèé, êîòîðûì ðàçðåøåíî ïîäêëþ÷èòüñÿ â òåêóùåì áèêîí-èíòåðâàëå. Âåðîÿòíîñòü òîãî, ÷òî èç n ñòàíöèé ïðè çàäàííîì çíà÷åíèè u áóäóò ïîäêëþ÷àòüñÿ k ñòàíöèé çàäà¼òñÿ ôîðìóëîé (u) PK|N (k|n)   n k = u (1 − u)n−k . k Áóäåì íàçûâàòü ¾óñïåõîì¿ ôàêò óñïåøíîãî ïîäêëþ÷åíèÿ ñòàíöèè ê òî÷êå äîñòóïà. Íàéä¼ì ðàñïðåäåëåíèå ÷èñëà óñïåõîâ S â òå÷åíèå áèêîí-èíòåðâàëà.  [13] îïèñàíà ìàòåìàòè÷åñêàÿ ìîäåëü ñëó÷àéíîãî ìåòîäà äîñòóïà Wi-Fi, êîòîðàÿ ïîçâîëÿåò íàéòè óñëîâíîå ðàñïðåäåëåíèå PS|K , ò.å. âåðîÿòíîñòü òîãî, ÷òî èç K ñòàíöèé, äîïóùåííûõ ê ïîäêëþ÷åíèþ, S ñòàíöèé ïîäêëþ÷àòñÿ óñïåøíî. Äàííàÿ ìîäåëü ïîçâîëÿåò òàêæå íàéòè óñëîâíîå ðàñïðåäåëåíèå ÷èñëà E ïóñòûõ ÈÍÔÎÐÌÀÖÈÎÍÍÛÅ ÏÐÎÖÅÑÑÛ ÒÎÌ 16  1 2016  ПРИСОЕДИНЕНИЕ УСТРОЙСТВ В СЕТЯХ IEEE 802.11AH 33 ñëîòîâ PE|K è ñîâìåñòíîå ðàñïðåäåëåíèå PS,E|K . Òîãäà ðàñïðåäåëåíèå ÷èñëà óñïåõîâ â òåêóùåì áèêîí-èíòåðâàëå ïðè çàäàííîì îáùåì êîëè÷åñòâå ñòàíöèé è çíà÷åíèè ïîðîãà çàäà¼òñÿ ôîðìóëîé (u) PS|N (s|n) = n X (u) PS|K (s|k)PK|N (k|n) = k=s n   X n k k=s uk (1 − u)n−k PS|K (s|k), à ìàòåìàòè÷åñêîå îæèäàíèå ÷èñëà óñïåõîâ îïðåäåëÿåòñÿ êàê (u) E [S|N = n] = n X (u) sPS|N (s|n). s=0 Àíàëîãè÷íûì îáðàçîì îïðåäåëÿþòñÿ ðàñïðåäåëåíèÿ ÷èñëà ïóñòûõ ñëîòîâ è ñîâìåñòíûå ðàñïðåäåëåíèÿ ÷èñëà ïóñòûõ è óñïåøíûõ ñëîòîâ (u) PE|N (e|n) n   X n k = u (1 − u)n−k PE|K (e|k), k k=0 (u) PS,E|N (s, e|n) n   X n k = u (1 − u)n−k PS,E|K (s, e|k), k k=s Äëÿ òîãî, ÷òîáû ìèíèìèçèðîâàòü ñðåäíåå âðåìÿ ïîäêëþ÷åíèÿ ãðóïïû ñòàíöèé, òî÷êà äîñòóïà äîëæíà â êàæäîì áèêîí-èíòåðâàëå ìàêñèìèçèðîâàòü ñðåäíåå êîëè÷åñòâî óñïåõîâ. Åñëè òî÷êà äîñòóïà îöåíèâàåò êîëè÷åñòâî íåïðèñîåäèíèâøèõñÿ ñòàíöèé êàê Nˆ , âûáîð çíà÷åíèÿ ïîðîãà äîëæåí ïðîèçâîäèòüñÿ ñëåäóþùèì îáðàçîì h i ˆ . unext = arg max E(u) S|N = N (1) u 3.2. Ìàêñèìèçàöèÿ ïðàâäîïîäîáèÿ ñ áåñêîíå÷íîé ïàìÿòüþ Ïðîíóìåðóåì áèêîí-èíòåðâàëû, íà÷èíàÿ ñ íóëÿ. Ïóñòü ut  çíà÷åíèå ïîðîãà, óñòàíîâëåííîå â íà÷àëå áèêîí-èíòåðâàëà t. Ïóñòü òàêæå st è et  íàáëþäàåìûå â áèêîí-èíòåðâàëå t êîëè÷åñòâà óñïåõîâ è ïóñòûõ âèðòóàëüíûõ ñëîòîâ ñîîòâåòñòâåííî. Îñíîâûâàÿñü íà íàáëþäàåìûõ âåëè÷èíàõ òî÷êà äîñòóïà ìîæåò îöåíèâàòü nt  êîëè÷åñòâî íåïîäêëþ÷åííûõ ñòàíöèé ê íà÷àëó t-ãî áèêîí-èíòåðâàëà. Íà ðèñ. 2 è 3 êðèâûå ïîêàçûâàþò ôîðìó çàâèñèìîñòåé ñðåäíåãî êîëè÷åñòâà óñïåõîâ E [S|K] è ïóñòûõ ñëîòîâ E [E|K] îò êîëè÷åñòâà ñòàíöèé, äîïóùåííûõ ê ïðèñîåäèíåíèþ â áèêîí-èíòåðâàëå. Êàê âèäíî, çàâèñèìîñòü E [S|K] ÿâëÿåòñÿ íåìîíîòîííîé, è ïðè íàáëþäåíèè êàêîãî-ëèáî ÷èñëà óñïåõîâ â áèêîíèíòåðâàëå íåëüçÿ îäíîçíà÷íî ñêàçàòü, êàêîå êîëè÷åñòâî ñòàíöèé áûëî äîïóùåíî ê ïðèñîåäèíåíèþ. Äàííîãî íåäîñòàòêà ëèøåíà çàâèñèìîñòü E [E|K]. Ïîýòîìó ìû ïðåäëàãàåì îöåíèâàòü ÷èñëî ñòàíöèé èñõîäÿ èç ñîâìåñòíîãî ðàñïðåäåëåíèÿ ÷èñëà ïóñòûõ è óñïåøíûõ ñëîòîâ. Ïîñêîëüêó â äàííîì ñöåíàðèè ñòàíöèè óáûâàþò ëèøü ïðè ïðèñîåäèíåíèè, ÷èñëî ñòàíöèé nt+1 , íå ïîäêëþ÷èâøèõñÿ ê íà÷àëó áèêîí-èíòåðâàëà t + 1 ìîæíî îöåíèòü, êàê nt+1 = nt − st = nt−1 − st − st−1 = ... = n0 − t X i=0 si . Òîãäà íà øàãå t òî÷êà äîñòóïà ìîæåò îöåíèâàòü íà÷àëüíîå êîëè÷åñòâî ñòàíöèé êàê òî, êîòîðîå ìàêñèìèçèðóåò âåðîÿòíîñòü íàáëþäåíèÿ ïîñëåäîâàòåëüíîñòè (s0, e0), (s1, e1), ...(st, et)   (t) n ˆ 0 = arg max n0 ÈÍÔÎÐÌÀÖÈÎÍÍÛÅ ÏÐÎÖÅÑÑÛ t Y i=0 X  (ui )  si , ei |n0 − PS,E|N sj   . ÒÎÌ 16 j=0 j<i  1 2016  БАНКОВ, ХОРОВ, ЛЯХОВ количество успешных слотов 34 35 p=0 p = 0.1 p = 0.5 p = 0.9 30 25 20 15 10 5 0 0 50 100 150 200 Количество станций, допущенных к подключению Ðèñ. 2. Çàâèñèìîñòü ñðåäíåãî çíà÷åíèÿ ÷èñëà óñïåõîâ â áèêîí-èíòåðâàëå îò êîëè÷åñòâà êîíêóðèðóþùèõ количество пустых слотов ñòàíöèé. 2000 p=0 p = 0.1 p = 0.5 p = 0.9 1800 1600 1400 1200 1000 800 600 400 200 0 0 50 100 150 200 Количество станций, допущенных к подключению Ðèñ. 3. Çàâèñèìîñòü ñðåäíåãî çíà÷åíèÿ ÷èñëà ïóñòûõ ñëîòîâ â áèêîí-èíòåðâàëå îò êîëè÷åñòâà êîíêóðè- ðóþùèõ ñòàíöèé. Èìåÿ äàííóþ îöåíêó, òî÷êà äîñòóïà âûáèðàåò çíà÷åíèå ïîðîãà " (u) ut+1 = arg max E u S|N = (t) n ˆ0 − t X # si . i=0 3.3. Ìàêñèìèçàöèÿ ïðàâäîïîäîáèÿ ñ êîíå÷íîé ïàìÿòüþ Îïèñàííûé â ïðåäûäóùåì ïîäðàçäåëå ïîäõîä îáëàäàåò ñóùåñòâåííûì íåäîñòàòêîì  îí íåïðèìåíèì â ñëó÷àå, êîãäà íîâûå ñòàíöèè ìîãóò ïîÿâëÿòüñÿ è èñ÷åçàòü ïîñëå íóëåâîãî áèêîíèíòåðâàëà. Áîëåå òîãî, îí òðåáóåò õðàíåíèÿ âñåé èñòîðèè ïðèñîåäèíåíèÿ ñòàíöèé è ìàêñèìèçàöèè ïðîèçâåäåíèÿ âåðîÿòíîñòåé (èëè ñóììû èõ ëîãàðèôìîâ) èñõîäîâ â êàæäîì ïðîøåäøåì áèêîí-èíòåðâàëå, ÷òî ïðåäúÿâëÿåò âûñîêèå òðåáîâàíèÿ ê èìåþùèìñÿ ó òî÷êè äîñòóïà âû÷èñëèòåëüíûì ðåñóðñàì è ïàìÿòè. Äëÿ áîðüáû ñ ïåðå÷èñëåííûìè íåäîñòàòêàìè ìîæíî èñïîëüçîâàòü àëãîðèòì, îöåíèâàþùèé êîëè÷åñòâî ñòàíöèé èñõîäÿ èç èíôîðìàöèè çà ïðåäûäóùèå W áèêîí-èíòåðâàëîâ.  òàêîì ñëóÈÍÔÎÐÌÀÖÈÎÍÍÛÅ ÏÐÎÖÅÑÑÛ ÒÎÌ 16  1 2016  ПРИСОЕДИНЕНИЕ УСТРОЙСТВ В СЕТЯХ IEEE 802.11AH 35 ÷àå â áèêîí-èíòåðâàëå t òî÷êà äîñòóïà îöåíèâàåò íå n0, à nt−W +1  t Y n ˆ t−W +1 = arg max nt−W +1 i=t−W +1  (ui )  si , ei |nt−W +1 − PS,E|N  X j=t−W +1 j<i  sj   è, èìåÿ äàííóþ îöåíêó âûáèðàåò çíà÷åíèå ïîðîãà t X " (u) ut+1 = arg max E u S|N = n ˆ t−W +1 − # si . i=t−W +1 Èíòåðåñíûì ïðîñòûì ÷àñòíûì ñëó÷àåì ÿâëÿåòñÿ àëãîðèòì ñ ïàðàìåòðîì W ðàâíûì 1, êîãäà òî÷êà äîñòóïà îöåíèâàåò ÷èñëî ñòàíöèé â íà÷àëå òîëüêî ÷òî ïðîøåäøåãî áèêîí-èíòåðâàëà (u ) t (st , et |nt ) , n ˆ t = arg max PS,E|N nt è âûáèðàåò íîâûé ïîðîã ut+1 = arg max E(u) [S|N = n ˆ t − st ] . u Ïðè âûáîðå çíà÷åíèÿ W âîçíèêàþò íåêîòîðûå ïðîòèâîðå÷èÿ. Ñ îäíîé ñòîðîíû, áîëüøîå çíà÷åíèå ïàðàìåòðà W ïîâûøàåò íàãðóçêó íà âû÷èñëèòåëüíûå ðåñóðñû òî÷êè äîñòóïà è òðåáóåò õðàíèòü áîëüøå äàííûõ. Òàêæå âàæíî òî, ÷òî ïðè áîëüøîì W òî÷êà äîñòóïà ìîæåò îöåíèâàòü ÷èñëî ñòàíöèé ïî óñòàðåâøèì äàííûì â ñëó÷àå, êîãäà ïîÿâèëÿþòñÿ íîâûå ñòàíöèè.  òî æå âðåìÿ áîëüøåå çíà÷åíèå W ñîîòâåòñòâóåò áîëüøåé âûáîðêå, ïî êîòîðîé îöåíèâàåòñÿ ÷èñëî ñòàíöèé, ÷òî äîëæíî ïðèâîäèòü ê áîëüøåé òî÷íîñòè îöåíêè (ïðè óñëîâèè, ÷òî çà ïîñëåäíèå W áèêîí-èíòåðâàëîâ íå ïîÿâëÿëèñü íîâûå ñòàíöèè). 3.4. Àäàïòèâíûé âûáîð ïîðîãà Âûøåïåðå÷èñëåííûå àëãîðèòìû îöåíêè ÷èñëà ñòàíöèé è ïîñëåäóþùåãî âûáîðà ïîðîãà ïîëàãàþòñÿ íà çíàíèå ðàñïðåäåëåíèé PS,E|K ÷èñëà óñïåøíûõ è ïóñòûõ ñëîòîâ ïðè çàäàííîì êîëè÷åñòâå ïîäêëþ÷àþùèõñÿ â áèêîí-èíòåðâàëå ñòàíöèé. Ýòî ÿâëÿåòñÿ íåäîñòàòêîì äàííûõ àëãîðèòìîâ ïî ñëåäóþùèì ïðè÷èíàì. Âî-ïåðâûõ, äëÿ õðàíåíèÿ ðàñïðåäåëåíèé òðåáóåòñÿ çíà÷èòåëüíûé îáú¼ì ïàìÿòè. Âî-âòîðûõ, ðàñïðåäåëåíèÿ îïðåäåëÿþòñÿ ïàðàìåòðàìè áèêîí-èíòåðâàëà è ïàðàìåòðàìè ìåòîäà äîñòóïà ê êàíàëó: ïðè èçìåíåíèè äëèòåëüíîñòè áèêîí-èíòåðâàëà èëè çíà÷åíèé ìèíèìàëüíîãî èëè ìàêñèìàëüíîãî êîíêóðåíòíîãî îêíà, äàííûå ðàñïðåäåëåíèÿ äîëæíû áûòü ïåðåñ÷èòàíû. Â-òðåòüèõ, ïðè íàëè÷èè ñòîðîííåãî øóìà ðàñïðåäåëåíèÿ ñòàíîâÿòñÿ íåàêòóàëüíûìè è äëÿ ïîëó÷åíèÿ íîâûõ ðàñïðåäåëåíèé íåîáõîäèìî ðàçðàáàòûâàòü íîâóþ ìîäåëü ïåðåäà÷è äàííûõ.  äàííîì ðàçäåëå îïèñàí àëãîðèòì âûáîðà ïîðîãà, êîòîðûé íå íóæäàåòñÿ â çíàíèè ðàñïðåäåëåíèÿ PS,E|K , à ëèøü îïèðàåòñÿ íà î÷åâèäíîå ñâîéñòâî ñèñòåì ñî ñëó÷àéíûì äîñòóïîì: ñðåäíåå êîëè÷åñòâî óñïåõîâ â áèêîí-èíòåðâàëå ðàñò¼ò ïðè ïîâûøåíèè êîëè÷åñòâà äîïóùåííûõ ê ïîäêëþ÷åíèþ ñòàíöèé îò 0 äî íåêîòîðîãî íåèçâåñòíîãî çíà÷åíèÿ k∗, à ïðè äàëüíåéøåì ïîâûøåíèè êîëè÷åñòâà ñòàíöèé óáûâàåò. Äàííûé àëãîðèòì èìååò äâà ñîñòîÿíèÿ: è . Âíà÷àëå àëãîðèòì íàõîäèòñÿ â ñîñòîÿíèè .  äàííîì ñîñòîÿíèè àëãîðèòì îöåíèâàåò êîëè÷åñòâî íåïðèñîåäèíèâøèõñÿ ñòàíöèé è êîëè÷åñòâî äîïóùåííûõ ê ïðèñîåäèíåíèþ ñòàíöèé, ïðè êîòîðîì ÷èñëî óñïåøíûõ ñëîòîâ ìàêñèìàëüíî.  ïåðâîì áèêîí-èíòåðâàëå óñòàíàâëèâàåòñÿ ìèíèìàëüíîå çíà÷åíèå ïîðîãà umin = Θ1 , êîòîðîå ãàðàíòèðóåò, ÷òî â áèêîí-èíòåðâàëå áóäåò ïûòàòüñÿ ïîäêëþ÷èòüñÿ îáó÷åíèå îáó÷åíèå ÈÍÔÎÐÌÀÖÈÎÍÍÛÅ ÏÐÎÖÅÑÑÛ ÒÎÌ 16  1 2016 ðàáîòà