Results 1 to 15 of 15
Hybrid View
-
7th December 2008 03:08 #1
Routing Algorithm за Wireless Sensor Networks
Имам проект с няколко човека да създадем протокол за събиране на информация от мрежа със сензори. Сензорите са Sunspot на SUN и комуникират помежду си чрез Wireless. Тъй като устройствата са на батерия, трябва този протокол да бъде с минимално изпращане и приемане на съобщения. Идеята която ми хрумна е следната:
Създавам дървовидна структура, като събирача на данни изпраща на всички около него "hello" пакет. Всеки от получилите пакета запазва своя баща и препраща съобщението надолу докато се получи дървовидната структура.Ако "син" получи два или повече "покани от бащи", взима първата и игнорира всяка следваща. Имам идеята всеки "син" да има втори резервен баща , ако случайно връзката пропадне.
Когато събирача на данни направи заявка и получи отговорите и случайно има разлика в броя на участниците, то бива дървото наново подредено. Също така, когато има нов сензор, автоматично да подава заявка за връзване към дървото.
Бих искал да обсъдим идеята ми и евентуално да предложите нещо по-ефективно или забележки по идеята.We are drowning in information, but starving for knowledge and time!
-
7th December 2008 13:46 #2
Балансирай някак броя на "синове" у бащите, да не осъмнат някои с цял орляк, а други без никва челяд
Това е сериозно.
EVGA X299 FTW K|i9-7960X@4.7|4x8 Patriot Viper Steel 4000|GTX 1660 Ti|970 EVO 1 TB|Seasonic Focus GX-1000|Xigmatek Elysium|Кило и половина вода
Rampage IV Extreme BE|E5-1680v2@4.7|4x4 HyperX 1866|Cougar Aqua 240|GTX 1050 Ti|970 EVO 1/4 TB|CM 850 SilentPro|HAF-X|Без истинско водно
-
7th December 2008 14:34 #3Registered User
Join Date: Dec:2006
Location: Sofia
Posts: 72
Става ли да дефинираш проблема по-точно? Какво точно искаш да минимизираш /максимизираш/
Ясно е че ако B i C са в обсега на А то
и двата върха ще се закачат на А вместо B на А и С на В, за да се минимизира броя прехвърляния на информация. Теоретично мога да ги подредя и по такъв начин както се казва в горния пост че на един баща да има цял орляк а друг да няма никакви синове ;\
и пак броя прехвърляния да е минимален
Ако трябва да разсъждавам, мисля че ти трябва да максимизираш времето на работа на батерията на най-ранно самоизключилия се сензор /*паднала му е батерията*/
нещо такова ли е?
ааа и още нещо
кажи с какви ресурси разполагаш. /памет на всяко устройство, способност за извършване на логически и математически операции/
събиращия инфорамация на точно определено място ли е или алгоритъма трябва да избере най-подходящото.Last edited by peltekov; 7th December 2008 at 15:12.
-
7th December 2008 17:29 #4
Технически данни:
Processor: ARM920T 32bit
Memory: 512Kb RAM, 4MB Flash
OS:Squawk VM
Относно математическите операции нямам никакви ограничения. На самите устройства е качен Java Mobile Edition + малко екстри.
Искам да минимизирам големината на съобщенията изпращани между сензорите и техния брой. Тъй като това се води състезание между отбори има формули, които изчисляват costs на алгоритъма. Параметрите в тези формули са големина на съобщението, броя на изпратените, броя на изгубените.
@Bombera, Балансирането все си мисля, че ще става от самосебе си при създаването на дървото. Друго като идея е всеки сензор да има променлива, в която се запазва колко сензора са нужни да се стигне до върха на дървото и по този начин да решава към кого да се вържат останалите, като всеки нов е по-добре да се върже по високо към корена на дървото. Решихме също така всеки сензор да слуша и да запазва в един свързан лист всички потенциално бащи и когато един пропадне да препраща на следващия. Ако има нов включен сензор, то той ще се върже към дървото след като бъде направено запитване от базовата станция.
Повече за формулите и за задачата има тук. Линка е валиден 120 часа.We are drowning in information, but starving for knowledge and time!
-
7th December 2008 17:50 #5
От към алгоритмична гледна точка това ми прилича на реално моделиране на черно-червено дърво. То е с височина log n * log n, като n е борят на роботите в случая. Проблема е, че 1-вия робот (на които всички останали са му синове, внуци...) ще получава най-много като количество информация. Хубавото е, че всеки робот има до 2-ма сина и един баща. Лошото е, че тези дървета са много гадни за писане и не знам дали ще се оправиш.
-
7th December 2008 18:48 #6
Gibona е изтъкнал правилно факта, че върховите нодове получават много информация. Да не говориме, че имаш доста overhead при капсулирането на съобщения нагоре по веригата(ако пазиш structure imprint). Не търси винаги най-сложното решение. При n failover маршрута имаш (n*n/2)* -1 вероятност за недоставен пакет. Защо не заложиш на token ring топология или bus решение, както е при CAN?
By replacing numbers with their logarithms, you just turn a multiplication problem into an addition problem.
-
8th December 2008 00:05 #7
Червено-черните дървета са с максимална височина 2 log2 (n+1) . Проблемът е, че тези устройства могат да бъдат разположени случайно, някои от тях ще се включват, на други може да им падне батерията и така нататък.Т.е не мога да имам AVL, бинарно или каквото и да е дърво.
Имаме идеята всеки баща да чака информация от синовете си и да я прекапсолова наново, като слагаме един общ header.Така ще намалим значително големинаа на пакетите. Отделно базовата станция при Query брои винаги приетите пакети и ако липсва устройсво преподрежда дървото наново. Също така мислим да следим статуса на батерията и ако някое устройство му падне батерията под минимума, ще преподреждаме неговите синове.
CAN ми се струва нелогично решение, тъй като ако наредим всички устройсва едно след друго, то за да получим информация от последното, ще ни бъдат нужни n-2 препращания.We are drowning in information, but starving for knowledge and time!
-
8th December 2008 16:43 #8Registered User
Join Date: Oct:2003
Location: София
Posts: 4,317
Би ли написал точно условието на задачата? Защото не можах да се ориентирам от онова, което прочетох във файла.
Също така, как се изчислява резултатът (оценката)? Топологията на мрежата известна ли е предварително? Не за вас, а за системата. Физическата структура на мрежата известна ли е предварително - т. е. разстояния между възлите? Знае ли се каква консумация имат устройствата за различните типове операции? Устройствата движат ли се?
-
8th December 2008 18:30 #9
За жалост буквално условие на задачата няма. Каквото пише на фолията, това имам като информация. Ще се опитам на интерпретирам условието.
Общо има 3 стъпки за завършване на задачата. Първата стъпка е да работи мрежата с 4 сензора. Втората е с 20 сензора във вида на GRID(т.е всички подредени на една маса). И последната стъпка е да подкараме 20 сензора, които са разпръснати в една сграда.
Точното разположение на всеки сензор не се знае нито от системата, нито от нас. Има атрибут наречен Location, но той е да бъдат разделени сензорите на групи(Пример: Всички сензори в коридорите или всички в стаите).Знае се че тези сензори при тестване ще бъдат изключвани/вкючвани за да се симулира съответно паднала батерия или изгубено устройство / включено устройство.
Устройствата не се движат, но тъй като при трета стъпка са разположени сензорите в различни стаи/коридори, ще има различни смущения. Това може да доведе до загуба на устройствата.
Нужни са следните функционалности на мрежата:
SELECTION - Запитване примерно на температура през определено време
PROJECTION
AGGREGATION(AVG,MIN,MAX,MEDIAN, COUNT)
Какво се измерва:
Температура
Светлина
Волтаж - мери се напрежението на входа на мини УСБ-то на устройството, за да се разбере дали е свързано към компютър
Формули:
1. SELECT * FROM sensors - repeated 15 times
SF=(Tcomplete -T)³x(MSGr x R + MSGs x S)
2. SELECT NodeID, Temperature FROM sensors
WHERE TEMP>v
SAMPLE 30s DURATIOn 30min
SF=(MSGr x R + MSGs x S)
Има още две запитвания, но формулите се повтарят
Легенда:
Тcomplete = сумата на върнатите отговори
Т= сумата на отговорите, които трябва да бъдат върнати
S = сума на изпратените съобщения
R = сума на върнатите съобщения
MSGs=средна големина на изпратените съобщения
MSGr= средна големина на върнатите съобщения
Може би съм се изразил в другите ми мнения леко грешно и съм заблудил някои хора. Идеята е да се намали броя на съобщенията и тяхната големина, тъй като те участват във формулите.We are drowning in information, but starving for knowledge and time!
-
8th December 2008 19:35 #10Registered User
Join Date: Oct:2003
Location: София
Posts: 4,317
Все пак не разбрах как се изчислява резултатът - т. е. как се оценяват различните решения.
Защо питам. Както знаем от физиката, електроматнитните вълни намаляват с квадрата на разстоянието. Това значи, че ако на някакво разстояние нивото на сигнала е 1, на два пъти по-голямо разстояние нивото на сигнала ще е 4 пъти по-малко. Поради това най-икономичният откъм енергия начин на предаване на съобщения може да се окаже от съсед към съсед, приближавайки се до основния възел. Да вземем един идеален случай - два възела и основен, разположени на равни разстояния помежду си и на една права - A, B, M (основен). Ако A изпраща сигнал на B, ще се нуждае от мощност P1. Съответно, понеже разстоянието от B до M е същото, за препращане от B до M също трябва мощност P1. Общата мощност за излъчване става 2P1.
Ако обаче А изпраща съобщение директно до М, понеже разстоянието е два пъти по-голямо, отколкото до B, ще му трябва мощност 4P1.
Разбира се, това е опростяване, трябва да се вземе предвид и енергията за обработка на съобщението в B. Освен това в реалния случай разстоянията и разположенията няма да бъдат толкова удобни.
Но все пак, какво се получава - в първия случай имаме повече съобщения, но по-малка мощност, т. е. по-дълъг живот на системата. Във втория имаме по-малко съобщения, но по-голяма консумация.
Затова питам как се оценява решението. Ако се оценява само по брой съобщения, най-елементарният алгоритъм е всеки възел да изпраща единствено до главния възел. Само че за тази цел трябва доста по-голяма мощност, съответно повече консумирана енергия.
Продължавам обаче да си мисля, че може да се ползва някакъв вариант на Spanning Tree Protocol. Особено ако устройствата могат да мерят нивото на получавания сигнал. Тази стойност ще позволи задаване на тегла на връзките между възлите, които са от полза за изграждането на дървото в протокола.
Другият вариант би бил да се ползва модификация на стандартен алгоритъм за рутиращ протокол: http://en.wikipedia.org/wiki/Dijkstra's_algorithm
Но при всички положения трябват тегла на връзките (ребрата в графа). Това не ми е ясно как ще се постигне в случаи 1 и 2, ако устройствата не могат да мерят нивото на получения сигнал. (В случай 3 става лесно, понеже мощността на излъчване на базовата станция може да се мени произволно - просто се започва broadcast от най-ниската мощност и се увеличава постепенно, като се проверява кои устройства отговарят за всяко ниво на мощност.)
И не ми стана ясно колко надеждна е връзката. Пишеш, че в третия вариант някои устройства може да отпадат. А в първите два?
-
8th December 2008 23:02 #11
Има функция която изчислява нивото на сигнала. Обаче ни притеснява факта , че може би има някакви интеференции в сградата и самото мерене няма да е особенно ефективно. Отделно върху задачата не гледаме от физична гледна точка, а от брой и съответно големина на съобщенията. Според мен идеалния случай е с възможно най-малко възли да покрием максимален брой сензори. Това обаче крие опасността да бъде съобщението загубено, ако връзката е нестабилна.Т.е. трябва да намеря златната среда между разстояние и ниво на сигнала. Може примерно да меря сигнала постоянно и да се връзвам примерно не при най-слабия сигнал, а втория или третия по слабост на сигнала. Утре ще се събирам с колегите да обсъдим някои подробности, но за момента съм решил да го правим чрез дървовидна структура.
П.С. За другия вторник ще имам вече фолия относно грубия строеж на задачата. Ако се интересува някой, мога да кача туй онуй.We are drowning in information, but starving for knowledge and time!
-
10th December 2008 00:08 #12
Усещам как тази задача ще се появи в някоя А група на състезанията по информатика в много извратен вид
За лично ще следя развитието на задачата, ако екипа има нужда от писане/разяснение на алгоритъм ще помгам. А ако не я дадат тази година ще я дам аз догодина 
-
10th December 2008 02:31 #13
Задачата сама по себе си не е толкова трудна, но има много неясности около нея и като гледам ще ни трябва доста време. Днес се събирах с един от колегите и си блъскахме главите точно как да изглежда пакета, с когото ще приемаме и предаваме съобщения.Тъй като на ниско ниво кореспондират устройствата чрез byte[], решихме да конструираме собствена Сериализация на обектите. Така ще си намалим съобщението с около 5 пъти и ще изпращаме нужните за нас неща т.е. от около 125 bytes/message свалихме на около 27 bytes/message. Също така мислим при всеки баща да преопаковаме получените съобщения и да ги пращаме като едно голямо. Така ще спестим доста хеадъри на съобщения и доста изпратени съобщения. Това обаче усложнява нещата и се чудим все още дали има смисъл да се прави. Също като идея ни хрумна да използваме при всеки баща нещо подобно на cache, така че ако данните вече са изпращани нагоре по дървото, ще тече съобщение с по малък обем, тъй като няма да съдържа цялата информация.
Първи драсканици относно съобщението:
------------------------------------------------------------------------------
SysData - вид на съобщението и допълнителни атрибути -- 1 byte
NodeID - Нещо като MAC на сензора --- 2 bytes
MessageType - разновидност на съобщението(температура, светлина ...) -- 1 byte
eon - край на информацията за съответния сензор --- 1 byte
NodeID
....
....
...
eof - край на информацията на съобщението -- 1 byte
-------------------------------------------------------------------------------
Нещата предполагам не изглеждат много ясни, та ако има въпроси питайте.
We are drowning in information, but starving for knowledge and time!
-
13th December 2008 22:59 #14Registered User
Join Date: Dec:2003
Location: Burgas
Posts: 53
) Нека първо разбера какво се иска и тогава ще му мислим 
Ок, защо не пробвате ето това като идея.. Мерите в началото всички ребра по някаква извратена формула, която да определя теглото на реброто, след което .. строите минимално покриващо дърво на графа, който се получава (може да се ползва алгоритъм на крускал или прим). Така и сега идва триковата част, можете да правите така като имате изключени върхове, просто пазите 1 списък с ребрата и строите дървото от вече получените връзки.Тоест все едно затривате всички съществуващи ребра до изключените върхове и имате отново гора от покриващи дървета и започвате да ги свързвате. Може да ползвате само 1 връх, който да обработва информацията за структурата на дървото или няколко. Дефакто по този начин всеки път като правите дървото, ще имате N заявки от даденият връх до останалите и той ще пресмята дървото. Това ми се струва най-одачен вариант.Last edited by delian; 15th December 2008 at 10:07. Reason: сляти мнения
"Има само две безкрайни неща-Вселената и човешката глупост.Ама за вселената не съм сигурен." Алб.Аинщайн
-
15th December 2008 10:34 #15
Dinkeza, това беше първото нещо което ни хрумна да направим. Т.е. ние правим нещо подобно на Kruskal, но вместо да смятаме тежестта на ребрата, смятаме на колко сензора разстояние се намира базовата станция и свързваме новия сензор към реброто с най-малко Hops(т.е. най малкото разстояние като брой на хопове между него и базовата станция). По този начин правим възможно най-компактното дърво.
ПС Тук са фолията за утрешната презентация. Не са много подробни, тъй като трябва да не се казва всичко на конкуренцията, но ако ви е интересно може да хвърлите един поглед.We are drowning in information, but starving for knowledge and time!




Reply With Quote

Lenovo ThinkPad 15 или IdeaPad 15
5th May 2023, 22:16 in Мобилни компютри