ترجمه طلایی خوشه صرفه جویی در انرژی در شبکه های حسگر بی سیم پر اتلاف

ترجمه طلایی خوشه صرفه جویی در انرژی در شبکه های حسگر بی سیم پر اتلاف

Energy-efficient clustering in lossy wireless sensor networks

اثبات. در آغاز الگوریتم خوشه­بندی k-هاپ، گره i یک پیام وزنی لینک به همسایه­های k-هاپ خود از جمله وزن لینک­های مجاورش ارسال می­کند. همچنین گره i باید پیام­های وزنی لینک را به همسایه­های k-هاپ باز پخش (ارسال مجدد) کند، زیرا یک پیام ارسالی تنها می­تواند به یکی از همسایه­های k-هاپ برسد. پس از دریافت پیام وزنی لینک از تمام گره­ها در nbr^k_i ، گره i می­تواند حداقل مسیر هزینه­ی انرژی را برای هر عضو در nbr^k_i محاسبه کند و سپس وزن انتخابی خود Wsel(i) را تعیین کند. پس از آن، گره i، وزن انتخابی خود را به همسایه­های k-هاپ ارسال می­کند. مشابه با پیام وزنی لینک، گره­های i باید پیام­های وزنی انتخابی را مجددا به گره­های nbr^k_i ارسال کند. در بدترین حالت، گره i لازم است پیام­های وزنی لینک برای هر گره را در nbr^k_i مجددا ارسال نماید. بنابراین، پیچیدگی پیام در پیش­فرایند برابر است با.

پس از دریافت پیام­های وزنی انتخابی از همه­ی همسایه­های k-هاپ، گره i اگر حداقل وزن انتخابی را داشته باشد، خودش را بعنوان یک سرخوشه اعلام می­کند. در غیر اینصورت، منتظر پیام­های اعلام از گره­های دیگر می­ماند و یک پیام مشارکتی برای پیوستن به خوشه را ارسال می­کند. بنابراین، گره i تنها یک پیام را در زمان شکل­گیری خوشه تولید خواهد نمود. مشابه با مرحله­ی پیش­پردازش، گره i احتمالا نیاز به بازپخش پیام­های اعلام و مشارکت برای همسایه­های k-هاپ خود داشته باشد. در بدترین حالت، گره i باید پیام­های تشکیل خوشه­ در هر گره را در nbr^k_i بازپخش کند. بنابراین، پیچیدگی پیام تشکیل خوشه برابر است با . به­طور خلاصه، پیچیدگی پیام خوشه­بندی k-هاپ برابر است با.

Proof. At the beginning of the k-hop clustering algorithm node i broadcasts a link weight message to its k-hop neighbors including the weight of its adjacent links. Node i also has to rebroadcast link weight messages for its k-hop neighbors as a broadcast message can only reach one-hop neighbors. After receiving the link weight message from all nodes in nbrki node i can calculate the minimum energy cost path to each member in nbrki and then determine its selection weight Wsel(i). After that node i broadcasts its selection weight to its k-hop neighbors. Similar to the link weight message node i also has to rebroadcast selection weight messages for nodes in nbrki. In the worst case node i needs to rebroadcast the link weight and selection weight messages for each node in nbrki. Therefore the message complexity during the pre-process is
O(2(|nbrki| + 1)).

5.4. مسائل و مباحث اجرائی

یک روش، پخش پیام سلام در هر گره در دوره­های معین، یعنی در یک دوره tاست. یک گره حسگر شروع به پخش پیام­های سلام در یک زمان تصادفی می­کند و این را در یک فرکانس پایین تکرار می­کند؛ بنابراین منطقی است فرض کنیم که احتمال برخورد پیام­های سلام نزدیک به صفر است.