الگوریتم محلی برای تفکیک گره های حیاتی/غیرحیاتی در شبکه های ادهاک سیار و حسگر

الگوریتم محلی برای تفکیک گره های حیاتی/غیرحیاتی در شبکه های ادهاک سیار و حسگر

چکیده

تفکیک دقیق گره های حیاتی/غیرحیاتی متصل به مرکز یکی از کارهای مهم در شبکه های حسگر و ادهاک سیار برای ارزیابی آسیب پذیری شبکه در مقابل خطاهای گره های حیاتی و ارائه ابزارهای احتیاطی برای زنده ماندن است. در این مقاله یک الگوریتم محلی برای تفکیک گره های حیاتی/غیرحیاتی (LASCNN) ارائه شده است و از آن برای ایجاد تمایز میان گره های حیاتی/غیرحیاتی در اتصالات شبکه مبتنی بر اطلاعات توپولوژی محدود استفاده می شود. هر گره لیستی از اتصالات k گامی را ایجاد و نگه داری می کند و از LASCNN برای تعیین حیاتی/غیرحیاتی بودن آن استفاده می کند. LASCNN براساس این لیست، در صورتی گره را حیاتی تشخیص می دهد که همسایگان گره در k گام بدون وجود این گره غیرمتصل باشند، در غیراین صورت آن را غیرحیاتی تشخیص می دهد. آزمایشات شبیه سازی، مقیاس پذیری LASCNN را اثبات می کنند و کارایی آن در قیاس با طرح های اطلاعات شبکه سراسری مناسب است. دقت LASCNN در تعیین گره های حیاتی برابر ۸۷درصد (در یک گام) و ۹۸درصد (در ۲ گام) است و دقت آن برای تعیین گره های غیرحیاتی در یک گام برابر ۹۱ درصد و برای دو گام برابر ۹۳ درصد است.

کلمات کلیدی: شبکه های ادهاک سیار و حسگر، الگوریتم های توزیع شده و محلی، تفکیک، گره های حیاتی/غیرحیاتی

Localized Algorithm for Segregation of Critical/Non-critical  Nodes in Mobile Ad Hoc and Sensor Networks 

Abstract

Timely segregation of connectivity-centric critical/non-critical nodes is extremely crucial in mobile ad hoc and sensor networks to assess network vulnerabilities against critical node failures and provide precautionary means for  survivability. This paper presents a localized algorithm for segregation of critical/non-critical nodes (LASCNN) that  opts to distinguish critical/non-critical nodes to the network connectivity based on limited topology information. Each  node establishes and maintains a k-hop connection list and employ LASCNN to determine whether it is critical/non critical. Based on the list, LASCNN marks a node as critical if its k-hop neighbor’s become disconnected without the  node, non-critical otherwise. Simulation experiments demonstrate the scalability of LASCNN and shows the  performance is quite competitive compared to a scheme with global network information. The accuracy of LASCNN  in determining critical nodes is 87% (1-hop) and 93% (2-hop) and non-critical nodes 91% (1-hop) and 93% (2-hop).