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

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

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

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

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

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

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

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

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

По материалам: