Данные о загруженности дорог можно получать разными способами: с вертолетов, при помощи видеокамер или мобильных телефонов.

Проект MIT под названием CarTel исследует возможности самих автомобилей для отслеживания трафика на дорогах. Результатом работы проекта явился новый алгоритм, который оптимизирует распространение данных в сети, объединяющей автомобили по беспроводной связи. Исследователи в компании Ford уже тестируют алгоритм на предмет его включения в будущие версии Sync - устанавливаемой в автомобили системы связи и развлечений, которую разрабатывают совместно Ford и Microsoft.

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

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

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

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

Наилучшим способом удовлетворить обоим этим требованиям оказалось использование бинарной последовательности выполнения (binary carry sequence) - последовательности чисел, где каждое следующее число является показателем максимальной степени двойки, на которую соответствующее целое число будет делиться без остатка. Например, единица может быть поделена без остатка на 2⁰, 2 - на 2¹, а 3 - снова на 2⁰. Таким образом, последовательность первых 12 чисел такова: 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2.

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

Авторам алгоритма - Кельвину Ньюпорту (Calvin Newport) и Алехандро Корнехо (Alejandro Cornejo) - удалось математически доказать, что использование бинарной последовательности выполнения оптимизирует распространение информации в сети. Эксперт из компании Ford, тестирующий алгоритм, считает, что распространение данных по сети автомобилей будет весьма востребовано в городах. Альтернативный вариант - загрузка данных о трафике из сотовой сети, что доступно каждому обладателю iPhone. С другой стороны, объединенные беспроводной сетью машины смогут обмениваться данными и там, где покрытие сотовой сети отсутствует.

Источник:  http://rnd.cnews.ru/