Одной из актуальнейших проблем соврменности является загрязнение окружающей среды выбросами в атмосферу CO₂. Соглсаcно исследованиям (http://www.theclimategroup.org/facts_and_actions/what_can_be_done/infrastructure/transport) объем выборсов CO₂ будет постоянно расти. Транспорт — один из основных источником выбросов, особенно в крупных городах. Большое количество автомобилей, автобусов и грузовиков загрязняют атмосферу своими выхлопами, пока медленно преоделвают городские заторы.

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

Но как можно добиться “зеленой волны светофоров” для общей массы автомобилей, движущихся по городу?

Современные технологии, особенно мобильные телефоны, уже прочно вошли в нашу жизнь. Практически каждый новый девайс имеет встроенный GPS приемник и беспроводной адаптер. Представим, что все водители имеют мобильный телефон в котором перед выездом указывают своё место назначения на карте. Все светофоры объеденены между собой в единую сеть, например WiFi-Mesh. При этом мобильные телефоны водитетелей также подключаются к этой сети и образрают таким образом со светофорами города большую сеть. После ввода водителем точки назначения, устройство ему предлагает оптимальный маршрут с наименьшим числом остановок, т.е. такой маршрут, чтобы при проезде через перекресток, светофоры имели зеленый попутный сигнал.

Если разделить участников сети на две категории: светофоры и автомобили, то можно заметить, что светофоры между собой образуют четкий граф связей, если принять абстракцию, что на каждом перекрестке стоит ровно один светофор и он образует ровно один узел. При этом связи, построенные Mesh протоколом маршрутизации между такими узлами – есть ни что иное как ребра данного графа. Данный граф имеет устойчивую топологию, так как узлы не перемещаются. В тоже время маршрут, проложенный телефоном – путь(поток!!) в этом графе. Если таких путей много, то мы получаем классическую задачу на графах для поиска максимального потока в графе.

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

Разделение участников Mesh-сети может быть реализовано добавлением в стек-протоколов 802.11 специальных меток, содержащих информацию о типе узла. Постоянное обновление и пересчет маршрута на телефоне потребует больших энергозатрат, что приведет к быстрому выключению телефона. Данную проблему можно решить, если в тоже время сделать из светофоров не просто участников сети (mesh-point), а узлами grid, вычисляющего оптимальный маршрут с задаными параметрами(тем более что каждый узел как минимум имеет информацию о своих соседях).