بخشی از مقاله
کاربرد داده ساختارهای جنبشی در مسيريابی شبکههای حسگر متحرک
چكيده
يکی از موضوعات مطرح در طراحی الگوريتم‌ها بحث شبکههای حسگر می‌باشد. اين شبکه‌ها متشکل از مجموعه‌ای از واحدهای متحرک و مستقل از هم با توان مصرفی و پردازشی محدود است که از طريق فرستنده‌های راديويی با يکديگر در ارتباطند و اقدام به جمع‌آوری اطلاعات می‌نمايند. مساله‌ی مسيريابی در
اين شبکه‌ها به گونه‌ای که حداقل انرژی مصرف شود، از دسته مسائل غير چند جمله‌ای سخت می‌باشد که ارائه راه حل‌های تقريبی مناسب موضوع برخي از تحقيقات در اين زمينه است. در بيشتر مدل‌های ارائه شده فرض بر ثابت بودن حسگرها است؛ در اين مقاله سعی می‌شود الگوريتمی برای مسيريابی در شبکه‌ی حسگرهای متحرک ارائه شود. با توجه به ماهيت جنبشی اين شبکه‌ها ، استفاده از داده ساختارهايي که بتواند ساختار زير درخت فراگير را به صورت
بهينه نگاهداری نمايند بسيار سودمند است. در اين تحقيق از داده ساختار جنبشی برای نگاهداری زير درخت فراگير استفاده شده است. در اين مقاله اين روش ارايه و بررسی می‌شود و نشان می‌دهيم که باعث کاهش پيچيدگی محاسباتی مسيريابی در اين شبکه‌ها می‌شود.
كلمات كليدي
الگوريتم، شبکههای حسگر، مسيريابی، داده ساختارهای جنبشی، کوچکترين زير درخت فراگير محلی
Kinetic Data Structures for Routing Problem in Mobile Sensor Networks
Kamyar Rafati, Naeem Esfahani, Mohammad Ghodsi
Abstract
“Sensor networks” is an important topic in computer science and algorithm design. These networks are constructed from a set of independent mobile units with limited power and process capability. These units communicate and gather information using radio transmitters. The problem of routing in these networks with minimum power consumption is a NP-hard problem. Therefore, many researches use approximation algorithms for this problem. Most of the proposed models work with fixed sensors. In this paper, we propose an algorithm for routing in mobile sensor networks. According to the inherent kinetic structure of such networks, the use of a kinetic data structure which efficiently maintains minimum spanning tree (MST) is useful. In this paper, we present such structure for our problem and show that this method reduces the time complexity of routing in sensor networks.
Keywords
Algorithm, Sensor Networks, Routing, Kinetic Data Structures, Minimum Spanning Trees
1- مقدمه
با ظهور ارتباطات بی¬سيم بين عناصر مختلف و به دنبال آن مسئله شبکه¬های بی سيم و متحرک، توجه بسياری از انديشمندان رشته علوم کامپيوتر به مسائل موجود در اين شبکه از قبيل مسيريابی معطوف شد. اما اين شبکه¬ها پاسخگوی تمام نيازها در زمينه ارتباطات بی سيم نبودند. به همين منظور مدل شبکه¬های ويژه ارائه شد که در آنها ارتباطات از طريق فرستنده¬ها و گيرنده¬های راديويي با فاصله ارتباطی محدود انجام می¬گرفت و در ضمن ساختار
يکپارچه مرکزی برای مسيريابی و مديريت ندارند. در قدم بعدی محدوديت توان مصرفی و عملياتی نيز به مدل فوق افزوده شد و مدل شبکه حسگر معرفی شد.
شبکه های حسگر کاربرد بسيار وسيعی دارند. مثلا حسگرهای تشخيص آتش سوزی در يک جنگل و يا شهر همچنين حسگرهای تشخيص تشعشعات هسته¬ای در يک رآکتور هسته¬ای، نمونه¬هايي از اين کاربردها هستند.
ويژگي¬های شبکه¬های حسگر را می¬توان به اجمال به اين موارد تقسيم نمود: 1. انرژی محدود عناصر .2. پهنای باند محدود .3. شبکه بدون ساختار و متغير با زمان .4. کيفيت پايين ارتباطات .5. قدرت محاسبات محدود در عناصر.
از جمله مسائل مطرح در زمينه شبکه¬های حسگر، بحث مسيريابی در اين شبکه¬ها است. الگوريتم¬های متفاوتی برای اين مسئله ارائه شده است. الگوريتم¬های ارائه شده را می¬توان به دو دسته همگن و ناهمگن تقسيم نمود. الگوريتم¬¬های همگن فرض را بر يکسان بودن عناصر شبکه (از نظر برد فرستنده) می¬گذارند. الگوريتم¬های ناهمگن از انعطاف¬پذيری بيشتری برخوردار هستند. الگوريتم¬های ناهمگن با توجه به اطلاعاتی استفاده می¬کنند به سه دسته تقسيم می¬شوند. 1- بر مبنای محل : در آنها محل دقيق عناصر مشخص می¬باشد. 2- بر مبنای جهت : در آنها فرض می¬شود که هر کس جهت نسبی همسايگانش را نسبت به خود می¬داند. 3- بر مبنای همسايه : در آنها فرض می¬شود که شناسه همسايه¬ها در اختيار است.
الگوريتم¬های ارائه شده را از يک منظر ديگر می¬توان به دو دسته متمرکز و نامتمرکز نيز تقسيم نمود. در الگوريتم¬های متمرکز، يک ناظر خارجی در سيستم وجود دارد که مسئوليت مسيريابی را به عهده دارد. البته فرض وجود چنين ناظری اولا با ماهيت شبکه-های حسگر سازگار نيست در ضمن قابليت مقياس¬پذيری ندارد.
از جمله روش¬های رايج در زمينه مسيريابی استفاده از درخت فراگير کمينه است. اما به دو دليل که در ادامه خواهيم ديد، استفاده از آنها در اين شبکه¬ها محبوبيت پيدا نکرده است. اولا پيدا کردن کوچکترين درخت فراگير يک الگوريتم ماهيتا متمرکز است و دوما به علت آنکه هزينه ساخت آن بالاست و در اين شبکه¬ها - به علت متحرک بودن عناصر - نياز است که مرتبا اين درخت ساخته شود.
در اين مقاله يک الگوريتم برای مسيريابی در شبکه¬های حسگر بر مبنای کوچکترين درخت فراگير ارائه می¬شود ولی سعی شده که مشکلات ذکر شده در بالا در آن پاسخ داده شود. برای اين منظور اولا از کوچکترين درخت فراگير محلی استفاده شده است که نياز ناظر را از بين می¬برد و همچنين از يک ساختار جنبشی برای نگهداری آن استفاده می¬شود که مشکل هزينه تغييرات را از بين می¬برد.
در زمينه مسيريابی در شبکه¬های حسگر کارهای گوناگونی انجام شده است ولی در تمام آنها فرض بر ثابت بودن ساختار شبکه در طول حيات شبکه است. همچنين داده ساختارهای گوناگونی برای نگاهداری اجزای شبکه مطرح شده است ولی اکثر آنها هزينه به روز رسانی بالايي دارند و همچنين برای مسئله
مسيريابی مناسب نيستند. لذا در اين مقاله تلاش شد تا فرض¬های مطرح شده بسيار به محيط واقعی شبيه باشند که تا زمان نوشتن اين مقاله کاری با اين درجه شباهت با محيط واقعی پيدا نکرديم. نتيجه حاصل نيز هزينه نگاهداری و به روز رسانی کمينه¬ای دارد که برای حسگر های با انرژی محدود مناسب است.
در بخش¬های بعدی ابتدا يک الگوريتم برای کوچکترين درخت فراگير محلی ارائه می¬شود. سپس يک روش جنبشی برای نگهداری کوچکترين درخت فراگير ارائه می¬شود. در ادامه الگوريتم اصلی که ترکيبی از اين دو روش است معرفی می-شود و بعضی خواص آن اثبات می¬شود . در انتها پيچيدگی الگوريتم و نتيجه-گيری آورده شده ¬است.
2- کوچکترين درخت فراگير محلی
در اين قسمت روشی برای ساخت کوچکترين زير درخت فراگير به صورت محلی ارائه می¬شود. ايده اصلی از روش ارائه شده توسط لی و همکارانش [1] گرفته شده است.
الگوريتم ساخت اين درخت در دو فاز انجام می¬شود. در مرحله اول اطلاعات بين عناصر شبکه تبادل می¬شود و در مرحله دوم هر عنصر به صورت مجزا کوچکترين زير درخت فراگير را برای خود می¬سازد. در ادامه هر يک از دو فاز را به تفضيل شرح می¬دهيم.
فاز تبادل اطلاعات : در اين فاز همانند مدل بردار فاصله در مسيريابی درون دامنه¬ای عمل می¬شود. به اين صورت که هر عنصر در شبکه اطلاعات خود را از تمام عناصر شبکه به صورت يک بردار فاصله به همسايگانش می فرستد. به علت اينکه عناصر از وجود تمام عناصر ديگر آگاه نيستند استفاده از شناسه الزامی است. پس از اتمام اين فاز ، تمام عناصر و يا گره‌های شبکه ، اطلاعات کل شبکه را در اختيار دارند.
فاز ساخت کوچکترين زير درخت فراگير : در اين فاز ، همانند فاز دوم در روش ارائه شده توسط لی و همکارانش [1] ، هر گره با استفاده از الگوريتمی مانند پريم [4] کوچکترين زير درخت فراگير را می سازد. در الگوريتم پريم درخت حاصل يکتا نيست زيرا در مواردی که فاصله دو گره از يک گره يکسان باشد به صورت اتفاقی يکی از آنها انتخاب می¬شود. ولی به منظور اينکه تمام عناصر ديد يکسانی از اين درخت داشته باشند ، ما تابع فاصله را به صورت زير تغيير داده¬ايم تا هميشه درخت يکتايي توليد شود.
که در آن برابر فاصله راس از راس است. در انتهای اين فاز هر عنصر يک درخت فراگير دارد که در تمام گره¬های مختلف شبکه يکسان هستند و در حقيقت روی آن توافق شده است. در صورتی که عناصر شبکه در يک صفحه باشند اثبات می شود که بزرگترين درجه راس¬های درخت حداکثر 6 می¬شود. اين نکته باعث کاهش قابل توجهی از انرژی مصرفی هر گره می¬شود.
تا اين مرحله هر گره ، کوچکترين زير درخت فراگير لازم برای مسيريابی را ساخته است. در بخش بعد روشی برای نگهداری بهينه اين درخت در موارد وجود حرکت و يا حذف و ايجاد گره¬های جديد با کمک يک داده ساختار جنبشی ارائه می¬شود.
3- کوچکترين درخت فراگير پارامتری و جنبشی
برای مدل کردن ساختار جنبشی گره‌ها می‌توان روشهای مختلفی را پيش گرفت. در ابتدايی‌ترين حالت می‌توان فرض کرد معادله‌ی حرکت گره‌ها دقيقا مشخص است و بر پايه‌ی آن داده ساختار مساله را حل کرد. مشکل اين روش اين است که اولا معادله‌ی حرکت يک گره ممکن است بسيار پيچيده باشد و بدست آوردن اطلاعات لازم از آن کار ساده‌ای نباشد؛ دوما ماهيت معادله‌ی حرکت يک گره يک مفهوم پيوسته است و برای ما مناسب‌تر است اگر بتوانيم آن را به صورت يک مفهوم گسسته مدل کنيم. بنابراين از مدل معرفی شده توسط آگاروال و همکارانش [2] استفاده می‌کنيم که در آن به جای در نظر گرفتن معادله‌ی حرکت يک گره، تغييرات وزن يک يال را داريم و آن را يک تابع خطی در نظر می‌گيريم و برای گسسته کردن اين تابع از رابطه‌ی برای يال استفاده می‌کنيم. در اين تابع دو عدد و دو عدد حقيقی هستند و به عنوان يک پارامتر گسسته تغيير کرده و باعث تغيير وزن يال‌ها می‌شود. به طور کلی دو دسته الگوريتم جنبشی برای حل مساله‌ی کوچکترين درخت فراگير داريم که هر کدام را می‌توان با ديگری شبيه‌سازی نمود:
• الگوريتم جنبشی ساختاری: که در آن يال‌ها اضافه و حذف می‌شوند و تغيير وزن را با حذف و اضافه کردن يال شبيه‌سازی می‌کنيم.
• الگوريتم جنبشی تابعی: که توانايی تغيير وزن يال‌ها را دارد و اضافه و حذف يال‌ها را با استفاده از يک عدد بسيار بزرگ به عنوان وزن يال حذف شده شبيه‌سازی می‌کند.
يکی از تکنيک‌هايی که در اين روش استفاده می‌شود روش تنک کردن است که عملا روش تقسيم و حل می‌باشد. در اين روش گراف را به صورت بازگشتی به تعدادی دسته تقسيم می‌کنيم. نکته‌ای اين تقسيم بندی‌ها دارند اين است که درخت نهايی حاصل از گراف به راحتی از کنار هم قرار دادن جواب‌های زير درخت‌ها حاصل از زير گراف‌ها بدست می‌آيد. اپستين و همکارانش [7] نشان دادند که اين عمل نتيجه‌ی درستی می‌دهد. فرناندز و همکارانش [8] نيز نشان دادند که اين روش برای مساله‌ی پارامتری نيز درست کار می‌کند و هزينه‌ی آن را نيز محاسبه کردند.
نقطه‌ی عطف اين روش مطرح کردن ايده‌های هندسه‌ی محاسباتی در کاربرد تئوری گراف‌هاست؛ نشان داده می‌شود که می‌توان اطلاعات مربوط به گره‌ها را توسط پوش محدب نگهداری کرد؛ به اين ترتيب که با توجه به دسته‌بندی که انجام می‌شود، مجموعه‌هايی داريم که برای داشتن درخت فراگير بايد يکی از يال‌ها را انتخاب و حذف کرد. اگر در اين انتخاب بزرگترين عنصر مجموعه را حذف کنيم درخت ما کمينه خواهد بود. در اين‌جا جنبش باعث می‌شود که اين بزرگترين
عنصر با تغيير که حاصل از جنبش است عوض شود و برای داشتن کوچکترين درخت فراگير مجبور به تعويض يال شويم. با استفاده از پوش محدب می‌توانيم در زمان بزرگترين يال جديد را پيدا کنيم و جای يال قبلی را با آن عوض کنيم. روند کار به اين ترتيب است که با استفاده از تبديل هو [Hough59] معادله‌ی وزن يال‌ها بر اساس را تبديل به نقاط می‌کنيم. در مساله‌ی دوگان بدست آمده خطی که بر دو پوش محدب مماس می‌شود مشخص می‌کند کدام دو خط بايد جابجا شوند. اين دو نقطه‌ی پيدا شده در عمل نشان دهنده‌ی بيش‌ترين رشد وزن در يال‌هايی که در درخت هستند و بيش‌ترين کاهش وزن در يال‌هايی که در درخت نيستند می‌باشند و اگر قرار باشد جای دو يال عوض شود بايد اين دو يال باشند. دو يال می‌توانند در جابجايی روابط زير را با هم داشته باشند:
• جابجايی درون افرازی: هر دو در يک افراز هستند.
• جابجايی افراز دوگان: يالی که روی درخت فراگير کمينه بود -بايد حذف شود- در يکی از افرازهايی است که يک سر يال ديگر در آن است.
• جابجايی بين افرازی: دو يال رابطه‌های بالا را با هم ندارند.
به طور کلی با اضافه کردن راس می‌توانيم کاری کنيم که يک گراف فقط شامل راس‌هايی با درجه‌ی 3 يا 1 باشد و عملا حالت دودويی داشته باشد. برای گراف داده شده هم اين کار را انجام می‌دهيم . سپس برای جلوگيری از گسترش اطلاعات مربوط به تغيير مکان يک گره در کل گراف، اقدام به افراز گره‌ها می‌کنيم. و با توجه به رابطه‌ی دو يال که با هم عوض می‌شوند، اقدام در جهت بروز رسانی درخت می‌نماييم. افراز انجام شده باعث می‌شود که تغييرات حتی‌الامکان محلی باقی بمانند و از حدی که لازم نيست فراتر نروند.
4- کوچکترين درخت فراگير محلی با نگهداری به کمک داده ساختار جنبشی
در دو بخش قبل ، روش¬هايي برای ساخت کوچکترين زير درخت فراگير محلی و همچنين ساختاری جنبشی برای نگاهداری کوچکترين زير درخت فراگير آشنا معرفی شدند. متاسفانه هيچ کدام از اين روش¬ها برای شبکه¬های حسگر مناسب نيستند. کوچکترين زير درخت فراگير محلی به علت تغييرات زياد در محل عناصر شبکه حسگر هزينه بسيار بالايي را ، هم از نظر انرژی و هم از نظر پيغام-های رد و بدل شده ، دارد. در مقابل داده ساختار جنبشی ارائه شده نيز با وجود اينکه هزينه به روز رسانی مناسبی دارد ولی به علت اينکه محلی نيست لذا بايستی که تغييرات آن در همه سيستم منعکس شود که نيازمند ارتباطات بسيار زيادی در شبکه می-باشد.
در اين بخش مدلی ارائه می¬شود که در آن سعی شده است که از مزايای هر دو روش فوق استفاده شود و مدلی مناسب برای ساخت و نگاهداری کوچکترين زير درخت فراگير در شبکه¬های حسگر ارائه شود.
اين الگوريتم در دو مرحله انجام می شود. در مرحله اول به کمک الگوريتم محلی داده شده در بخش 2 تمام گره¬های شبکه يک زير درخت فراگير ايجاد می¬کنند. نکته قابل توجه اين است که در پايان اين مرحله تمام عناصر شبکه ديد يکسانی از شبکه دارند. در مرحله دوم هر گره به کمک داده ساختار ارائه شده در بخش 3 ، اين درخت ايجاد شده را در صورت بروز تغييرات به روز می¬کند. سپس تغييرات منتشر می¬شود. نکته قابل توجه اين است که اين تغييرات فقط به گره¬هايي ارسال می¬شود که در درخت فراگير ، حداقل يکی از گره¬های مجاور آن تغيير کرده باشد يعنی يالی از آن حذف شده باشد و يا اينکه يال جديدی به آن وارد شده باشد. در ادامه اين دو مرحله را بيشتر شرح می-دهيم.
در مرحله اول ، ابتدا اطلاعات مانند روش بردار فاصله در مسيريابی درون دامنه¬ای تبادل می¬شود تا تمام گره¬ها ، اطلاعات تمام عناصر شبکه را جمع آوری کنند. سپس با تابع فاصله تعريف شده در بخش 2 ، کوچکترين زير درخت فراگير را ايجاد می¬کنند که همان طور که گفته شد يکتا است.
مرحله دوم که در حقيقت مرحله نگاهداری از درخت فراگير ايجاد شده است ، هر گره به کمک ساختار جنبشی بخش 3 درخت خود را به روز نگاه می-دارد و در صورت نياز همسايگان خود را از تغييرات درخت مطلع می¬سازد. در اين مرحله هر گره با داشتن محل و جهت حرکت و سرعت خود و همچنين محل و جهت
حرکت و سرعت همسايگان خود ، می¬تواند زمان دقيق تغيير در درخت فراگير را محاسبه نمايد و در صف وقايع خود قرار دهد. در هنگام ايجاد تغيير ، گره¬هايي که آن تغيير را در صف وقايع خود دارند ابتدا درخت خود را به روز می¬کنند. سپس نوبت به آن می¬رسد که تغييرات را به ساير گره¬ها اطلاع دهند. در صورتی که قرار باشد که تمام گره¬ها از اين موضوع مطلع شوند ، الگوريتم محلی بودن خود را از دست می¬دهد و به يک الگوريتم غير محلی تبديل می¬شود. برای
حفظ محلی بودن الگوريتم هر گره که درخت فراگير آن به روز شده است تغييرات را فقط برای گره¬هايي می فرستد که يال¬های تغيير کرده در بيش از يکی از زير درخت¬های آن در زير درخت فراگير باشد. در اين صورت انتشار تغييرات محدود به قسمت¬هايي است که تغييراتی در آنها رخ داده است و ساير گره¬ها در بخش¬های بدون تغيير ساختاری ، مطلع نخواهند بود.
نکته مهم در مورد مرحله دوم اين است که چون تغييرات به صورت محلی منتشر می¬شود لذا بعد از مدتی گره¬های شبکه ، کوچکترين زير درخت فراگير متفاوتی از شبکه خواهند داشت و ديگر يکتايي که در مرحله اول وجود داشت رعايت نمی¬شود. بنابراين بايد نشان دهيم که با وجود اين ديدهای متفاوت ، همچنان خواص اصلی حفظ می¬شود. در ادامه لمی بيان می¬شود که در آن اثبات می¬کنيم که با وجود اين ديدهای غير يکسان همچنان بسته¬ها روی مسيرهای کوچکترين درخت فراگير حرکت می¬کنند..
لم: اگر برای فرستادن هر بسته ، هر گره آن بسته را به گره بعد از خود در مسير بين خود و مقصد در درخت فراگير تحويل دهد آنگاه بسته حتما روی مسير موجود در کوچکترين زير درخت فراگير کل شبکه حرکت خواهد کرد.
اثبات: فرض می¬کنيم که بسته¬ای است که روی مسير بهينه خود روی درخت فراگير کلی حرکت نکرده است و گره اولين گره¬ای است که آن را در مسير حرکت خود اشتباه هدايت کرده است. گره¬ای که بسته را به آن هدايت کرده است را می¬ناميم و گره¬ای که در درخت کلی بعد از قرار دارد را می¬ناميم. زمان را زمانی در نظر می¬گيريم که گره از مسير درخت اصلی خارج شده است و جايگزين آن شده است. چون که يال¬های گره تغيير کرده است پس با توجه به الگوريتم حتما بايد تغييرات به آن نيز اطلاع داده می¬شد. پس فرض وجود راس اشتباه است و هميشه بسته روی مسير اصلی منتقل می-شود.
بنابر لم فوق الگوريتم ما هميشه بسته¬ها را از مسير بهينه کوچکترين زير درخت فراگير عبور می دهد.
5- پيچيدگی الگوريتم
اين الگوريتم همان طور که در بخش قبل گفته شد از دو مرحله تشکيل شده است. در اين بخش پيچيدگی هر يک را به صورت جداگانه بررسی می کنيم.
در فاز پخش اطلاعات در مرحله اول همان طور که گفته شد به کمک الگوريتم بردار فاصله تمام گره¬ها ساختار درخت فراگير را در خود ايجاد می¬کنند. اين عمل نيازمند جابجايی تعداد زيادی پيغام است و در نتيجه کارآيي بالايي ندارد. اما نکته مهم اين است که اين مرحله تنها يک بار و در ابتدای کار شبکه انجام می¬شود و در ساير مراحل ديگر تکرار نمی¬شود. سپس هر گره به کمک الگوريتم پريم کوچکترين زير درخت فراگير را با هزينه محاسبه می¬کند.
در مرحله دوم بايستی که ساختار درخت در مقابل تغييرات روی داده حفظ شود. اثبات شده است که الگوريتم بخش 3 می¬تواند يک گراف را با يال را به کمک ساختار جنبشی با هزينه ، که در آن برابر تعداد افزوده شدن يال و يا حذف يال و يا تغيير حاصل در ساختار درخت است ، نگاهداری کند. همچنين اثبات می¬شود که اگر از تکنيک تصادفی کردن استفاده شود هزينه برابر می¬شود. اما نکته مهم در مورد اين الگوريتم ، هزينه پايين انتشار تغييرات است که چون محلی عمل می¬شود بسيار اندک می¬باشد.
6- نتيجه
در اين مقاله يک الگوريتم جنبشی و در عين حال محلی برای ساخت و نگاهداری کوچکترين زير درخت فراگير ارائه شده است. اين دو ويژگي ، اين الگوريتم را برای مسئله مسيريابی در شبکه¬های حسگر مناسب می¬نمايد. همچنين اثبات شده است که با وجود اينکه گره¬های مختلف با گذشت زمان ديد يکسانی از کل شبکه ندارند ولی باز هم بسته¬ها در مسير بهينه کوچکترين درخت فراگير کلی حرکت می¬کنند.
به نظر می رسد که مرحله اول انتشار ساختار شبکه که فعلا به کمک الگوريتم بردار فاصله انجام می¬شود می¬تواند به کمک الگوريتم¬های با تعداد پيغام کمتر جايگزين شود که می-تواند در آينده توسعه¬ای بر مدل کنونی باشد. همچنين يافتن الگوريتم¬های جنبشی مناسب¬تر نيز می تواند به عنوان کارهای بعدی انجام پذيرد.
مراجع
[1] P. Santi, Topology control in wireless ad hoc and sensor networks, ACM Computer Survey 37, 2 (Jun. 2005), 164-194.
[2] P. K. Agarwal, D. Eppstein, , L. J. Guibas, M. R. Henzinger, Parametric and Kinetic Minimum Spanning Trees, In Proceedings of the 39th Annual Symposium on Foundations of Computer Science (November 08 - 11, 1998), FOCS IEEE Computer Society, Washington, DC, 596.
[3] N. Li, J. C. Hou, L. Sha, Design and analysis of an MST-based topology control algorithm, in Proceedings of the IEEE Infocom 2003.
[4] R. Prim, Shortest connection networks and some generalizations, The Bell System Technical Journal, vol. 36, pp. 1389–1401, 1957.
[5] W. Baek, David S. L. Wei, C. C. Jay Kuo, Power-Aware Topology Control for Wireless Ad-Hoc Networks, IEEE SECON 2005.
[6] C. Gentile and R.E. VanDyck, Kinetic Spanning Trees for Minimum Power Routing in MANETs, IEEE VTC Spring, Birmingham, AL., May 2002.
[7] D. Eppstein, Z. Galil, G. F. Italiano, A. Nissenzweig, Sparsification - A technique for speeding up dynamic 11 graph algorithms, Journal of ACM, 44(1):669--696, 1997.
[8] D. Fernandez-Baca, G. Slutzki, and D. Eppstein, Using sparsification for parametric minimum spanning tree problems, Proc. 5th Scand. Workshop Algorithm Theory. Springer-Verlag, Lecture Notes in Computer Science 1097, July 1996.
زير‌نويس‌ها
