Abstract
A routing problem in static wireless ad hoc networks is considered as it arises in a rapidly deployed, sensor based, monitoring system known as the wireless sensor network. Information obtained by the monitoring nodes needs to be routed to a set of designated gateway nodes. In these networks, every node is capable of sensing, data processing, and communication, and operates on its limited amount of battery energy consumed mostly in transmission and reception at its radio transceiver. If we assume that the transmitter power level can be adjusted to use the minimum energy required to reach the intended next hop receiver then the energy consumption rate per unit information transmission depends on the choice of the next hop node, i.e., the routing decision. We formulate the routing problem as a linear programming problem, where the objective is to maximize the network lifetime, which is equivalent to the time until the network partition due to battery outage. Two different models are considered for the information-generation processes. One assumes constant rates and the other assumes an arbitrary process. A shortest cost path routing algorithm is proposed which uses link costs that reflect both the communication energy consumption rates and the residual energy levels at the two end nodes. The algorithm is amenable to distributed implementation. Simulation results with both information-generation process models show that the proposed algorithm can achieve network lifetime that is very close to the optimal network lifetime obtained by solving the linear programming problem
چکیده
مسئله‌ی مسیریابی در شبکه‌های اد هاک بی‌سیم و ایستا را می‌توان به عنوان مسئله‌ای در نظر گرفت که در یک سیستمِ مانیتورینگ مبتنی بر حسگر و سریعاً توسعه یافته - تحت عنوان شبکه‌ی حسگر بی‌سیم - رخ می‌دهد. اطلاعاتی که به وسیله‌ی گره‌های مانیتورینگِ مستقر در این شبکه‌ها به دست می‌آید را باید به سمت مجموعه‌ای از گره‌های درگاه مسیریابی و هدایت کرد. در این شبکه، هر گره تواناییِ حس، پردازش داده‌ها و محاوره را داشته که البته انجام این کارها محدود به انرژیِ مصرفی باتری این گره‌ها برای انتقال و دریافت داده‌ها و انرژی مصرفی در فرستنده/گیرنده‌ی این گره‌ها می‌باشد. در صورتی که فرض کنیم که سطح انرژی گرهی فرستنده را می‌توان به طوری تنظیم کرد که از حداقل میزان انرژی برای رساندن داده‌ها به گیرنده‌ی هاپ بعدی برخوردار باشد، از این رو نسبت مصرف انرژی به ازای انتقال هر واحد اطلاعات، بسته به انتخاب گرهی بعدی دارد که این خود یک تصمیم مسیریابی می‌باشد. ما اقدام به تدوین مسئله‌ی مسیریابی به عنوان یک مسئله‌ی برنامه‌ریزی خطی نموده‌ایم که در این مسئله، هدف بیشینه‌سازی طول عمر شبکه می‌باشد، یعنی بیشینه‌سازی زمانی که شبکه می‌تواند تا زمان تخلیه‌ی باتری به کار خود ادامه دهد. دو مدل متفاوت را برای فرآیندهای تولید اطلاعات در نظر گرفته‌ایم. در یک مدل، نسبت‌های ثابتی برای تولید اطلاعات مفروض بوده و در مدل دیگر از فرآیندهای تولید اطلاعات به صورت دلخواه استفاده می‌شود. یک الگوریتم مسیریابی با کمترین هزینه نیز پیشنهاد گردیده است که این الگوریتم، از هزینه‌های لینک برای انعکاس مصرف انرژی ارتباطی و سطوح انرژی مانده در دو گره ی پایانی استفاده می‌کند. این الگوریتم را می‌توان به صورت توزیع شده پیاده سازی کرد. نتایج شبیه‌سازی به همراه هر دو مدل تولید اطلاعات نشان می‌دهد که الگوریتم پیشنهادی می‌تواند به طول عمر شبکه‌ای که بسیار نزدیک به طول عمر بهینه‌ی شبکه‌ی حاصل از حل مسئله‌ی برنامه‌ریزی خطی می‌باشد، دست پیدا کند.
1-مقدمه
یک شبکه‌ی حسگر بی‌سیم متشکل از گره‌های ایستا که به صورت پراکنده توزیع شده‌اند را در نظر بگیرید ( شکل 1) که در آن، هر گره بر اساس انرژی باتری مصرفی خود برای انتقال و دریافت داده‌ها در سمت فرستنده و گیرنده‌ی رادیوئی خود عمل می‌کند. فرض کنید که در هر گره، یک سری از اطلاعاتی ایجاد شده و این اطلاعات را باید به مجموعه‌ای از گره‌های درگاه که به احتمال از چندین هاپ استفاده می‌کنند تحویل داد...