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

Формула изобретения

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

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

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

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

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

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

7. Устройство по п.6, отличающееся тем, что множество хранящихся последовательностей включает в себя циклы перемещения и трассы перемещения.

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

9. Устройство по п. 8, отличающееся тем, что средства выбора дополнительно содержат средства для формирования второй количественной меры степени совпадения продолжительности текущей последовательности с продолжительностью каждой из хранящихся последовательностей, причем на основе значений отношения и второй количественной меры выбирается одна из хранящихся последовательностей.

10. Устройство по п.9, отличающееся тем, что средства выбора дополнительно содержат средства для формирования третьей количественной меры степени совпадения частоты текущей последовательности с частотами каждой из хранящихся последовательностей, причем на основе значений отношения, второй количественной меры и третьей количественной меры выбирается одна из хранящихся последовательностей.

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

12. Способ по п.11, отличающийся тем, что количественная мера представляет собой отношение числа положений в текущей последовательности, совпадающих с положениями в хранящейся последовательности, к общему числу положений в текущей последовательности.

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

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

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

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

17. Способ по п.16, отличающийся тем, что на этапе сравнения маркированной последовательности определяют отношение числа положений в маркированной последовательности, совпадающих с положениями в хранящейся последовательности, к общему числу положений в маркированной последовательности.

18. Способ по п.17, отличающийся тем, что на этапе сравнения маркированной последовательности определяют степень совпадения продолжительности маркированной последовательности с продолжительностью каждой из хранящихся последовательностей.

19. Способ по п.18, отличающийся тем, что на этапе сравнения маркированной последовательности определяют степень совпадения частоты маркированной последовательности с частотой каждой из хранящихся последовательностей.

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

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

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

23. Устройство по п.22, отличающееся тем, что вторые средства дополнительно определяют степень совпадения длительности маркированной последовательности с длительностью каждой из хранящихся последовательностей.

24. Устройство по п.23, отличающееся тем, что вторые средства дополнительно определяют степень совпадения частоты маркированной последовательности с частотой каждой из хранящихся последовательностей.

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

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

27. Способ по п. 25, отличающийся тем, что определяют отношение числа положений в маркированной последовательности, совпадающих с положениями в хранящейся последовательности, к общему числу положений в маркированной последовательности.

28. Способ по п.27, отличающийся тем, что определяют степень совпадения длительности маркированной последовательности с длительностью каждой из хранящихся последовательностей.

29. Способ по п.28, отличающийся тем, что определяют степень совпадения частоты маркированной последовательности с частотами каждой из хранящихся последовательностей.

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

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

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

33. Устройство по п.32, отличающееся тем, что средства сравнения и определения выполнены с возможностью определения степени совпадения длительности маркированной последовательности с длительностью каждой из хранящихся последовательностей.

34. Устройство по п.33, отличающееся тем, что средства сравнения и определения выполнены с возможностью определения степени совпадения частоты маркированной последовательности с частотой каждой из хранящихся последовательностей.

35. Сеть связи, отличающаяся тем, что содержит множество серверов, установленных в соответствующих географических районах и объединенных в распределенную файловую систему, мобильное оконечное устройство, оснащенное средствами для связи с сервером, ближайшим к мобильному оконечному устройству, причем средства связи осуществляют доступ к прикладным файлам и файлам с данными, хранящимися в серверах, платформу мобильной распределенной системы (ПМРС), оснащенную средствами для управления распределенной файловой системой серверов и средствами для прогнозирования следующего положения мобильного оконечного устройства, причем средства для управления распределяют по серверам информацию, характеризующую положение и основывающуюся на следующем положении, прогнозируемом средствами прогнозирования.

36. Сеть связи по п.35, отличающаяся тем, что ПМРС включает в себя по меньшей мере один агент ПМРС и по меньшей мере один мобильный плавающий агент (МПА), причем МПА связан с мобильным оконечным устройством, а агент ПМРС обменивается данными и заранее выделяет МПА на по меньшей мере одном сервере для мобильного оконечного устройства на основании следующего положения, прогнозируемого средствами прогнозирования.

37. Сеть связи по п.36, отличающаяся тем, что МПА представляет собой процедуру, выполняемую на сервере, удаленном от мобильного оконечного устройства, которое обменивается данными и заранее устанавливает связь с сервером, близким к мобильной станции, и которое управляет повторным кэшированием данных для агента ПМРС.

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

Описание изобретения к патенту

Область техники

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

Предшествующий уровень техники

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

Вследствие нерегулярного потока телефонных вызовов мобильных оконечных устройств в различных географических районах приемлемой архитектурой перспективных мобильных сетей связи является слоистая или иерархическая сотовая архитектура. В общем случае иерархическая сотовая структура включает ортогональные сотовые слои ячеек различных типов/размеров, покрывающие общий географический район. Иерархическая сотовая структура чаще всего выполняется в виде макроячеек (macrocell), покрывающих микроячейки (microcell) и пикоячейки (picocell), которые различаются пространственной протяженностью и другими характеристиками. Например, пикоячейкой является область, имеющая несколько групп каналов или идентичный код, причем номинальный радиус пикоячейки зачастую не превышает 200 м. Скорость обмена информацией между абонентами, находящимися в пределах пикоячейки, может быть доведена до 2 - 10 Мбит/с, в то время, как порядок скорости обмена в пределах макроячейки составляет 10 - 100 кбит/с.

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

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

Использование кэширования для сокращения времени ожидания и облегчения сетевого трафика основано на свойстве временной локализации запросов к данным в компьютерных программах. Это свойство описано в статье D. Lilja "Согласованность кэшированных данных в больших многопроцессорных системах с общей памятью: результаты и сравнительный анализ", ACM Computing Surveys vol. 25, N 3, p. 303 - 338 (Sept. 1993). Временная локализация означает, что данные, недавно запрашиваемые программой, вероятно вновь будут запрошены в ближайшем будущем. Таким образом, создается местная копия или кэш-память недавно запрашиваемых удаленных данных, с тем, чтобы повторное обращение к тем же самым данным выполнялось при помощи локальной процедуры без перегрузки сетевого трафика. При помощи качественной кэш-памяти обращение к удаленным данным большого объема может выполняться фактически с той же эффективностью, что и обращение к локальным данным.

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

Другим приемлемым для распределенных систем способом, в котором используется априорное знание о тех удаленных данных, которые могут понадобиться, является выборка данных с упреждением. Удаленные данные заранее передаются клиенту, то есть передаются до того, как эти данные действительно будут запрошены. Информация о том, какие данные понадобятся в будущем, может быть получена из анализа предыдущих запросов пользователя. Так, например, в системах с распределенными файлами данных часто заранее загружаются рабочие файловые наборы, причем необходимые файловые наборы определяются на основе анализа особенностей предыдущих обращений клиента к файлам данных. В другом общеизвестном способе предварительной выборки данных используется свойство пространственной локализуемости, которое указывает на большую вероятность того, что в будущем клиенту понадобятся данные, хранящиеся по адресу или на странице, соседними с данными, прочитанными перед этим.

Известен способ определения параметров траектории объекта в реальном масштабе времени, в котором результаты последующих измерений используются для уточнения ранее полученной оценки (Теоретические основы радиолокации. Под ред. В.Е. Дулевича, изд. 2, М: Сов. радио, 1978, с.588-592).

Однако в памяти ЭВМ хранятся лишь текущие оценки параметров траектории с указанием точности оценки.

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

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

Известен способ распределения каналов связи в системах связи, основанный на прогнозировании местоположения подвижного объекта по результатам сравнения статистических данных о его местоположении (координатах) и перемещениях, хранящихся в памяти ЭВМ, с текущими данными (Связь с подвижными объектами в диапазоне СВЧ. Под ред. У.К. Джейкса. Перевод с англ. М: Связь, 1979, с. 463-466).

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

Известный способ не позволяет обеспечить прогнозирование последующего местоположения подвижного объекта с достаточной точностью.

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

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

Раскрытие изобретения

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

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

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

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

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

В соответствии с другой особенностью настоящего изобретения способ выявления систематических составляющих в перемещениях мобильного терминала включает этапы (a) определения того, является ли текущее положение мобильного терминала стационарным состоянием или граничным состоянием; (b) маркировки последовательности положений, содержащей текущее положение, одно из наиболее поздних предшествующих стационарных состояний и наиболее позднее предшествующее граничное состояние, а также предыдущие положения, встретившиеся между одним из наиболее поздних предшествующих стационарных состояний и наиболее поздним предшествующим граничным состоянием; (c) сравнения помеченной последовательности с каждой из множества хранящихся последовательностей положений и определения по меньшей мере одного количественного замера степени совпадения помеченной последовательности с каждой из хранящихся последовательностей; а также (d) увеличения показателя приоритетности соответствующей хранящейся последовательности на заданную величину при условии, что по крайней мере один из количественных замеров достигает заданного уровня.

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

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

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

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

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

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

Краткое описание чертежей

В дальнейшем изобретение поясняется описанием вариантов его выполнения со ссылками на сопровождающие чертежи, в числе которых:

фиг. 1 изображает пример иерархической многослойной сотовой системы;

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

фиг. 3 - схему перемещения мобильного абонента в иерархической сети связи;

фиг. 4 - устройство прогнозирования перемещений мобильного абонента (УППМА), выполненное в соответствии с настоящим изобретением;

фиг. 5 - схему перемещения пользователя по различным состояниям, сгруппированным в циклы перемещений;

фиг. 6 - схему объединения состояний в трассы перемещения;

фиг. 7 - схему функционирования детектора диаграммы перемещений и информационных структур, формируемых в базе данных диаграмм перемещений;

фиг. 8 - блок-схему способа выявления циклов перемещения в соответствии с настоящим изобретением;

фиг. 9 - блок-схему способа выявления трасс перемещения в соответствии с настоящим изобретением;

фиг. 10 - схему работы устройства прогнозирования перемещений;

фиг. 11 - схему древовидной структуры способа прогнозирования перемещений;

фиг. 12 - вариант схемы перемещений пользователя по различным состояниям с течением времени;

фиг. 13a, 13b - пример структурных ограничений, используемых в процессе сравнения совпадений;

фиг. 14 - блок-схему устройства прогнозирования положения мобильного абонента в соответствии с настоящим изобретением;

фиг. 15 - пример нормированных результатов имитации устройства прогнозирования перемещений мобильного абонента, выполненного в соответствии с настоящим изобретением;

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

Лучший вариант осуществления изобретения

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

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

На фиг. 1 показана примерная иерархическая многослойная сотовая система. Зонтичная макроячейка 10, выполненная в виде восьмиугольника, входит в сотовую структуру более высокого уровня. Каждая зонтичная ячейка может иметь структуру микроячеек более низкого уровня. Зонтичная ячейка 10 содержит микроячейку 20, характеризующуюся районом, очерченным пунктирной линией, и микроячейку 30, заданную районом, также очерченным пунктирной линией, причем обе микроячейки расположены вдоль городских улиц, а также пикоячейки 40, 50 и 60, которые покрывают отдельные этажи высотного здания. Пересечение двух городских улиц, покрываемое микроячейками 20 и 30, может являться районом с напряженным трафиком и, следовательно, может характеризоваться как "горячая точка".

На фиг. 2 показана структурная схема примерной мобильной сотовой радиотелефонной системы, включающей примерные базовую станцию 110 и мобильную станцию 120. Базовая станция содержит блок управления и обработки 130, подключенный к мобильному коммутационному центру (МКЦ) 140, который в свою очередь подключен к телефонной сети общего пользования (ТСОП) (не показана). Основные особенности подобной сотовой радиотелефонной системы хорошо известны на практике и раскрыты, например, в американском патенте No 5175867 Wejke и др., озаглавленном "Переключение каналов через смежные ячейки в сотовой системе связи", а также в заявке на американский патент No 07/967027, озаглавленной "Мультирежимная обработка сигналов", поданной 27 октября 1992 г. , причем как патент, так и заявка присоединяются по ссылке.

Базовая станция обслуживает множество речевых каналов при помощи приемопередатчика голосовых каналов 150, управление которым осуществляется посредством блока управления и обработки 130. Кроме того, каждая базовая станция содержит приемопередатчик канала управления 160, который может обслуживать более одного канала управления. Приемопередатчик канала управления 160 управляется также при помощи блока управления и обработки 130. Приемопередатчик канала управления 160 по каналу управления базовой станции или ячейки в широковещательном режиме передает управляющую информацию мобильным терминалам, настроенным на данный канал управления. Ясно, что приемопередатчики 150 и 160 могут быть выполнены в виде одного устройства, подобного приемопередатчику голосовой и управляющей информации 170, предназначенного для использования совместно с цифровыми каналами передачи управляющей информации и цифровыми каналами радиообмена, использующими единую несущую частоту.

Мобильная станция 120 принимает информацию, передаваемую в широковещательном режиме по каналу управления, при помощи своего приемопередатчика голосовой и управляющей информации 170. Затем блок обработки 180 оценивает информацию, принятую по каналу управления, которая содержит характеристики ячеек, с которыми возможно соединение мобильной станции, и определяет, к какой ячейке необходимо подключиться. В предпочтительном варианте информация, принимаемая по каналу управления, не только включает абсолютную информацию, относящуюся к ячейке, с которой он связан, но также содержит и относительную информацию о ячейках, примыкающих к ячейке, с которой связан канал управления, как это описано в американском патенте N 5353332 Raith и др., озаглавленном "Способ и устройство для управления связью в радиотелефонной системе", который присоединяется к настоящей заявке по ссылке.

Примерная диаграмма перемещений мобильного терминала показана на фиг. 3. Мобильный пользователь A движется по району, покрываемому иерархической сотовой архитектурой, включающей систему пикоячейки со скоростью обмена 2 Мбит/с и систему макроячейки, например систему GSM, со скоростью обмена 9.6 кбит/с. Пользователь A попадает в одну из покрытых пикоячейкой областей через вход D и в течение некоторого времени движется в пределах области, покрываемой этой ячейкой (эта область может находиться в пределах здания). Пользователь A входит в комнату L, конференц-зал C, а затем через вход D покидает область, покрываемую первой пикоячейкой, попадая в область, покрываемую макроячейкой, как это показано на фиг. 3. Абонент A движется по области, покрываемой макроячейкой, к области, покрываемой другой пикоячейкой, в которую он входит через другой вход В и перемещается в пределах этой области.

В соответствии с одной особенностью настоящего изобретения перемещения пользователя A должны быть зарегистрированы, как это происходит в устройстве прогнозирования перемещений мобильного абонента (УППМА) в мобильном терминале пользователя A или в сети связи. Когда пользователь A движется с определенной скоростью в точку М из комнаты C или комнаты L, УППМА должно указывать на высокую вероятность того, что пользователь A покинет район, покрываемый пикоячейкой с высокой скоростью обмена информацией. УППМА должно информировать другие системы и приложения с тем, чтобы они при необходимости предприняли необходимые действия, такие как динамическое распределение каналов или заблаговременная загрузка информации, до того, как пользователь A покинет район.

Как показано на фиг. 4, УППМА, выполненное в соответствии с настоящим изобретением, включает детектор диаграмм перемещения (ДДП, IPD, itinerary pattern detector) и базу данных диаграмм перемещения (БДДП, IPB, itinerary pattern database), а также предсказатель перемещений (ПП, МР, motion pridictor). ДДП используется для выявления регулярных диаграмм перемещений (ДП, IPS, itinerary patterns), отмечающихся в процессе перемещений пользователя между разными местоположениями или состояниями, а также для записи ДП в базу данных диаграмм перемещений (БДДП.). В общем случае БДДП включает также определенную информацию, относящуюся к строению или физической структуре системы связи, как это будет подробно описано ниже. ПП использует информацию о диаграммах перемещения, хранящуюся в БДДП, для прогнозирования следующего положения или состояния пользователя. ПП также сравнивает предсказанное состояние с действительным следующим состоянием пользователя и обновляет ДП, хранящиеся в БДДП.

Исходными данными, подаваемыми в УППМА, являются ОИ (lAs) или состояния, в которых находится мобильный абонент, при этом считается, что система непрерывно отслеживает новое состояние абонента на заданном промежутке времени, например 1-5 секунд. Ясно, что ОИ указывают на положение мобильного абонента, т. е. ячейки, в которых абонент находился и находится. Таким образом, ОИ могут представляться в любом приемлемом виде, типа номеров кодов в системе многостанционного доступа с кодовым разделением (МДКР), или положений ячеек в системе многостанционного доступа с временным разделением (МДВР), подобной используемой в Европе системе GSM или используемой в Северной Америке системе AMPS. Диаграммы перемещений или последовательности ОИ запоминаются в БДДП, к которой имеет доступ предсказатель перемещений ПП.

Для корреляционного анализа ЦП (MCs) или ТП (MTs) используются схемы сравнения трех типов. Сравнение первого типа или сравнение состояний указывает степень совпадения последовательности состояний с другой последовательностью состояний той же длины; это позволяет вычислять первый коэффициент совпадения, что подробно описывается ниже. Сравнение второго типа, или сравнение скоростей, или временное сравнение указывает на степень совпадения длительности последовательности состояний с длительностью другой последовательности состояний той же длины; на основе этого, в соответствии с описанной ниже процедурой, вычисляется второй коэффициент совпадения. Сравнение третьего типа урезывает на степень совпадения частоты последовательности состояний с частотой другой последовательности состояний той же длины; это позволяет вычислять третий коэффициент совпадения, как будет описано ниже.

Перед подробным описанием настоящего изобретения необходимо привести следующие вспомогательные определения и аббревиатуры.

Граничный ЦП: цикл перемещения, в котором по меньшей мере одно состояние является граничным состоянием; ГЦП имеет более высокий приоритет, чем ЦП, причем параметр граничного приоритета равняется .

Граничная ТП: трасса перемещения, в которой по крайней мере одно состояние является граничным состоянием; ГТП является более приоритетной, чем ТП, причем параметр граничного приоритета равняется .

Граничное состояние: состояние на границе сотового слоя.

ПВПВ: "первым вошел - первым вышел".

Разветвленное состояние: объединенное состояние, для которого последующие состояния находятся в различимых циклах перемещения.

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

База данных диаграмм перемещения: информационная база данных, максимальное число диаграмм перемещения, хранящихся в которой, составляет М.

Объединенное состояние: состояние, содержащееся по крайней мере в двух различимых циклах перемещения.

НДИ: наиболее давно использовавшийся.

Цикл перемещения: цикл, имеющий n (где n > 1) последовательных состояний, включающий по меньшей мере одно стационарное состояние.

Трасса перемещения: трасса, которая начинается и заканчивается стационарными состояниями или граничными состояниями.

Состояние указателя: состояние в списке состояний, которое содержит указатель, указывающий на ЦП или ТП, сохраненные в БДДП.

: показатель приоритетности, указывающий на приоритет ЦП или ТП.

Состояние: положение пользователя, т.е. область идентичности ОИ на диаграмме перемещения (или графе движения), где C_k.t указывает на состояние k в момент времени t (текущее время).

Список состояний: список состояний, в котором состояния хранятся в порядке времени поступления.

Стационарное состояние: состояние (ОИ), в котором мобильный терминал остается по меньшей мере на протяжении времени .

Т_цп: период ЦП, заданный разностью t_n-t_i, характеризующей временной интервал между первым и последним состояниями в ЦП.

Переходное состояние: состояние, в котором мобильный терминал остается в течение времени, меньшем интервала .

_b: временной критерий для выявления ГС.

_s: временной критерий для выявления СтС.

В соответствии с настоящей заявкой на изобретение ДДП основывается на двух основных процедурах: модели циклов перемещения (ЦП) и модели трасс перемещения (ТП). Модель ЦП описывает долговременные систематические перемещения пользователя, которые, как считается, имеют вид замкнутых петель или циклов состояний. Модель ТП описывает определенные перемещения, которые, как полагается, имеют вид линейных маршрутов состояний.

Модель ЦП основывается на предположении о том, что при перемещении пользователя из определенного состояния велика вероятность того, что пользователь вернется в то же состояние. Таким образом, движения пользователя мобильного терминала моделируются как различные циклообразные диаграммы, примеры которых приведены на фиг. 5. Состояния, описываемые циклами, обозначены номерами 1-27, 29-35, которые указывают области идентичности ОИ, соответствующие состояниям. Из чертежа видно, что ЦП является замкнутой петлей или "циклом" состояний, имеющим продолжительность Т_цп и содержащим по меньшей мере два состояния и по меньшей мере одно стационарное состояние. УППМА, выполненное в соответствии с настоящим изобретением, выявляет стационарное состояние по следующему критерию: если сигнал ОИ (входное состояние), поданный в УППМА, не меняется на протяжении заданного интервала времени _s (например, _s 5 мин ), то состояние C_k.t является стационарным.

С другой стороны, каждый цикл перемещения представляет собой последовательность состояний, например [1, 16, 17, 18, 21, 20, 19, 18, 1]. Очевидно, что при рассмотрении цикла перемещения определяется и направление обхода, так как порядок состояний в последовательности отличается для различных направлений. Кроме того, с каждым ЦП связаны НДИ показатель приоритетности , который указывает приоритетность ЦП по отношению к другим ЦП в БДЦП, параметр частоты F, указывающий частоту последовательности состояний (см. фиг. 12), а также параметр граничного приоритета , причем каждый из этих параметров для всякого нового ЦП устанавливается равным нулю. "Новый" ЦП выявляется путем сравнения приходящего ЦП с каждым из ЦП, хранящихся в БДДП. Если для нового ЦП коэффициент совпадения первого типа , который далее будет описан более подробно, совпадает с коэффициентом одного из хранящихся ЦП, то показатель приоритетности хранящегося ЦП увеличивается на 1. В противном случае новый ЦП записывается в БДДП с начальными значениями = F = = 0. Если одно или несколько состояний в ЦП являются граничными состояниями, то этот ЦП обозначается как граничный ЦП, и его параметр граничного приоритета увеличивается на 1.

УППМА, выполненное в соответствии с заявкой на изобретение, определяет, является ли входное состояние граничным состоянием, на основе одного из следующих критериев: либо (1), если на протяжении заданного интервала времени _b (например, _b 5 мин ) не было получено входных сигналов ОИ, то состояние является граничным состоянием; либо (2), если на протяжении заданного интервала времени _b (например, _b 5 мин ) не было получено входных сигналов ОИ, а был получен сигнал новой ОИ (состояние C_k+1.t), то состояние C_k+1.t является граничным состоянием.

С использованием модели ТП БДДП формирует трассы перемещения, каждая из которых начинается и оканчивается стационарным состоянием или граничным состоянием. При этом замкнутые петли состояний не требуются, и модель ТП является более свободной моделью ЦП. На фиг. 6 приведены шесть примеров ТП, полученных из ЦП, приведенных на фиг. 5, причем необходимо отметить, что каждый ЦП включает по меньшей мере одну ТП.

Подобно ЦП при рассмотрении трассы перемещения необходимо определять направление перемещения, так как порядок состояний различается для разных направлений. Кроме того, с каждой ТП связан НДИ показатель приоритетности , указывающий приоритет ТП по сравнению с другими ТП, параметр частоты F и граничный параметр приоритета , причем все эти параметры для новой ТП устанавливаются равными нулю. "Новая" ТП выявляется путем сравнения приходящей ТП с каждой из ТП, хранящихся в БДДП. Если для новой ТП индекс совпадения первого типа , подробно описанный ниже, совпадает с индексом одной из хранящихся ТП, то показатель приоритетности хранящейся ТП увеличивается на 1. В противном случае новая ТП запоминается в БДДП с начальными значениями параметров = F = = 0. Если одно или несколько состояний в ТП являются граничными состояниями, то эта ТП обозначается как граничная ТП, и ее параметр граничного приоритета увеличивается на 1.

Функционирование БДДП и структуры данных, формируемые БДДП, далее подробно раскрываются со ссылками на фиг. 7, на которой один цикл перемещения ЦП1 содержит три трассы перемещения ТП1, ТП2, ТП3, хранящиеся в БДДП в порядке "наиболее давно использовавшейся" (НДИ). На фиг. 7 показан также список состояний СС, содержащий N последних состояний, поступивших в УППМА, хранящиеся в порядке "первым вошел - первым вышел" (ПВПВ) (на чертеже чтение осуществляется слева направо). Стрелки показывают, как БДДП преобразует последовательность состояний в списке состояний в ТП, хранящиеся в БДДП (которые не соответствуют фиг. 5 и фиг. 6). Надпись "Огр: 1/8, стена, улица, шоссе и т. п." означает примеры структурно ограниченных состояний, которые обуславливаются физической структурой системы связи, что будет более подробно описано ниже. Ясно, что БДДП и СС могут быть реализованы самым различным образом при помощи различных известных на практике электронных запоминающих устройств.

Способ выявления ЦП (ВЦП).

При формировании диаграмм перемещения на основе модели ЦП, исходя из состояний в списке состояний, УППМА выполняет способ выявления циклов перемещения (ВЦП), включающий этапы, проиллюстрированные со ссылками на блок-схему, представленную на фиг. 8. ВЦП и способы в соответствии с настоящим изобретением описываются с использованием псевдокода языка программирования "С", при помощи которого эти способы могут быть легко реализованы на аппаратном оборудовании и в математическом обеспечении любой мобильной станции, базовой станции, мобильного коммутационного центра сотовой системы радиотелефонной связи.

Пусть N - максимальное число состояний в списке состояний СС; пусть ЦП_j - j-ой ЦП; а также пусть другие обозначения соответствуют введенным выше аббревиатурам. Заполним список из k состояний (1 k N) в порядке ПВПВ, причем в БДДП номер j замещаемых ЦП (где 1 k М) замещается в порядке НДИ в соответствии со следующими этапами.

Начало

1) Если C_k.t является стационарным состоянием или граничным состоянием,

если для i=K-L до 1, если любое C_i.t= =C_k.t (для любого t и для k-i > L) и C_i.t является СтС или ГС, то пометить последовательность состояний [C_i.t-t1, C_i+1.t-t2,...,C_k.t] как новый ЦП,

Конец_если;

Иначе перейти в Конец;

Конец_если;

2) Если любое состояние в новом ЦП является граничным состоянием, то пометить новый ЦП как "граничный приоритет" с параметром граничного приоритета = +1;

Конец_если;

3) Сравнить каждый новый ЦП с каждым из ЦП, хранящихся в БДДП,

Если ₁ (совпадение), то увеличить показатель приоритетности хранящегося ЦП на 1 и вычислить параметр частоты F хранящегося ЦП;

Иначе

Если ₂ < ₁ (частичное совпадение), то пометить последнее из совпадавших состояний как "разветвленное состояние" в обоих ЦП;

Конец_если;

Сохранить новый ЦП в БДДП в порядке замещения НДИ;

Конец_если;

Удалить последовательность [C_i.t-t1, C_i+1.t-t2,... C_k.t] из списка состояний;

Конец.

В приведенном выше алгоритме ₁ и ₂ - номера, такие, что 0 ₂ < ₁ 1; СтС - стационарные состояния; ГС - граничные состояния; L-1,2,3,. длина (измеряемая в числе состояний) наиболее короткого ЦП, хранящегося в БДДП; а - коэффициент совпадения первого типа. Параметр ₁ представляет собой доверительный порог, устанавливаемый в соответствии с точностными требованиями или требуемой доверительной вероятностью; обычно ₁ устанавливается равным 0.95, 0.975, 0.99 и т.п. Параметр ₂ представляет собой коэффициент частичного совпадения, который характеризует степень совпадения двух последовательностей состояний, так что ₂ = 0.3, 0.4, 0.5. соответствует 70%, 60%, 50%... совпадения состояний; считается, что ₂ должно устанавливаться равным по меньшей мере 0.5, так как представляющие интерес результаты получаются только при совпадении по меньшей мере половины состояний двух последовательностей.

Коэффициент совпадения первого типа является показателем степени совпадения первой последовательности состояний со второй последовательностью состояний той же длины (сравнение состояний). Коэффициент вычисляется с использованием следующего выражения:



где m_s - число совпавших состояний в последовательностях, N_s - общее число состояний в последовательностях.

Способ выявления ТП (ВТП).

При формировании диаграмм перемещения на основе модели ТП БДДП выполняет способ выявления циклов перемещения (ВЦП), включающий этапы, проиллюстрированные со ссылками на блок-схему, представленную на фиг. 9.

Пусть TП_j - j-ая ТП; пусть М - максимальный номер ТП в БДДП; а также пусть другие обозначения соответствуют введенным выше аббревиатурам. Заполним список из k состояний (1 k N) в порядке ПВПВ, причем в БДДП номер j замещаемых ТП (где 1 <j М) замещается в порядке НДИ в соответствии со следующими этапами.

Начало

1) Если C_k.t является стационарным состоянием или граничным состоянием,

если для i=K-L до 1, если C_i.t является СтС или ГС (для любого t и для k-1 > L), то пометить последовательность состояний [C_i.t-t1, C_i+1.t-t2,..., C_k.t как новую ТП;

Конец_если;

Иначе перейти в Конец;

Конец_если;

2) Если любое состояние в новой ТП является граничным состоянием, то пометить новую ТП как "граничный приоритет" с параметром граничного приоритета = +1;

Конец_если;

3) Сравнить каждую новую ТП с каждой из ранее записанных ТП,

Если ₁ (совпадение), то увеличить показатель приоритетности хранящейся ТП на 1 и вычислить параметр частоты F хранящейся ТП;

Иначе

Если ₂ < ₁ (частичное совпадение), то пометить последнее из совпадавших состояний как "разветвленное состояние" в обеих ТП;

Конец_если;

Сохранить новую ТП в БДДП в порядке замещения НДИ;

Конец_если;

Заменить новую записанную ТП на СУ в списке состояний;

Конец.

В приведенном выше алгоритме - коэффициент совпадения первого типа; ₂ и ₁ - номера такие, что 0 ₂ < ₁ 1; ПмС - помеченное состояние; L= 1,2,3, . . . минимальная длина (измеряемая в числе состояний) ТП. Необходимо отметить, что использование состояния указателя вместо другого состояния является предпочтительным, так как позволяет избежать повторений.

Предсказатель перемещений.

Предсказатель перемещений ПП, включенный в УППМА в соответствии с настоящим изобретением, формирует прогнозы следующего состояния циклов перемещения или трасс перемещения при помощи регрессионного и корреляционного сравнения текущих перемещений с ДП, хранящимися в БДДП. В общем случае выходная информация БС_вых, выдаваемая ПП, представляет собой будущее состояние или последовательность будущих состояний.

На фиг. 10 показаны действия ПП, который включает средства сравнения входных состояний, подаваемых в УППМА с прогнозируемыми состояниями, формируемыми УППМА, а также средства для сравнения входных состояний с ДП, хранящимися в БДДП, и для формирования прогнозов. Если схема сравнения показывает, что прогноз верный, т.е., что текущее входное состояние совпадает с предсказанным состоянием, то прогноз выдается в качестве выходной информации УППМА. Если схема сравнения показывает, что текущее входное состояние не совпадает с прогнозом, или при инициализации УППМА, то процесс предсказания перемещения повторяется для формирования следующего прогноза.

Если входное состояние не совпадает с соответствующим предсказанным состоянием, то последовательность входных состояний, начиная с последнего стационарного или граничного состояния, сравнивается при помощи ПП с каждым из ЦП и ТП, хранящихся в БДДП. Это процесс сравнения выявляет наиболее подходящую хранящуюся диаграмму движения, которая после этого выдается с выхода предсказателя перемещений. Способ прогнозирования перемещений, включающий приведенные ниже этапы, преимущественно выполняется в виде дерева, как это показано на фиг. 11.

Способ прогнозирования перемещений (СПП).

Пусть C_k.t - состояние k в момент времени t и пусть n > 0, t_i > 0, а М - максимальный номер ТП и ЦП в БДДП. Заполним список из k состояний (1 k N) в порядке ПВПВ, причем в БДДП номер j замещаемых ТП и ЦП (где 1 j M) замещается в порядке НДИ в соответствии со следующими этапами. Также будем считать, что БС_вых - [0] или БС_вых [0], а C_k.t не совпадает с первым состоянием в БС_вых.

Начало

1) Для каждого нового приходящего состояния C_k.t сравнить новую последовательность [C_k-n.t-tn, C_k-n.t-tn+1,... C_k.tl с каждым ЦП и ТП, хранящимися в БДДП, (где C_k-n.t-tn - последнее СтС или ГС, а n > 0);

2) Использование сравнения первого типа ():

Если только один хранящийся ЦП или ТП удовлетворяет требованию - сравнения с новой последовательностью ( ₁), тогда БС_вых = [C_k+1.t+t1, C_k+2.t+t2, . ., C_k+m.t+tm]. Для совпавшего ЦП или ТП, (m > 0); перейти в Конец;

Иначе Если ни одно из хранящихся ЦП или ТП не имеет , совпадающее с новой последовательности, тогда

БС_вых = Ц_вых;

Перейти в Конец;

Иначе использовать сравнение второго типа ();

Конец_если;

3) Использование сравнения второго типа ():

Для всех хранящихся ЦП или ТП c , совпадающим по - критерию с новой последовательностью ( ₁), (объединенные состояния). Если только один хранящийся ЦП или ТП удовлетворяет требованию - сравнения с новой последовательностью ( ₃), тогда БС_вых = [C_k+1.t+t1, C_k+2.t+t2,..., C_k+m,t+tm] для совпавшего ЦП или ТП, (m > 0); перейти в Конец;

Иначе Если ни одно из хранящихся ЦП или ТП не имеет , совпадающее с новой последовательности, тогда отыскать одно ограниченное в перемещениях состояние, которое по - и - критериям лучше всего совпадает с новой последовательностью; перейти в Конец;

Иначе использовать сравнение третьего типа (Ф);

Конец_если;

4) Использование сравнения третьего типа (Ф):

Для всех хранящихся ЦП или ТП, удовлетворяющих - и - критериям (объединенные состояния). Если только один хранящийся ЦП или ТП удовлетворяет требованию Ф-сравнения, тогда БС_вых = [C_k+1.t+t1, C_k+2.t+t2, ..., C_k+m.t+tm] для совпавшего ЦП или ТП, (m > 0); перейти в Конец;

Иначе Если ни одно из хранящихся ЦП или ТП не имеет F, совпадающего с F новой последовательности ( ₄), тогда отыскать одно ограниченное в перемещениях состояние, которое по -, - Ф-критериям лучше всего совпадает с новой последовательностью; перейти в Конец;

Иначе (более одной хранящейся ЦП или ТП имеет F, совпадающее с F новой последовательности ( ₄)), отыскать одно из ограниченных в перемещениях состояний с наибольшей суммой +,

Конец_если;

Конец.

В приведенном выше алгоритме - коэффициент совпадения первого типа, - коэффициент совпадения второго типа, Ф - коэффициент совпадения третьего типа, а остальные обозначения соответствуют введенным выше аббревиатурам. Кроме того, в приведенной выше процедуре условие ₃ соответствует выполнению - критерия, а условие ₄ соответствует выполнению Ф-критерия, где ₃ и ₄ - доверительные пороги, относящиеся к критериям сравнения второго и третьего типа, в соответствии с которыми сравниваются скорости или частоты двух последовательностей состояний. Так как скорость или частота мобильного пользователя в большинстве случаев меняются значительно более часто, то значения параметров ₃ и ₄ не должны быть ограничены настолько, насколько это требуется для параметров ₁ и ₂. Таким образом, значения ₃ и ₄ могут быть 0.1, 0.05, 0.025, 0.005,..., в зависимости от точностных требований или требуемой доверительной вероятности; обычно ₃ и ₄ принимаются равными 0.05 для обеспечения доверительной вероятности 95%.

Коэффициент сравнения второго типа указывает на степень совпадения продолжительности (скорости) первой последовательности состояний с продолжительностью (скоростью) второй последовательности состояний той же длины (сравнение по скорости или временное сравнение). Коэффициент определяется из следующего выражения:



где (t_i+1 - t_i)₁ - временной интервал между состоянием i и состоянием i+1 в первой последовательности; (t_i+1 - y_i)₂ - временной интервал между состоянием i и состоянием i+1 во второй последовательности; _ - оператор вычитания по модулю, где модуль 24 используется для временных интервалов, измеряемых в часах, а модуль 60 - для интервалов, измеряемых в минутах; - оператор сложения по модулю, где модуль 24 используется для временных интервалов, измеряемых в часах, а модуль 60 - для интервалов, измеряемых в минутах.

Коэффициент сравнения третьего типа Ф указывает на степень совпадения частоты первой последовательности состояний с частотой второй последовательности состояний той же длины (сравнение по частоте или периоду). На фиг. 12 показано, как вычисляется коэффициент совпадения третьего типа Ф для пользователя, движущегося через различные состояния (показаны по вертикальной оси) с течением времени (показано по горизонтальной оси). Шесть циклов перемещения, обозначенные на фиг. 12, могут быть интерпретированы как повторные возвраты к различным частотам F₁, F₂, где F₁ - частота, использующаяся на двух и более продолжительных циклах перемещения, a F₂ - частота, используемая на четырех более коротких циклах перемещения.

Частоты F_k ЦП или ТП вычисляются в соответствии со следующим выражением:



где n = +1.

Частота F_k" новой поступающей последовательности состояний, как видно из фиг. 12, вычисляется из выражения:



Таким образом, коэффициент совпадения третьего типа Ф определяется в соответствии с выражением:



где Ф_k = 0 указывает на точное совпадение. Далее будет понятно, что коэффициент совпадения третьего типа Ф вычисляется из следующего выражения:



где F₁ - частота первой сравниваемой последовательности, F₂ - частота второй сравниваемой последовательности.

Как видно из фиг. 11, если только один ЦП или ТП удовлетворяет - критерию сравнения с поступившей последовательностью ( ₁), то эта одна последовательность выдается в качестве прогноза УППМА. Если более одного ЦП или ТП удовлетворяют - критерию, то проводится сравнение с использованием второго критерия. Если только один хранящийся ЦП или ТП удовлетворяет - критерию сравнения с поступившей последовательностью ( > ₃), то эта одна последовательность выдается в качестве прогноза УППМА. Если более одного ЦП или ТП удовлетворяют - критерию, то проводится сравнение с использованием третьего критерия. Если только один хранящийся ЦП или ТП имеет значение F, которое совпадает со значением F приходящей последовательности, то эта одна последовательность выдается в качестве прогноза УППМА. Если совпадающее значение F имеют более одного ЦП или ТП, то в качестве прогноза УППМА выдается последовательность, имеющая состояние со структурными ограничениями с наибольшим показателем приоритетности .

Состояния со структурными ограничениями, используемые в процедурах сравнения, вытекают из физической структуры системы связи, которая априорно известна в системе. Если УППМА устанавливается на мобильной станции, то информация об этой физической структуре может быть передана на мобильную станцию посредством дополнительных сообщений, передаваемых по каналу управления. Базис состояний с ограниченными перемещениями показан на фиг. 13a и фиг. 13b.

Как показано на фиг. 13a, мобильный пользователь, находящийся в заданной ячейке, например ячейке 0, может перемещаться в одну из шести прилегающих ячеек в той же самой плоскости, а также в примыкающие ячейки, находящиеся выше или ниже этой плоскости; таким образом, при отсутствии иной информации переход в каждую из этих восьми ячеек может быть осуществлен с вероятностью 1/8 при условии, что пользователь случайно и равновероятно движется во всех направлениях. На фиг. 13b показана физическая конструкция, в которой дверь находится на одном конце коридора, примыкающего к другому коридору. Системе связи априорно известно, что мобильный пользователь, находящийся в одном из коридоров, не может пройти сквозь стены и попасть в одну из других ячеек. Эта информация может быть использована для выявления состояний с ограниченным пространственным перемещением.

Далее приводится псевдокод обобщенной процедуры, выполняемой устройством прогнозирования перемещения мобильного абонента УППМА в соответствии с настоящим изобретением, проиллюстрированной также при помощи блок-схемы на фиг. 14.

Начало

1) Если приходящее C_k.t является новым состоянием, ТО

Выполнить шаги 2), 3), 4). Иначе Выполнить шаги 5), 6), 7), 8),

Конец_если;

2) Для каждого нового приходящего C_k.t продолжать список из k состояний (где 1 k N) в порядке ПВПВ и пометить C_k.t как "граничное состояние" на основе критерия;

3) Если длина БС_вых больше единичного и C_k.t совпадает по - критерию с первым состоянием БС_вых, то БС_вых = БС_вых - C_k.t; Перейти на шаг 9);

Конец_если;

4) Выполнить способ прогнозирования перемещений (СПП);

5) Если С_k.t = = C_k.t-t (для _s), пометить C_k.t как "стационарное состояние" на основе критерия;

Конец_если;

6) Выполнить способ выявления трасс перемещения (ВТП);

7) Выполнить способ выявления циклов перемещения (ВЦП);

8) В БДДП держать j ЦП+ТП в порядке НДИ, где (0 j М);

9) Повторить, начиная с шага 1);

Конец.

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

Работа предложенного в настоящем изобретении УППМА имитировалась, и результаты имитации далее рассматриваются со ссылками на фиг. 15, где приведен пример нормированных результатов имитации предложенного в изобретении УППМА, в котором число состояний равнялось 100, длина списка состояний 500, размер БДДП 500, а _o равнялось 0.05. Работа УППМА имитировалась на протяжении пяти недель.

На фиг. 15 показано соотношение между степенью прогнозируемости СП и коэффициентом случайности. Коэффициент случайности характеризует долю перемещений, обусловленных чистой случайностью; единичный коэффициент случайности означает, что отдельные перемещения или переходы между состояниями являются полностью случайными. Степень прогнозируемости является отношением числа правильно предсказанных состояний к общему числу входных состояний; единичная степень прогнозируемости означает, что каждый из прогнозов УППМА является правильным.

На фиг. 15 "оптимальная зависимость" соответствует предполагаемому наилучшему (теоретическому) результату, т.е. если коэффициент систематичности в перемещениях (т. е. коэффициент, с которым коэффициент случайности связан выражением 1-Х) составляет X, то степень предсказуемости равняется X.

Из фиг. 15 видно, что диаграмма, полученная в результате имитации работы УППМА, хорошо повторяет оптимальную зависимость; пунктирная линия на фиг. 15 является линейной зависимостью, аппроксимирующей результаты имитации по методу наименьших квадратов. В результате имитации работы УППМА получено, что эффективность прогнозирования, равная отношению степени предсказуемости к коэффициенту систематичности, составляет около 95%.

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

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

= _oKДП,

где _o - неотрегулированная плотность Пуассоновского распределения. Коэффициент дневной подвижности КДП принимал одно из трех значений в зависимости от имитируемого времени суток: КДП = 2 для времени 20.00 - 06.00; КДП = 4 для времени 08.30 - 16.00 и КДП = 8 для времени между 06.00 - 08.30 и 16.00 - 20.00. Считалось, что такое изменение коэффициента подвижности достаточно точно аппроксимирует изменение реальных условий.

Предложенное в заявке устройство прогнозирования перемещения мобильного абонента может быть использовано в схеме управления связью при энергичных перемещениях мобильного абонента, которая может быть названа управлением связью с прогнозированием перемещений абонента. На основе ранее полученных диаграмм перемещения пользователя УППМА прогнозирует его будущее положение, благодаря чему данные и/или услуги связи заблаговременно подключаются и/или заблаговременно выделяются в предсказанное положение еще до того, как пользователь там окажется. При этом данные и/или услуги связи в прогнозируемом районе будут выделяться абоненту практически с той же эффективностью, что и в предшествующем его местоположении.

Для более тесного распределения ресурсов и услуг связи, т.е. для обеспечения мобильности обслуживания и выделения ресурсов в беспроводной системе передачи данных, предложенное в изобретении УППМА, должно быть использовано в мобильном плавающем агенте (Mobile Floating Agent, MFA, МПА) и агенте платформы мобильной распределенной системы (Mobile Distributed System Platform Agent, MDSPA, АПМРС). Мобильность обслуживания определяется как мобильность различной служебной логики в опорной (underlying) сети, направленная на повышение качества обслуживания запросов мобильных пользователей. Мобильность ресурсов определяется как мобильность выделения в опорной сети таких ресурсов, как системные данные/программы, пользовательские данные, пользовательские программы и т.п., направленная на повышение качества обслуживания запросов мобильных пользователей. Управление мобильностью, вытекающее из мобильности пользователя и терминала, требуется для обеспечения мобильности ресурсов и услуг связи.

Для эффективного обеспечения мобильности каждый пользователь и каждый терминал в преимущественном варианте должен быть представлен в сети соответствующим агентом, который содержит всю относящуюся к пользователю или терминалу служебную логику и все служебные данные и управляет всеми сеансами связи пользователя или терминала. Пользователи/терминалы подключаются к узлам доступа сети, а агенты обеспечивают их обслуживание в узлах обслуживания. В сетях типа европейской сети GSM контроллеры базовой станции действуют как узлы доступа, а МКЦ со своими встроенными регистраторами положения посетителей (visitor location register) действует и как узел обслуживания, и как посещаемое положение (visited location). Различные особенности таких интеллектуальных сетей и агентов описаны в статье L. Soderberg, "Развитие интеллектуальных архитектур для персональной связи", Ericsson Review vol. 70, N. 4, с. 156 - 171 (1993), которая присоединяется по ссылке.

На фиг. 16 МПА может быть выполнен в виде процедуры или набора процедур, выполняемых на удаленных фиксированных главных вычислительных машинах (hosts, "хостах") или трассировщиках, которые обмениваются данными и заблаговременно подключены к ресурсам локального "хоста" и которые копируют кэш-память данных второго класса для АПМРС. АПМРС может быть выполнен в виде процедуры или набора процедур, выполняемых на местном фиксированном "хосте" или трассировщике, которые связывают и заблаговременно назначают МПА удаленным фиксированным "хостам" и трассировщикам для их мобильного пользователя клиента.

Платформа мобильной распределенной системы и МПА выполнены таким образом, чтобы обеспечивать работу при различных скоростях обмена информацией, подключение различных линий связи в различных местах и поддерживать мобильность ресурсов и услуг связи. ПМРС обычно обеспечивает функции управления информацией о положении и функции управления перемещением с предсказанием, которые необходимы для поддержки различных приложений, таких как мобильные файловые системы, мобильные интеллектуальные сети и т. п. В общих чертах функции УИП касаются информации о ресурсах и услугах связи (включая ресурсы программного и аппаратного обеспечения, возможностей подключения к сети, допустимых типах протоколов связи и т.п.), обеспечиваемых системами или сетями связи в заданном географическом районе. Функции УПП касаются прогнозирования положения мобильного терминала, а также функций назначения виртуального распределенного плавающего агента, которые назначают агента различным положениям в соответствии с предсказанным положением и обеспечивают предварительное соединение и мобильность обслуживания/ресурсов.

УИП в ПМРС обслуживает информацию о положении и накладывает ее на различные виды обслуживания, предлагаемые мобильной инфраструктурой в различных географических положениях. Кроме того, УИП информирует как приложения, так и агентов, поддерживающих приложения в мобильной сети, об изменениях в положении мобильного терминала и обеспечивает динамическое подключение услуг связи. Например, позволяет сети иметь распределенную файловую систему и несколько серверов, расположенных в различных географических районах. Если мобильный терминал был перемещен из района вблизи одного из серверов в район вблизи другого сервера, то УИП информирует как второй сервер, так и устройство управления кэш-памятью в мобильном терминале о том, что второй, находящийся ближе, сервер должен обеспечивать выборку требуемого файла.

При помощи АПМРС и МПА служебная логика и локальные ресурсы отвязываются от опорной сети и могут перемещаться вокруг нее, следуя за своими мобильными пользователями. Кроме того, при использовании функций управления перемещением с предсказанием, которые становятся доступными с использованием предложенного в заявке УППМА, служебная логика и ресурсы могут быть заранее выделены и заранее подключены в те места, в которые движется пользователь.

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

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