کوتاهترین مسیر در شبکه های حسگر بیسیم

مسأله کوتاهترین مسیر در شبکه های حسگر بیسیم

 هدف این پروژه ارائه الگوریتمی است تا بتواند به نحوی بهینه پیامی را در یک شبکه حسگر بیسیم از مبدا به مقصد ارسال کند. بهینگی در این ارسال به معنای آن است که این پیغام از مسیری منتقل گردد که حاصل جمع مجموع تمام یال های در این مسیر نسبتا کوتاه باشد. ایده در این پروژه استفاده از اتوماتای سلولی برای حل این مساله می باشد.

علت انتخاب این مدل برای حل این مساله آن است که پردازش تمام حسگر ها و محاسبه فاصله تمام آن ها تا هر حسگر هزینه بر است. لذا پردازش باید به صورت محلی صورت گیرد. لذا الگوریتم زیر برای حل این مساله پیشنهاد می گردد.

ایده پروژه اول به این صورت است که برای مسیر یابی در شبکه های بیسیم به این صورت عمل شود.:

• ابتدا سلولار اتوماتا از نود مبدا آغاز به کار می کند .
• یکی از همسایه های خود را باید انتخاب کند تا پیام را بدین وسیله به مقصد برساند .
• از بین همسایه ها نودی را انتخاب می کند که هم از خود نود فاصله زیادی نداشته باشد و هم به مقصد نزدیک تر شده باشد.
• لذا برای انتخاب این نود از یک تابع بهینگی استفاده می کند که ضریبی خطی از فاصله هر یک از همسایه ها تا خود نود و همچنین از مقصد می باشد.
• این روند ۲تا۴ تا زمانی ادامه می یابد که یا پیام به مقصد برسد و یا تعداد جابجایی ها و یا کل طول مسیر به یک آستانه خاصی برسد.

کدنویسی پروژه

این پروژه به منظور پیاده سازی الگوریتم فوق با هدف پیدا کرذن مسیری نسبتا مناسب با زمان اجرای مطلوب به زبان Matlab  تهیه شده است. برای اجرای پروژه فوق کافی است script ای که با نام main.m در پوشه پروژه وجود دارد را با استفاده از برنامه matlab  به اجرا در آورید.

محتویات این فایل به شر ح زیر می باشد:

clc

clear

n=20;

p=.8;

Nodes=randi(20,n-2,2);

edges=(rand(n,n)<p);

start=[0,10];

goal=[20,10];

f=0;

maxrun=5;

k=0;

while f==0 &&  k<maxrun

    k=k+1;

    disp(['Run ' num2str(k)]);

plot(Nodes(:,1),Nodes(:,2),'.g')

hold on

plot(start(1),start(2),'*r')

plot(goal(1),goal(2),'*r')










for i=1:n

    edges(i,i)=0;

end

N=[start;Nodes;goal];

for i=1:n

    for j=1:i

        if edges(i,j)

            edges(j,i)=edges(i,j);

        plot([N(i,1),N(j,1)] ,[N(i,2),N(j,2)],'-')

        end

    end

end

plot(Nodes(:,1),Nodes(:,2),'.g')




axis ([-1 21 -1 21 ])

w=0;

flag=0;

current=1;%start

while w<n && flag==0

    w

    pause(.2)

    adj=find(edges(current,:));

    a=findBest(Distance(N(adj,:),start),Distance(N(adj,:),goal));

    %adj(a)

    edges(adj(a),current)=0;edges(current,adj(a))=0;

    plot([N(current,1),N(adj(a),1)] ,[N(current,2),N(adj(a),2)],'-r')

    drawnow

    current=adj(a);

    if current==n

        flag=1;

    end

    w=w+1;

end

if current==n

    disp('SUCCESSFULL')

    f=1;

else

    disp('NONSUCCESSFULL! TRY AGIAIN')

    disp('Next Run...')




end

hold off

end

متغیر n در اینجا نشان دهنده تعداد حسگر ها است و p پارامتری است که برای شبیه سازی استفاده شده و احتمال وجود یال را بین هر دو حسگر شبکه نشان می دهد. مقدار این متغیر بین صفر تا یک قابل تنظیم می باشد. هر چه این عدد به یک نزدیکتر باشد بیانگر آن است که حسگر های شبکه اتصالات بیشتری به هم دارند و هر چه عدد به صفر نزدیک تر باشد شبکه خلوت تری داریم.

در خط بعد حسگر ها به طور تصادفی با توزیع یکنواخت بر روی محیط شبیه سازی پخش تعریف می گردند و مکان مبدا و مقصد پیام تعیین می شود و سپس با توجه به پارامتر p  به طور تصادفی یال های موجود در شبکه ایجاد می شوند.

حال به حلقه اول می رسیم. این حلقه به این منظور طراحی شده است تا اگر در هر مرحله بعد از تعداد قدم های معین شده به هدف نرسیدیم، دو باره الگوریتم از اول تکرار شود تا مسیر جدیدی را بیابد و این تکرار تا زمانی که هنوز به maxrun نرسیده ایم ادامه پیدا می کند.

حسگر ها بر روی صفحه نمایش داده می شوند و محل مبدا و مقصد پیام نیز بر روی تصویر نمایش داده می شود.

در حلقه کوچک جدید نیز در صورت تعریف یال به صورت حلقه برای هر راس این حلقه حذف می گردد. چند دستور بعدی نیز به منظور رسم گرافیکی یال ها به صورت مناسب بر روی محیط شبیه سازی می باشد.

حلقه ای که در این قسمت با آن مواجه می شویم، حلقه اصلی برنامه است. این حلقه تا زمانی ادامه می یابد که یا به هدف رسیده ایم و یا تعداد حسگر های موجود در مسیر از تعداد کل حسگر ها بیشتر شده است و این شرط نشان می دهد که در حلقه افتاده ایم. متد های جلوگیری از افتادن در حلقه بسیار پیچیده اند و زمان اجرایی بسیار بالایی دارند لذا این استراتژی تا حد زیادی ما را از افتادن در حلقه دور می دارد و همچنین زمان اجرایی نسبتا مناسبی نیز دارد.

ابتدا همسایه های هر حسگر پیدا می شوند و سپس از بین این همسایه ها آن یک انتخاب می گردد که از همه بهتر باشد. ملاک بهتر بودن از یک تابع خطی به دست آمده که ایده اصلی الگوریتم را تشکیل می دهد. پیاده سازی انتخاب بهترین همسایه در یک تابع به نام findBest انجام گرفته است که در قسمت بعدی توضیح خواهیم داد. سپس پیام با استفاده از این یال به حسگر بعدی منتقل می گردد و در محیط نمایش نیز این یال با رنگ قرمز مشخص می گردد و سپس این روش یعنی پیدا کردن حسگر بعدی به همین منوال ادامه می یابد تا به مقصد برسیم. در صورتی که تا تعداد کام معینی به مقصد برسیم، برنامه این موفقیت را اعلام می کند و اگر نتوانیم تا این تعداد گام به مقصد برسیم، برنامه اعلام می کند که اجرا ناموفق بوده و اجرای جدید از نو آغاز می گردد.

در ادامه تابع findBest  را شرح می دهیم:

function [ I ] = finBest( d1,d2 )




% d1'

% d2'

a=1;

b=20;

D=a*d1+b*d2;

[m,I]=min(D);

I=I(1);

end

این تابع دو متغیر d1  و d2 را می گیرد. متغیر d1  فاصله هر نود تا بقیه حسگر ها را در خود دارد و d2 فاصله هر نود همسایه تا نود مقصد را نشان می دهد. a , b دو پارامتر این تابع هستند. در این تابع از بین همسایه ها آن یک انتخاب می گردد که با توجه به این دو پارامتر بهینه تر باشد. تابع بهینگی از ترکیبی خطی از این دو فاصله تشکیل شده است و دو پارامتر به ترتیب نشان دهنده اهمیت هر یک از این دو فاصله است.

تابع دیگری نیز که تعریف کرده ایم تابع Distance می باشد:

function [ d ] = Distance(N, s )

for i=1:size(N,1)

    d(i)=sqrt(sum((N(i)-s).^2));

end

%d

end

این تابع به ازای تمام نقاط موجود در مجموعه نقاط فاصله را تا نقطه s با روش فاصله اقلیدسی می یابد.

اجرای پروژه

شکل زیر نمایی از اجرای این پروژه است. ابتدا پیام در مبدا کار خود را آغار می کند و ارسال پیام با استراتژی که در بخش قبلی شرح داده شد، صورت می گیرد.

نکات قابل توجه به شرح زیر می باشد:

• با توجه به تصادفی بودن نقاط روی صفحه، جای حسگر ها و همچنین یال ها در هر بار اجرای الگوریتم با هم متفاوت است ولی در صورت ناموفق بودن اجرا در برنامه در صورت تکرار الگوریتم جایابی نقاط و یالها مانند تکرار قبل می باشد.
• استراتژی اتخاذ شده در عین جال که سرعت اجرایی بالایی (اردر زمانی کم) دارد، جواب های خوبی دارد و در اکثر موارد اجرا مسیر در همان اجرای اول پیدا می شود.
• با تغییر پارامتر های شبیه سازی مثل تعداد حسگر ها، احتمال وجود یال بین حسگرها و همچنین پارامتر های الگوریتم مانند ضرایب خطی موجود در تابع بهینگی اجرای برنامه را قبل مقایسه نمایید.

برای دریافت مشاوره با ما در تماس باشید: admin@matlab360.ir