Автосеть: Машины в чате
Данные о ситуации на дорогах могут поступать с датчиков на обочинах, с вертолетов или (весьма распространенная практика) обновляться самими автолюбителями при помощи мобильных телефонов. Но все эти подходы имеют ряд недостатков или ограничений. В частности, вертолетное наблюдение слишком дорого, дорожные датчики «замечают» пробку только тогда, когда она уже распространилась на очень протяженный участок, а сообщения от «частников» могут быть недостоверными (или отсутствовать вовсе), находясь в прямой зависимости от настроения и чувства юмора водителя.
В рамках проекта Массачусетского технологического института «CarTel» ведется разработка технологий, позволяющих использовать сами автомобили в качестве источников информации о ситуации на дорогах — надежных и вездесущих. Команда CarTel представила новые алгоритмы, позволяющие оптимизировать распространение данных по беспроводной сети, связывающей автомобили. Компания Ford уже протестировала работу алгоритма, предполагая включить его в будущие версии Ford SYNC — платформы бортовых компьютеров, разработанной Ford совместно с Microsoft.
На протяжении последних 4 лет CarTel во главе с профессором Хари Балакришнаном (Hari Balakrishnan) осуществляет сбор данных о характере движения в районе Бостона при помощи сети приемников GPS, установленных на такси. На основании этой информации группа разрабатывает алгоритмы, позволяющие эффективно собирать и обрабатывать данные о дорожной ситуации. После анализа полученных алгоритмов и внесения в них некоторых улучшений исследователи собираются испытать их в условиях реального города, используя объединенные в сеть транспортные средства.
Келвин Ньюпорт (Calvin Newport), один из исследователей, говорит, что их предыдущие разработки основывались на предположении, что для любых двух автомобилей в сети будет существовать хотя бы один «путь связи», но эксперименты показали, что это не так. Кроме того, два автомобиля, находящихся в радиусе действия беспроводной связи друг от друга, в условиях города часто движутся рядом довольно долгое время, стоят на одних и тех же светофорах и вместе попадают в пробки — поэтому информация от автомобилей, идущих параллельным курсом, как правило, не слишком полезна.
Поэтому эффективный алгоритм распространения информации должен обеспечивать обмен данными между машинами, идущими встречным курсом, которые могут оставаться в радиусе беспроводной связи лишь несколько секунд. С другой стороны, алгоритм предусматривает более низкий приоритет обмена данными для автомобилей, которые стоят на светофоре и имеют больше времени, чтобы «поболтать». Сообщение о грузовике, сломавшемся посреди загруженной улицы, будет иметь больший приоритет, чем информация о выбоинах на проезжей части.
Ньюпорт совместно с Алехандро Корнехо (Alejandro Cornejo) установил, что для распределения приоритетов сообщений лучше всего воспользоваться последовательностью чисел, называемой «бинарная последовательность выполнения» («binary carry sequence»). Каждая цифра в этой последовательности — показатель максимальной степени двойки, на которую соответствующее число может быть разделено без остатка. Число 1 может быть поделено без остатка только на 1 (2 в степени 0 — первая цифра последовательности). Число 2 делится нацело на 2 (2 в степени 1 — вторая цифра). А вот тройка делится нацело только на 1, и третьей цифрой последовательности снова будет 0. Таким образом, бинарная последовательность выполнения имеет вид: 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2 ...
Важной особенностью такого набора чисел является то, что, хотя малые числа появляются намного чаще, на протяжении достаточно длительного промежутка времени каждое большое число гарантированно появится хотя бы один раз. Поэтому сообщения с высоким приоритетом (0) будут передаваться чаще, но не «забивая» полностью сообщения с более низким приоритетом. Ньюпорт и Корнехо смогли математически доказать, что использование этого алгоритма оптимизирует распространение данных по всей сети.
Система, по мнению представителя Ford, будет весьма востребована в городских районах. Для пользования её необязательно будет иметь бортовой компьютер, можно будет получать данные при помощи мобильных телефонов. Чем выше плотность транспортных потоков (а ведь именно в условиях высокой загруженности возрастает необходимость в оперативной информации о ситуации на дорогах), тем выше пропускная способность сети, и тем быстрее водители смогут получать данные.
Бортовые компьютеры на автомобилях — явление уже весьма обыденное. Также, как и их настольные собратья, они обмениваются данными, выполняют анализ ситуации, помогают своим владельцам и подвергаются атакам хакеров. Но у некоторых автомобилей (например, Scuderia Ferrari) на борту — настоящий вычислительный центр. Читайте об этом — «Скорость мысли».
По сообщению MIT News