МЕТАПРОСТРАНСТВО: ПРОМЕЖУТОЧНОЕ КОММУНИКАЦИОННОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ ЧАСТИЧНО СОЕДИНЕННЫХ ОДНОРАНГОВЫХ СЕТЕЙ МОБИЛЬНОЙ СВЯЗИ С ПРОИЗВОЛЬНОЙ СТРУКТУРОЙ
METASPACE: INTERMEDIATE COMMUNICATION SOFTWARE FOR PARTIALLY CONNECTED FREE-STRUCTURE PEER MOBILE COMMUNICATION NETWORKS

Область техники к которой относится изобретение
Данное изобретение относится в целом к сетевым компьютерным системам и, в частности, относится к промежуточному коммуникационному программному обеспечению для частично соединенных одноранговых компьютерных сетей мобильной связи с произвольной структурой (сетей ad-hoc - одноранговых сетей без жестко заданной структуры и централизованного управления с возможностью непосредственного соединения между узлами).
Предшествующий уровень техники
Распределенные приложения важны для будущего компьютерных сетей, потому что они увеличивают эффективность. Текущие распределенные системы либо предполагают серверы с высокой степенью доступности, либо сетевые соединения с высокой степенью доступности. Согласование распределенных приложений проблематично для одноранговых беспроводных систем с произвольной структурой, потому что пропускная способность всей одноранговой сети беспроводной связи с произвольной структурой ограничена. Распределенные приложения особенно проблематично согласовывать для малых, но так называемых «интеллектуальных устройств», таких как сотовые телефоны, персональные цифровые информационные устройства (PDA) и носимые компьютеры, которые могут взаимодействовать с датчиками и контроллерами и другими объектами окружения. Возможность соединения таких устройств и объектов может, к примеру, быть обеспечена посредством протокола Bluetooth или IEEE 802.11. Ограничения мощности, радиопокрытие и географическое распределение совместно работающих узлов часто препятствуют иметь сквозной маршрут для узлов одноранговой сети с произвольной структурой (узлов ad-hoc). В общем, способы маршрутизации в сети ad-hoc предполагают сквозной маршрут, который соединяет узлы связи, и сфокусированы на обнаружение местоположения существующего маршрута, такого как ряд промежуточных узлов, соединяющих совместно работающие устройства. Многие приложения, такие как те, которые требуют связи в реальном времени, требуют полностью соединенный маршрут для переноса следующих друг за другом пакетов регулярным образом. Другие приложения не требуют полностью соединенного маршрута и могут существовать в сильно сегментированных сетях с доставкой нерегулярных сообщений. Такие приложения включают в себя управление персональными данными/информацией, распространение новостной информации и персональный обмен сообщениями. Таким приложениям требуется только услуга асинхронного обмена сообщениями. Известные способы предусматривают, что если нет маршрута, связь прекращается.
Для существующих методик для одноранговых сетей с произвольной структурой (сетей ad-hoc), согласующих распределенные приложения, была бы выгодна отмена требования в отношении сквозных маршрутов между узлами связи.
Сущность изобретения
Соответственно, система предоставления промежуточного программного обеспечения, именуемая Пространство метаданных (Метапространство (MetaSpace)), разработана для обеспечения услуги асинхронной доставки сообщений для частично соединенных одноранговых сетей мобильной связи с произвольной структурой. Варианты выполнения настоящего изобретения используют мобильные устройства для функционирования в качестве мостов между отдельными островами сетей. Эти мобильные устройства работают в качестве носителей, которые хранят и распространяют сообщения.
Один вариант выполнения ориентирован на систему и программную архитектуру, которая поддерживает способы кэширования, переноса и маршрутизации сообщений. Конкретнее, варианты выполнения обеспечивают способы и системы, которые расширяют концепцию коммуникационного пространства связи на распределенную среду и объединяют ее со стандартными технологиями Web-услуг, т.е. простым протоколом доступа к объектам (SOAP), и последовательными протоколами Web-услуг (WS). Это коммуникационное пространство, называемое «Метапространство», обеспечивает расширение Web-услуг на одноранговые сети мобильной связи с произвольной структурой. Другой вариант выполнения направлен на способы предоставления кэширования, переноса и маршрутизации асинхронных сообщений.
Дополнительные признаки и преимущества изобретения будут понятны из нижеследующего подробного описания иллюстративных вариантов выполнения, которое дается со ссылками на сопровождающие чертежи.
Перечень чертежей
Хотя приложенная формула изобретения излагает признаки настоящего изобретения с достаточной конкретностью, изобретение вместе со своими задачами и преимуществами может быть наилучшим образом понятно из нижеследующего подробного описания, рассматриваемого с сопровождающими чертежами, на которых:
Фиг.1 - блок-схема, иллюстрирующая в общем случае примерную компьютерную систему, на которой базируется настоящее изобретение;
Фиг.2 - блок-схема виртуального буфера данных в коммуникационном пространстве согласно варианту выполнения настоящего изобретения;
Фиг.3 - блок-схема среды промежуточного программного обеспечения, Метапространства, в соответствии с вариантом выполнения настоящего изобретения;
Фиг.4 - блок-схема, иллюстрирующая сообщение SOAP со ссылками на двоичные объекты в соответствии с вариантом выполнения настоящего изобретения;
Фиг.5 - блок-схема алгоритма, иллюстрирующая способ для мобильных устройств выполнить доставку;
Фиг.6 - блок-схема, определяющая взаимодействия между одноранговыми устройствами в соответствии с вариантом выполнения настоящего изобретения;
Фиг.7 - блок-схема, иллюстрирующая взаимодействия между одноранговыми устройствами в соответствии с вариантом выполнения настоящего изобретения;
Фиг.8 - блок-схема алгоритма, иллюстрирующая способ в соответствии с вариантом выполнения настоящего изобретения;
Фиг.9 - блок-схема, иллюстрирующая взаимно соединенные узлы в частично соединенной топологии и маршрутизацию сообщений в ней в соответствии с вариантом выполнения настоящего изобретения;
Фиг.10 - блок-схема алгоритма, иллюстрирующая способ определения оценки пути для сообщения в частично соединенной сети в соответствии с вариантом выполнения настоящего изобретения;
Фиг.11 - блок-схема алгоритма, иллюстрирующая способ для устройства для определения эффективной длины пути в соответствии с вариантом выполнения настоящего изобретения.
Подробное описание изобретения
На чертежах, где одинаковые ссылочные позиции относятся к одинаковым элементам, изобретение иллюстрируется как реализуемое в подходящей вычислительной среде. Хотя это и не требуется, изобретение будет описываться в общем контексте машиноисполняемых команд, таких как программные модули, выполняемые персональным компьютером. В общем случае программные модули включают в себя процедуры, программы, объекты, компоненты, структуры данных и т.д., которые выполняют конкретные задания или реализуют определенные абстрактные типы данных. Кроме того, специалистам в данной области техники должно быть понятно, что изобретение может быть реализовано на практике и с другими конфигурациями компьютерных систем, включая карманные устройства, многопроцессорные устройства, микропроцессорную или программируемую бытовую электронику, сетевые ПК, мини-компьютеры, универсальные компьютеры (мэйнфреймы) и т.п. Изобретение может быть также реализовано на практике в распределенных вычислительных средах, где задания выполняются удаленными устройствами обработки данных, которые соединены через сети связи. В распределенной вычислительной среде программные модули могут располагаться как в локальных, так и в удаленных запоминающих устройствах.
Фиг.1 иллюстрирует пример пригодной среды 100 вычислительной системы, в которой может быть реализовано изобретение. Среда 100 вычислительной системы является лишь примером подходящей вычислительной среды и не подразумевается как налагающая какие-либо ограничения ни по объему использования, ни по функциональным возможностям изобретения. Не следует также интерпретировать вычислительную среду 100 как имеющую какую бы то ни было зависимость или требование, относящее к любому компоненту или к комбинации компонентов, проиллюстрированных в иллюстративной рабочей среде 100.
Изобретение релизуемо с помощью разнообразных других сред или конфигураций вычислительных систем общего или специального назначения. Примерами общеизвестных вычислительных систем, сред и/или конфигураций, которые могут быть применимы для использования с изобретением, включают в себя, но не в порядке ограничения: персональные компьютеры, серверные компьютеры, карманные или носимые устройства, планшетные устройства, многопроцессорные системы, основанные на микропроцессорах системы, телеприставки, программируемую бытовую электронику, сетевые ПК, мини-компьютеры, мэйнфреймы, распределенные вычислительные среды, которые включают в себя любые из вышеупомянутых систем или устройств, и тому подобное.
Изобретение может быть описано в общем контексте машиноисполняемых команд, таких как программные модули, выполняемые на персональном компьютере. В общем случае программные модули включают в себя процедуры, программы, объекты, компоненты, структуры данных и т.д., которые выполняют конкретные задания или реализуют определенные абстрактные типы данных. Изобретение может также быть реализовано в распределенных вычислительных средах, где задания выполняются удаленными устройствами обработки данных, которые соединены через сети связи. В распределенной вычислительной среде программные модули могут располагаться как в локальных, так и в удаленных запоминающих устройствах.
На фиг.1 иллюстративная система для реализации изобретения включает в себя универсальное вычислительное устройство в виде компьютера 110. Компоненты компьютера 110 могут включать в себя, но не в порядке ограничения, блок 120 обработки данных, системную память 130 и системную шину 121, которая соединяет различные системные компоненты, включая системную память, и блок 120 обработки данных. Системная шина 121 может относиться к любому из нескольких типов шинных структур, включая шину памяти или контроллер памяти, периферийную шину и локальную шину, с использованием любой из множества шинных архитектур. В качестве примера, а не ограничения, такие архитектуры включают в себя шину промышленной стандартной архитектуры (ISA), шину микроканальной архитектуры (МСА), расширенную шину ISA (EISA), локальную шину Ассоциации стандартов видеоэлектроники (VESA) и шину межсоединения периферийных компонентов (PCI), известную также как мезонинная шина.
Компьютер 110, как правило, включает в себя множество машиночитаемых носителей. Машиночитаемые носители могут быть любыми доступными носителями, к которым компьютер 110 может осуществить доступ, и включают в себя как энергозависимые, так и энергонезависимые носители, а также как съемные, так и несъемные носители. В качестве примера, а не ограничения, машиночитаемые носители могут содержать компьютерные запоминающие носители и среды передачи. Компьютерные запоминающие носители включают в себя энергозависимые и энергонезависимые, съемные и несъемные носители, реализованные любым способом или технологией для хранения информации, такой как машиночитаемые команды, структуры данных, программные модули или иные данные. Компьютерные запоминающие носители включают в себя, но не в порядке ограничения, оперативное запоминающее устройство (ОЗУ), постоянное запоминающее устройство (ПЗУ), электрически стираемое программируемое ПЗУ (EEPROM), флэш-память или память иной технологии, ПЗУ на компакт-диске (CD-ROM), цифровой многоцелевой диск (DVD) или иной оптический дисковый носитель, магнитные кассеты, магнитную ленту, магнитный дисковый носитель или иные магнитные запоминающие устройства либо другой носитель, который можно использовать для хранения необходимой информации и к которому компьютер 110 может осуществлять доступ. Среды передачи, как правило, воплощают машиночитаемые команды, структуры данных, программные модули или иные данные в модулированном данными сигнале, таком как несущая волна или иной транспортный механизм, и включают в себя любые среды доставки информации. Выражение «модулированный данными сигнал» означает сигнал, одна или более характеристик которого установлены или изменены таким образом, чтобы обеспечить кодирование информации в сигнале. В качестве примера, а не ограничения, среды передачи включают в себя проводные среды, такие как проводная сеть или прямое проводное соединение, и беспроводные среды, такие как звуковые, радиочастотные (RF), инфракрасные и другие беспроводные среды. Комбинации любых из вышеуказанных носителей и сред также охватываются понятием «машиночитаемый носитель».
Системная память 130 включает в себя компьютерные запоминающие носители в виде энергозависимой и/или энергонезависимой памяти, такой как постоянно запоминающее устройство (ПЗУ) 131 и оперативно запоминающее устройство (ОЗУ) 132. Базовая система 133 ввода-вывода (BIOS), содержащая базовые процедуры, которые помогают переносить информацию между элементами в компьютере 110, например во время запуска, обычно хранится в ПЗУ 131. ОЗУ 132 обычно содержит данные и/или программные модули, которые оперативно доступны для блока 120 обработки данных и/или которыми он в текущий момент оперирует. В качестве примера, а не ограничения, фиг.1 иллюстрирует операционную систему 134, прикладные программы 135, другие программные модули 136 и данные 137 программ.
Компьютер 110 может также включать в себя другие съемные/несъемные энергозависимые/энергонезависимые компьютерные запоминающие носители. Исключительно в качестве примера, фиг.1 иллюстрирует накопитель 141 на жестких магнитных дисках, который считывает с несъемного энергонезависимого магнитного диска или записывает на него, дисковод 151 для магнитного диска, который считывает со съемного энергонезависимого магнитного диска или записывает на него и дисковод 155 для оптического диска, который считывает со съемного энергонезависимого оптического диска 156, такого как CD-ROM либо иной оптический носитель, или записывает на него. Другие съемные/несъемные энергозависимые/энергонезависимые компьютерные запоминающие носители, которые могут использоваться в иллюстративной рабочей среде, включают в себя, но не в порядке ограничения, кассеты с магнитной лентой, карточки флэш-памяти, цифровые многоцелевые диски, цифровую видеоленту, твердотельное ОЗУ, твердотельное ПЗУ и тому подобное. Накопитель 141 на жестких магнитных дисках обычно подсоединен к системной шине 121 через интерфейс несъемной памяти, такой как интерфейс 140, а дисковод 151 для магнитного диска и дисковод 155 для оптического диска обычно подсоединены к системной шине 121 посредством интерфейса съемной памяти, такого как интерфейс 150.
Дисководы и накопители и связанные с ними компьютерные запоминающие носители, рассмотренные выше и проиллюстрированные на фиг.1, обеспечивают хранение машиноисполняемых команд, структур данных, программных модулей и других данных для компьютера 110. На фиг.1, например, накопитель 141 на жестких магнитных дисках иллюстрируется как хранящий операционную систему 144, прикладные программы 145, другие программные модули 146 и данные 147 программ. Отметим, что эти компоненты могут быть либо теми же самыми, либо отличными от операционной системы 134, прикладных программ 135, других программных модулей 136 и данных 137 программ. Операционной системе 144, прикладным программам 145, другим программным модулям 146 и данным 147 программ присвоены отличные ссылочные позиции, чтобы показать, что они, по меньшей мере, являются другими копиями. Пользователь может вводить команды и информацию в компьютер 110 через устройства ввода, такие как планшет или электронный цифровой преобразователь 164, микрофон 163, клавиатура 162 и координатно-указательное устройство 161, обыкновенно именуемое мышью, шаровым манипулятором (трэкболом) или сенсорной панелью. Другие устройства ввода (не показаны) могут включать в себя джойстик, игровую панель, спутниковую антенну, сканер или тому подобное. Эти и иные устройства ввода часто подсоединены к блоку 120 обработки данных через интерфейс 160 пользовательского ввода, который связан с системной шиной, но могут быть подсоединены и посредством других структур интерфейсов и шин, таких как параллельный порт, игровой порт или универсальная последовательная шина (USB). Монитор 191 или другой тип отображающего устройства также подсоединен к системной шине 121 через интерфейс, такой как видеоинтерфейс 190. Монитор 191 может быть также объединен с сенсорной экранной панелью или тому подобным. Отметим, что монитор и/или сенсорная экранная панель могут быть физически связаны с корпусом, в который встроено вычислительное устройство 110, такое как планшетный персональный компьютер. В дополнение к этому, компьютеры, такие как вычислительное устройство 110, могут также включать в себя другие периферийные устройства вывода, такие как громкоговорители 197 и принтер 196, которые могут быть подключены через периферийный интерфейс 194 вывода или тому подобное.
Компьютер 110 может работать в сетевой среде с помощью логических соединений с одним или более удаленными компьютерами, такими как удаленный компьютер 180. Удаленный компьютер 180 может быть персональным компьютером, сервером, маршрутизатором, сетевым ПК, одноранговым устройством или другим общим сетевым узлом и, как правило, включает в себя многие или все элементы, описанные выше в отношении компьютера 110, хотя на фиг.1 показано только запоминающее устройство 181. Показанные на фиг.1 логические соединения включают в себя локальную сеть (LAN) 171 и глобальную сеть (WAN) 173, но могут также включать в себя и иные сети. Такие сетевые среды обычны в учреждениях, компьютерных сетях промышленных предприятий, интрасетях и Интернете. К примеру, в настоящем изобретении компьютерная система 110 может содержать машину-источник, из которой данные перемещаются, а удаленный компьютер 180 может содержать машину-адресат. Отметим, однако, что машина-источник и машина-адресат не обязательно должны быть соединены сетью или любым другим средством, но, вместо этого, данные могут перемещаться посредством любых носителей, выполненных с возможностью записи платформой источника и считывания платформой или платформами адресата.
При использовании в сетевой среде LAN компьютер 110 соединяется с LAN 171 через сетевой интерфейс или адаптер 170. При использовании в сетевой среде WAN компьютер 110 обычно включает в себя модем 172 или иное средство для установления связи по WAN 173, такой как Интернет. Модем 172, который может быть внутренним или внешним, может быть подсоединен к системной шине 121 через интерфейс 160 пользовательского ввода или другой подходящий механизм. В сетевой среде программные модули, показанные относящимися к компьютеру 110, или их части могут храниться в удаленном запоминающем устройстве. В качестве примера, а не ограничения, фиг.1 иллюстрирует удаленные прикладные программы 185 как находящиеся в запоминающем устройстве 181. Понятно, что показанные сетевые соединения являются иллюстративными и что можно использовать другие средства установления линии связи между компьютерами.
В последующем описании изобретение будет описываться со ссылкой на действия и символические представления операций, которые выполняются одним или более компьютерами, если не указано иное. По существу, понятно, что такие действия и операции, которые время от времени называются машиноисполняемыми, включают в себя манипуляцию электрическими сигналами, представляющими данные в структурированном виде, со стороны блока обработки данных компьютера. Эта манипуляция преобразует данные или сохраняет их в ячейках системы памяти компьютера, что переконфигурирует или иным образом меняет работу компьютера хорошо понятным для специалистов в данной области техники образом. Структуры данных, где данные сохраняются, являются физическими ячейками памяти, которые имеют конкретные свойства, определенные форматом этих данных. Однако, хотя изобретение и описывается в вышеупомянутом контексте, это не означает его ограничения, и, как ясно специалистам в данной области техники, различные действия и операции, описанные здесь далее, могут также быть реализованы в аппаратном обеспечении.
Варианты выполнения настоящего изобретения направлены на согласование распределенных приложений в одноранговой среде мобильной связи с произвольной структурой, охватывающей множество платформ и разнородных устройств. На фиг.2 блок-схема иллюстрирует среду промежуточного программного обеспечения для одноранговой среды с произвольной структурой, называемую здесь далее «Метапространством». Метапространство может включать в себя виртуальный буфер 202 данных, выполненный с возможностью согласования распределенных приложений, таких как приложение 204 и 206. Приложение 204 показано посылающим 208 метаданные к виртуальному буферу 202 данных, а приложение 206 показано принимающим метаданные 210. В совокупности Метапространство 200 обеспечивает выделение виртуального совместно используемого буфера связи для приложений 204 и 206, который может находиться в различных устройствах или узлах. Узлы в Метапространстве 200 известны как узлы 212, 214 и 216.
В одном варианте выполнения Метапространство 200 обеспечивает две программные услуги. Во-первых, одна услуга может реализовывать услугу по асинхронному обмену сообщениями между приложениями, расположенными в различных устройствах или узлах, без предварительных предположений о существовании сетевого соединения между этими различными узлами. Другая услуга может включать в себя услугу, которая обеспечивает совместное использование данных между приложениями, распределенными среди многих узлов.
В отличие от известных основанных на пространстве систем Метапространство 200 не опирается на серверы с высокой степенью доступности, которые содержат все пространство, или на сеть с архитектурой с высокой степенью доступности, которая соединяет различные узлы. Метапространство 200 поддерживает виртуальный буфер 202 данных в качестве совместно используемого буфера распределенным образом. Поэтому Метапространство 200 может обеспечивать оболочку для хранения, маршрутизации и переноса данных. Метапространство 200 может быть реализовано как облегченный компонент промежуточного программного обеспечения для выполнения на устройствах с ограниченными ресурсами, наподобие карманного ПК (Pocket PC) и интеллектуальных телефонов.
В одном варианте выполнения Метапространство 200 базируется на технологиях стандартных WEB-услуг, основывающихся на расширяемом языке разметки (XML), таких как SOAP и тому подобных. Преимущественно технологии стандартных Web-услуг XML облегчают возможность взаимодействия и расширяемость Метапространства 200. Например, за счет принятия одного и того же формата сообщений приложение может вызывать Web-услугу в Интернете через Метапространство 200.
На фиг.3 иллюстрируется программная архитектура Метапространства 200. Конкретнее, фиг.3 иллюстрирует взаимодействие между двумя средами 306(1-2) Метапространства в различных устройствах, когда они устанавливают парный канал связи, например, по протоколу Bluetooth. Установление такого парного канала связи может происходить, когда устройства, содержащие Метапространства 306 (1-2), находятся поблизости. В одном варианте выполнения устройство, содержащее программное обеспечение Метапространства, содержит три компонента в одном устройстве, включая хранилище 312 (1-2) метаданных, агента 310 (1-2) Метаданных и посредника 308 (1-2) динамически подключаемой библиотеки (DLL). Хранилище 312 метаданных может быть сконфигурировано как контейнер сообщений XML (SOAP), структурированный иерархически. Агент 310 Метапространства может быть реализован как активная часть Метапространства 200. Агент 310 Метапространства может отвечать за взаимодействие с другими устройствами по протоколам 314 Метапространства. Протоколы 314 Метапространства могут гарантировать доставку нерегулярных сообщений. Агент 310 Метапространства может также быть сконфигурирован для обработки запросов операций от приложений, которые используют Метапространство 200 для передачи и совместного использования данных. Подробности запроса могут быть замаскированы от приложений, таких как приложения 302(1-2), с помощью посредников 308 (1-2) DLL. Посредники 308 DLL представляют собой связываемые библиотеки и могут быть сконфигурированы для обеспечения компактных интерфейсов прикладного программирования (ИПП, API) для пользовательских приложений.
Память 312 метаданных содержит метаданные в качестве сообщений, которые могут быть сформированы как сообщения XML, упакованные в качестве сообщений протокола доступа к простым объектам (SOAP). Метаданные могут включать в себя данные протокола маршрутизации Web-услуг (маршрутизация WS), чтобы определить информацию и данные маршрутизации, пригодные для расширенного протокола, определенного для описания критической информации, необходимой для агентов 310 Метапространства, чтобы правильно обрабатывать сообщения. В одном варианте выполнения данные расширенного протокола сконфигурированы как элементы XML.
Пример сообщений XML, хранящихся в Метапространстве 200, показан ниже в Таблице 1.
Таблица 1
<img file="00000001.tif" he="221" wi="163" img-content="undefined" img-format="tif" />
В одном варианте выполнения Метапространство 200 расширяет формат SOAP путем добавления нового заголовочного элемента, заключенного в тэги (неотображаемые элементы разметки) msprop под пространством имен (namespace) Метапространства. Структуры данных для полей данных могут включать в себя следующее:
ExpirateTime: время истечения срока действия сообщений в абсолютном времени. Данные являются недействительными после этого момента времени.
HopLimitation: верхняя граница количества транзитных участков, на которые может переноситься сообщение. Значение верхней границы уменьшается на единицу после успешной передачи.
Timestamp: обычное время, помечающее время создания сообщения.
Namespace: идентифицирует подпространство, в котором помещается сообщение.
AdminDomain: домен, которым ограничено сообщение. Это поле отличается от поля Namespace в том, что adminDomain задает физическую границу устройств, которые совместно используют одну и ту же привилегию администрирования, а Namespace представляет собой логическое понятие. Это значение особенно полезно для сообщений групповой адресации и сообщений с адресацией любому члену группы. В этих случаях распространение сообщения ограничивается некоторым набором устройств, и такое ограничение препятствует нежелательной потере сообщений.
RelateTo: конкретизирует тему, к которой относится сообщение. Атрибут взаимосвязи обеспечивается, чтобы определить, как действовать, когда два сообщения относятся к одной конкретной теме, например, «заменить» («replace») означает, что более новое сообщение будет выводить из употребления более старые.
Priority: определяет приоритет сообщения, например, низкий, нормальный или высокий.
Property: это поле является расширяемым способом для приложения, чтобы задать специфические для приложения свойства (пара «имя-значение»), связанные с этим сообщением. Метапространство 200 можно сконфигурировать для поддержания основанных на содержимом поисков сообщений посредством свойств.
Согласно фиг.4, Метапространство 200 можно сконфигурировать для обработки метаданных, в том числе двоичных данных большого объема. Фиг.4 иллюстрирует составной объект 400, сконфигурированный для обработки двоичных данных. Эти двоичные данные могут быть на XML, причем данные кодируются в формате ASCII (американского стандартного кода обмена информацией), к примеру, Base64. Однако этот способ является дорогостоящим. Объект 400 иллюстрирует альтернативу, в которой Метапространство 200 хранит только ссылку в сообщении XML и хранит сохраненные двоичные данные где угодно в формате необработанных данных. Фиг.4 иллюстрирует часть 406, соответствующую сообщению SOAP и двоичный объект 1 408. Часть 406, соответствующая сообщению SOAP, и двоичный объект 1 408 разделены разделителем 412, а двоичный объект 1 408 отделяется от дополнительных двоичных объектов разделителями 414 (n). Сообщение 406 SOAP указывает на двоичный объект 1 408 посредством ссылки 1 402 и на другие двоичные объекты n посредством ссылки n 404.
Фиг.4 иллюстрирует, что нагрузку по обработке множества объектов можно смягчить с помощью внутренних ссылок и сохранения всех данных (данных сообщения XML и двоичных данных) в составном объекте, который можно отображать в файл.
На фиг.5 блок-схема алгоритма иллюстрирует способ выполнения обнаружения устройств и сопровождения соседей для Метапространства 200. В одном варианте выполнения Метапространство 200 использует универсальные идентификаторы информационных ресурсов (URI) для идентификации устройств и не ограничивается использованием какой-либо конкретной схемы URI. Далее, в одном варианте выполнения, чтобы идентифицировать приемник, Метапространство 200 использует схему metaspace://domain/device (метапространство://домен/устройство). Схемы, отличающиеся от этой, могут быть названы как Интернет-хост. Блок-схема 500 алгоритма иллюстрирует подход для обнаружения устройством своих соседей на основании протокола прослушивания-оповещения. Этап 510 предусматривает, что каждое устройство выполняет широковещательную рассылку информации маяка на общеизвестный порт. Этап 520 предусматривает, что, услышав такой маяк, устройство узнает, что существует активный сосед. Каждый маяк содержит поле срока аренды, которое указывает ожидаемое время доступности. Этап 530 предусматривает, что в связи с рассмотрением информации соседа как «мягкого» состояния (soft-state), устройства обновляют свои состояния до того, как срок действия их состояний истечет. Типичная структура маяка показана в Таблице 2.
Таблица 2
<img file="00000002.tif" he="65" wi="163" img-content="undefined" img-format="tif" />
Внутренняя структура данных (карта хеширования) строится для поддержания взаимосвязи между именем устройства и коммуникационным адресом агента 310 Метапространства в этом устройстве.
На фиг.6 блок-схема алгоритма иллюстрирует протокол переноса данных, который конкретизирует, как распространяются сообщения, когда два устройства встречают друг друга в среде Метапространства 200. Каждое устройство в Метапространстве 200, такое как устройство 306 по фиг.3, поддерживает хранилище для метаданных 312. При переносе сообщений к одноранговому устройству переносятся только те сообщения, которые неизвестны. Чтобы сделать это, фиг.6 иллюстрирует протокол двухфазного переноса данных. Этап 610 иллюстрирует фазу один и предусматривает, что одноранговые устройства обмениваются информацией о своих интересах и квитированием установления связи. Этап 620 предусматривает, что сообщения доставляются в течение этого обмена.
На фиг.7 иллюстрируется режим выталкивания для протокола переноса данных. Конкретнее, Устройство А 702 сначала объявляет Устройству В 704 экспортированное пространство имен Ns(A.exp) 706. Устройство В 704 вычисляет пересечение экспортированного пространства имен Устройства А 702 и своих собственных интересов Ns(A.exp)∩Ns(B.Int) 708, а затем отвечает Устройству А 702 таким пересечением, равно как и сводкой сообщений, которые известны Устройству B под пересекающимся пространством имен. В одном варианте выполнения эта сводка строится с помощью фильтра Блума, который известен и вариант выполнения которого описывается ниже. После приема ответа Устройство А 702 начинает сеанс доставки сообщений. Посредством проверки сообщения на соответствие сводке, 710, переносятся только те сообщения, которые неизвестны Устройству В 704.
Подобно режиму выталкивания, Метапространство 200 поддерживает соответствующий режим втягивания. Подобно режиму выталкивания, протокол режима втягивания (не показан) обеспечивает обращение режима, показанного на фиг.7, так что устройство, которое будет принимать данные, начинает сеанс путем посылки информации о своих интересах.
Фильтр Блума является известным фильтром, используемым для эффективного измерения потока трафика. В одном варианте выполнения фильтр Блума, подходящий для Метапространства 200, может быть сконфигурирован в предположении, что длина вектора сводки равна m. Пусть Н = (Н1, Н2, Н3, Н4) = MD5_Hash(msg_id). Каждое Нi (i=1, 2, 3, 4) является двойным словом. В векторе сводки устанавливается бит Ki = Hi mod m (i=1, 2, 3, 4). Фильтр Блума имеет некоторую вероятность ошибочного результата (FPP). Однако FPP достаточно мала в обычных случаях, поскольку Pfpp ≈ (1-e-(4n/m))4. В среде Метапространства 200 эта вероятность ошибочного результата вносит малый вред в перенос метаданных, потому что ошибочно непереданные сообщения могут быть перенесены в следующем сеансе переноса данных.
На фиг.8 вариант выполнения ориентирован на маршрутизацию сообщений в среде Метапространства 200. Конкретнее, в связи с тем, что среда Метапространства 200 включает в себя топологию соединений, которая динамически изменяется, фиг.8 показывает способ маршрутизации сообщений для динамически изменяющейся топологии. Способы маршрутизации предложены, - например, Vahdat и Becker предлагают способ маршрутизации среди мобильных устройств, который предусматривает, что каждый узел выделяет кэш для хранения сообщений для других узлов, A. Vahdat and D. Becker, «Epidemic Routing for Partially Connected Ad Hoc Networks», 2000; Technical Report CS-200006, Duke University, April 2000. Когда два раздельных узла встречаются, выполняется эпидемический процесс, в котором эти два узла обмениваются сообщениями, которые каждый содержит, а затем переносят одинаковый набор сообщений. Этот способ использует алгоритм лавинной маршрутизации и предполагает неограниченные размеры буфера и время, чтобы гарантировать доставку нерегулярных сообщений. Способ Vahdat и Becker и подобные способы следуют основанным на лавинной маршрутизации алгоритмам, которые генерируют необязательные сообщения, занимающие кэш-память, тем самым снижая скорости доставки.
Устройства, посылающие сообщения в среде Метапространства 200, могут не знать точное местоположение пункта назначения. Кроме того, устройства, посылающие сообщения, могут не знать маршрут к этому пункту назначения. Согласно способу в варианте выполнения, показанном на фиг.8, протокол маршрутизации в частично соединенной сети включает в себя принятие по меньшей мере двух решений. Во-первых, когда два устройства встречаются, принимается решение о том, какие сообщения доставляются от одного к другому. Во-вторых, когда на устройстве хранилище 312 метаданных заполнено, принимается решение о том, какие сообщения следует удалить, чтобы приготовить пространство для новых поступающих сообщений. В варианте выполнения такие решения принимаются локально. Далее, способ маршрутизации согласно варианту выполнения использует некоторую структурную информацию одноранговой сети мобильной связи с произвольной структурой.
Чтобы найти эту структурную информацию сети, фиг.8 предусматривает на этапе 810, что строится стохастическая модель сильно сегментированной сети. На основании этой модели этап 820 предусматривает, что метрика, называемая здесь далее длиной ожидаемого пути, используется для оценки маршрутов для доставки сообщений. Этап 830 предусматривает, что на основании этой метрики выделяется способ нахождения маршрутизации по кратчайшему ожидаемому тракту.
На фиг.9 иллюстрируется стохастическая модель сети согласно варианту выполнения. В этой модели показаны узлы 0-6, 900-912, соответственно. Согласно этой модели ребра с нулевой вероятностью соединений удаляются. Сплошная линия, соединяющая узел 5 910 и узел 6 912, представляет постоянное сетевое соединение. Сеть 900 может быть представлена сетью узлов, снабженных радиоустройствами беспроводной связи ближнего действия. Связь между двумя узлами может идти в обоих направлениях, если они находятся в одной и той же окрестности. В предположении, что каждый узел имеет конечную память, каждый узел можно сконфигурировать для переноса до М сообщений. Сообщение представляет собой блок информации, которым обмениваются между любыми двумя узлами.
Предположим полный граф G (V, E) в качестве стохастической модели сети 900 ad hoc. Каждая вершина в V представляет один идентичный узел в N. Для каждого ребра ei,j в Е присвоим вероятностный вес Pi,j, 0≤Pi≤1, который представляет вероятность существования соединения между этими двумя узлами. Если Pi,j равна нулю, нет никаких шансов, что узел i сможет связаться с узлом j непосредственно. Если Pi,j равна единице, имеется постоянное соединение между двумя узлами.
На фиг.10 блок-схема алгоритма иллюстрирует способ нахождения кратчайшего ожидаемого пути. Конкретнее, рассмотрим пару узлов <s, d>, где s - источник, а d - адресат. Этап 1010 предусматривает, что узел s посылает сообщение в момент времени 0, и распределение вероятности того, что d примет сообщение, представлено как П. П может быть определено посредством топологии стохастической модели сети, как описано выше. Этап 1020 предусматривает определение длины ожидаемого пути от s к d как ожидаемого времени, когда d примет сообщение, как показано в уравнении 1:
E(T) = Eпуть =<img file="00000003.tif" he="11" wi="17" img-content="undefined" img-format="tif" />
Уравнение 1
В Метапространстве 200 множество копий сообщения может посылаться, следуя множеству маршрутов. Здесь и далее маршрут с длиной кратчайшего ожидаемого пути будет называться как первичный маршрут. Этап 1030 предусматривает установку длины ожидаемого пути для первичного маршрута как верхнюю границу Епуть. Длина ожидаемого пути для первичного маршрута может быть выведена из уравнения 2:
Епуть ≈ Е<sub>первичн</sub> =<img file="00000004.tif" he="12" wi="16" img-content="undefined" img-format="tif" />
Уравнение 2
i
первичн
i
i
первичн
где p является вероятностью соединения для линии i связи по первичному маршруту. Этап 1040 предусматривает использование Е в качестве оценки для Епуть. Чтобы найти эту оценку, сначала вычисляется длина ожидаемого пути любой пары узлов <s, d> путем нахождения первичного маршрута между этими двумя узлами. Вслед за этим вес p заменяется на линии связи стохастической модели сети величиной 1/p, а затем выполняется известный алгоритм Дийкстра (Dijkstra), чтобы получить Е(s, d) ≈ Епуть (s, d). В варианте выполнения каждый узел должен иметь полную топологию стохастической модели сети. Построение и поддержание этой топологии может быть в одном варианте выполнения в некоторых отношениях аналогично маршрутизации с учетом состояния каналов, как известный протокол, такой как протокол первоочередного открытия кратчайшего маршрута (OSPF), который распределяет информацию маршрутизации между маршрутизаторами, принадлежащими к единой сети, с целью нахождения маршрута наименьшей стоимости от одного узла ко всем остальным узлам.
m
На фиг.11 вариант выполнения способа нахождения маршрутизации согласно кратчайшему ожидаемому пути иллюстрируется в блок-схеме алгоритма. Этот способ основан на метрике длины ожидаемого пути, описанной выше. Этап 1110 предусматривает, что для каждого сообщения в хранилище 312 метаданных устройства присваивается эффективная длина пути EPL. Этап 1120 предусматривает, что эффективная длина пути сбрасывается на бесконечность, когда устройство принимает новое сообщение. Этап 1130 предусматривает, что если сообщение распространяется к другому устройству, EPL обновляется как длина ожидаемого пути от целевого устройства к адресату сообщения. В псевдокоде способ маршрутизации может быть описан следующим образом:
Таблица 3
<img file="00000005.tif" he="105" wi="165" img-content="undefined" img-format="tif" />
Способ иллюстрирует, что бесполезно распространять сообщение к одному устройству, если имеется мало шансов доставить его адресату; что при очистке кэша для нового сообщения предпочтительны те, что доставлены с высокой вероятностью.
Метапространство 200 включает в себя приложение, программируемое в посреднике 308 DLL (proxy_dll), который функционирует в качестве моста между приложением и промежуточным программным обеспечением Метапространства 200. В варианте выполнения имеется четыре класса функций, как показано в Таблице 4.
Таблица 4
<img file="00000006.tif" he="168" wi="163" img-content="undefined" img-format="tif" />
Базовые операции Метапространства, охватываемые интерфейсами прикладного программирования (ИПП), включают в себя запись, считывание, перечисление и поиск.
Функция записи предусматривает, что все приложения выполняют вызов записи Write (spaceid, metadata), чтобы ввести метаданные в среду Метапространства. Метаданные могут быть упакованы в сообщения SOAP или сходный тип сообщений. Каждому из сообщений присваивается глобально уникальный идентификатор сообщений.
Функция считывания предусматривает два вида вызовов функции для приложений, чтобы считывать метаданные в Метапространстве. Первым видом вызова функции является take (msgid, MetaData * metadata), которая считывает метаданные и удаляет эти данные из Метапространства. Вторым видом функции является read (msgid, MetaData * metadata), которая удаляет данные и оставляет метаданные неизменными.
Функция перечисления и поиска предусматривает, что метаданные, хранящиеся в Метапространстве, могут быть перечислены путем вызова enum_metadata (spaceid, template), которая возвращает структуру enum_info, которую приложения могут использовать для считывания всех перечисленных данных. Шаблон (template) предусматривает критерии выбора, которые определяют, какие метаданные подлежат перечислению. Если предоставлен NULL (нуль), эта функция возвращает все хранящиеся в текущий момент метаданные.
Регистрация событий в Метапространстве также охватывается интерфейсами прикладного программирования. А именно, обеспечены ИПП для регистрации и отмены регистрации.
Функция регистрации предусматривает, что приложение может зарегистрировать обработчика, который обрабатывает некоторое событие, такое как определенный тип пришедшего сообщения или подсоединившегося устройства. Системный вызов регистрации таков: register (spaceid, event_type, template, handler). Шаблон задает фильтр, который применяется для выбора, когда происходит некоторый тип события. К примеру, когда происходит событие «прием сообщения», шаблон может задать, что обработчик вызывается лишь тогда, когда сообщение посылается от некоторого лица. Эта функция возвращает регистрационный идентификатор reg_id, который может далее использоваться для отмены регистрации события.
Функция Unregister (Отменить регистрацию) предусматривает, что приложение может удалить ранее зарегистрированный обработчик события, выполняя системный вызов unregister (reg_id).
Метапространство обеспечивает также по меньшей мере три ИПП операций пространства имен. Функция создания и удаления подпространства предусматривает, что приложение может создавать любое подпространство в Метапространстве. Системный вызов create(spacename) служит для создания подпространства в текущем метапространстве. Имя Пространства (spacename) уникальным образом идентифицирует подпространство. Системный вызов remove(spacename) выполняется, чтобы удалить подпространство. Отметим, что эти два системных вызова предусматриваются только для привилегированных приложений.
Функция экспорта и импорта пространства позволяет приложениям устанавливать, в отношении какого подпространства (подпространств) они заинтересованы в совместном использовании с другими устройствами. Приложение вызывает set_interest(spaceid), чтобы принимать сообщения от других устройств в подпространстве. Приложение вызывает set_export(spaceid), если приложению нужно передавать сообщения в подпространстве другим устройствам.
Функция перечисления подпространства предусматривает, что подпространство в Метапространстве можно перечислять путем вызова функции enum_space(template). Шаблон задает критерии выбора, по которым желают перечислять подпространства, связанные с приложением, например, все подпространства под sub_spaces, именуемом «my_family», все подпространства, которые экспортированы, или все подпространства, которые содержат ключевое слово «новости», и т.д.
Принимая во внимание многие возможные варианты выполнения, к которым могут быть применены принципы этого изобретения, понятно, что варианты выполнения, описанные здесь со ссылкой на чертежи, считаются лишь иллюстративными, а не ограничивающими объем изобретения. К примеру, специалисты поймут, что элементы проиллюстрированных вариантов выполнения, показанные в виде программного обеспечения, могут быть реализованы и в аппаратном обеспечении, и наоборот, или что проиллюстрированные варианты выполнения могут быть модифицированы в компоновке и деталях без отхода от сущности изобретения. Поэтому изобретение, как оно описывается здесь, предполагает все такие варианты выполнения, которые попадают под объем, определяемый нижеследующей формулой изобретения и ее эквивалентами.