چکيده— در شبکه های حسگر بیسیم (WSNs) اطلاعات میدانی (به عنوان مثال دما، رطوبت و جریان هوا) از طریق چندین حسگر بیسیم مجهز به باطری، کسب شده و در ادامه این اطلاعات به یک گره sink (مرکزی) بازپخش می شوند. با افزایش اندازه شبکه های حسگر بیسیم، گردآوری تمامی اطلاعات در قالب یک گره مرکزی (به لحاظ مصرف توان) از کارایی و بهره وری مناسبی برخوردار نخواهد بود. در راستای رفع این مشکل می توان تعداد گره های مرکزی را زیاد کرد. مجموعه گره های حسگر که در حال ارسال داده ها به گره مرکزی k می باشند؛ commodity یا آیتم k نامیده می شوند. در این مقاله به فرمول بندی مساله LOCL (زمان بقای بهینه آیتم به صورت ترتیبی -الفبایی) می پردازیم. در اینجا یک الگوریتم متمرکز و مرحله ای با نام الگوریتم LOCLپیشنهاد می گردد که می تواند راهکار مسیریابی بهینه را حاصل نموده و به ایجاد توازن ترتیبی میان زمان های بقای آیتم (commodity) منجر شود. سپس در ادامه نشان می دهیم که با در نظر گرفتن یکسری فرضیات معین می توان از طریق انجام بهینه سازی ترتیبی میان زمان های بقای گره، بهینه سازی زمان های بقای آیتم را حاصل نمود. این مساله ما را ترغیب مینماید که دومین الگوریتم خود را نیز پیشنهاد نماییم که الگوریتم LONL (زمان بقای گره بهینه به صورت ترتیبی) نامیده می شود. این الگوریتم برای پیاده سازی محلی مناسب می باشد. نتایج شبیه سازی نشان می دهند که الگوریتم های LOCL و LONL پیشنهاد شده توسط ما در مقایسه با الگوریتم مسیریابی MLMS ( حداکثر زمان بقا با وجود چندین گره مرکزی) و نیز الگوریتم مسیریابی LMM (تعادل حداکثری-حداقلی ترتیبی)، زمان های بقای استاندارد گره و آیتم (commodity) را افزایش می دهد.
کلمات کليدي بهینگی ترتیبی-الفبایی، چندین گره مرکزی، جریان مسیریابی، شبکه های حسگر بیسیم

Abstract:  In wireless sensor networks (WSNs), the field information (e.g., temperature, humidity, airflow) is acquired via several battery-equipped wireless sensors and is relayed toward a sink node. As the size of the WSNs increases, it becomes inefficient (in terms of power consumption) when gathering all information in a single sink. To tackle this problem, one can increase the number of sinks. The set of sensor nodes that are sending data to sink k is called commodity k. In this paper, we formulate the lexicographically optimal commodity lifetime (LOCL) routing problem. A stepwise centralized algorithm called the LOCL algorithm is proposed, which can obtain the optimal routing solution and lead to lexicographical fairness among commodity lifetimes. We then show that, under certain assumptions, the lexicographical optimality among commodity lifetimes can be achieved by providing lexicographical optimality among node lifetimes. This motivates us to propose our second algorithm, which is called the lexicographically optimal node lifetime (LONL) algorithm, which is suitable for practical implementation. Simulation results show that our proposed LOCL and LONL algorithms increase the normalized commodity and node lifetimes compared with the maximum lifetime with multiple sinks (MLMS) and lexicographical max–min fair (LMM) routing algorithms.
Keywords - Lexicographical optimality, multiple sinks, routing flow, wireless sensor networks (WSNs)