Разработка алгоритма для распределенной системы

Добрый день!
Для распределенной АСУ необходимо разработать систему единой нумерации.

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

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

Это что-то из раздела непротиворечивость и репликация распределенных систем Танненбаума, но у него нет прямого решения подобных проблем.

Существуют ли готовые решения, если нет, то куда копать? Может идеи какие?

0

Полностью готовые решения под такую задачу вряд ли есть. Да и исходники я такие не видел.
Задача полностью с нуля делается?
Думаю, сначала разбить на отдельные блоки.
(1) Откуда брать карту, как получать информацию о появлении и исчезновении объектов
(2) Как реализовать коммуникацию операторов.
Если нет единого сервера, то возможно нужно реализовать мини-сервера на базе отдельных операторов, которые видят большое количество участников. Делается через интернет (где у операторов могут быть проблемы с соединением с другими операторами) или в локальной сети или VPN (все видят всех) ?

0

1. Эта задача решена, клиентское ПО оформляет объекты и нумерует их в локальной нумерации. Карты загружаются до работы, сами клиенты расходятся по территории с небольшими планшетами, которые и есть узлы. К планшетам привязано некое распознающее оборудование, которое и является источником информации.
2. На конкретный транспорт мы стараемся не завязываться, в основном связь через сеть радиомодемов, провод появляется в качестве исключений. Подошел ближе - есть связь, отошел - пропала. Эта основная проблема, которая создает децентрализацию.
3. О всех найденных объектах узлы оповещают соседей. Автоматике задача нумерации не нужна, объекты прекрасно отождествляются по координатам, размеру. Эта задача больше полезна операторам, которые смогут по рации обсуждать объекты, называя их номер. Понятно, что можно потом вернуться, слить все в одну базу (что и делается), где будут присвоены номера. Но мне номера нужны во время работы.
4. Нахождение объектов в некой локальной нумерации допустимо, но количество и время таких ситуаций должно быть минимизировано. При этом каждый узел должен четко знать находится данный объект в общей или в локальной нумерации.


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


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

Меня интересует исключительно разработка алгоритма нумерации. Причем нумерации человеческой (1,2,3), 32-битные хеш-суммы от координат в качестве номеров подойдут не особо (да и координаты у каждого свои по точности).

Появилась идея, что задача относится к классу задач именования, своего рода распределенный DHCP, может стоит в эту сторону копать?

0

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

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

Без введения некоторой хэширующей (или "хэширующей") функции, я думаю, не представляется возможным составить глобальную нумерацию поскольку нет центрального узла, а конфигурация сети меняется в реальном времени. Если операторы общаются только через ПО - то пусть ПО транслирует нумерацию других узлов в локальную нумерацию конкретного узла, и наоборот.
Если операторы могут общаться не только через интерфейс ПО (через телефон, например), то без некоей классифицирующей функции не обойтись. У вас есть признаки, по которым определяется одинаковы ли два объекта у разных операторов, возможно эти признаки следуют перевести в удобную для вербализации форму?

0

Сообщение от wingblack ПО каждого оператора составляет свою таблицу соответствия между локальной нумерацией и нумерацией других узлов

Да, так сейчас и сделано, это нормально для автоматики, но очень не удобно для оператора.

Сообщение от wingblack У вас есть признаки, по которым определяется одинаковы ли два объекта у разных операторов, возможно эти признаки следуют перевести в удобную для вербализации форму?

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

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

0

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

Тут еще проблема в том, что возможна довольно большая задержка пока все узлы договорятся о общем номере, особенно если сеть распадется на отдельные группы.
Программе то все равно, программам достаточно хеша, а вот для операторов общий номер может уточняться медленно. Я вижу решение только в переводе характеристик в удобную для разговора форму. Например, в пределах одного "выезда" работа будет проводится на определенном участке - следовательно можно перевести глобальные "длинные" координаты в координаты локальной сетки, причем можно не только в системе счисления по основанию 10. Аналогично поступить с высотой объекта. И получим вполне удобное для вербализации глобальное обозначение вида 10-20-50. Если получим одинаковые вербальные обозначения для разных объектов - добавить еще одно число, которое использует уточнение имеющихся признаков, или уже тут вводить нумерацию, но тогда проблема останется.
Конечно, лучше бы чтобы размер вербальной формы сразу соответствовал точности сравнения объектов

0