view in publisher's site
- خانه
- لیست مقالات
- چکیده
Optimizing Sensor Placements in Water Distribution Systems Using Submodular Function Maximization
Drinking water distribution networks represent complex systems. Water flow rates in a water distribution system vary with time, with periodic features that reflect temporal variations in water demand by consumers. The intentional introduction of a contaminant disrupts the system and could theoretically be detected by a sensor or network of sensors placed at nodes (pipe junctions, reservoirs, storage tanks, or even individual consumer taps) in the system. Determining the best locations for placement of these sensors represents a significant research question, because the system has multiple states, the number of possible intrusion points is large, and the likely high cost of these sensors limits the number that can realistically be deployed. The optimal placement of these sensors to minimize the effect of an introduced contaminant on the population is a critical issue. Sensor placement for intrusion detection exhibits an important diminishing returns property: adding a sensor to a sensor network improves the detection ability less than adding it to a subset of the sensor network. We prove that this submodularity property holds for the objective functions that we consider for placing sensors, and exploit it by applying algorithms for maximizing monotonic submodular functions. Unlike existing optimization algorithms for selecting sensor placements, our efficient optimization procedure has strong theoretical performance guarantees. In spite of the problem's complexity, our algorithm is guaranteed to always find a solution that is at least within 63% of the optimum, and will often find a (near-) optimal solution. This method is applied to two hypothetical distribution systems (129 nodes and 12,527 nodes) to determine optimal sensor placements for a sensor network of 5 or 20 sensors. Optimization was based on multiple criteria including: (1) minimizing time to detection, (2) minimizing population affected prior to detection, (3) minimizing expected demand for contaminated water prior to detection, and (4) maximizing detection likelihood. A base scenario and three derivative scenarios were used to test the sensor location optimization for the hypothetical systems. In order to compute accurately the objective criteria, we exhaustively simulated all possible attack scenarios, using distributed computation. Five optimization objective functions were considered (i.e., optimization on each of the four objectives independently and then an equally weighted multi-objective optimization). The two networks analyzed in this project illustrate how a sensor network of 20 sensors is more than "adequate" for the example distribution system of 129 nodes, while a much larger sensor network would be needed for "adequate" detection in the example large network of 12,527 nodes. The developed algorithms generalize to networks of arbitrary size and can be constrained by expert knowledge or rankings of scenario likelihood. Further, the optimization algorithms have potential applications for placement of sensors in other complex, dynamic systems. This paper was presented at the 8th Annual Water Distribution Systems Analysis Symposium which was held with the generous support of Awwa Research Foundation (AwwaRF).
Optimizing سنسور لمسی در سیستم‌های توزیع آب با استفاده از تابع submodular تابع submodular
شبکه‌های توزیع آب آشامیدنی نشان‌دهنده سیستم‌های پیچیده هستند. نرخ جریان آب در یک سیستم توزیع آب با زمان تغییر می‌کند، با ویژگی‌های دوره‌ای که تغییرات زمانی در تقاضای آب توسط مصرف کنندگان را منعکس می‌کند. معرفی عمدی یک آلاینده، سیستم را مختل می‌کند و از لحاظ نظری می‌تواند توسط حسگر یا شبکه حسگر که در گره‌ها (اتصالات لوله، مخازن، مخازن ذخیره‌سازی، یا حتی taps مصرف منفرد)در سیستم قرار می‌گیرند، تشخیص داده شود. تعیین بهترین مکان‌ها برای قرار دادن این حسگرها نشان‌دهنده یک سوال تحقیقاتی مهم است، زیرا سیستم چندین ایالت دارد، تعداد نقاط نفوذ ممکن بزرگ است، و هزینه بالای این حسگرها، عددی را محدود می‌کند که می توان به طور واقع‌بینانه از آن‌ها استفاده کرد. جایابی بهینه این حسگرها برای به حداقل رساندن اثر یک آلاینده شناخته‌شده بر روی جمعیت یک مساله مهم است. یک حسگر به یک شبکه حسگر، توانایی تشخیص کم‌تر از اضافه کردن آن به زیرمجموعه‌ای از شبکه حسگر را بهبود می‌بخشد. ثابت می‌کنیم که این خاصیت submodularity برای توابع هدف صدق می‌کند که ما برای قرار دادن حسگرها در نظر می‌گیریم و با استفاده از الگوریتم ها برای حداکثر کردن توابع submodular یکنواخت از آن بهره‌برداری می‌کنیم. برخلاف الگوریتم های بهینه‌سازی موجود برای انتخاب محل‌های حسگر، روش بهینه‌سازی کارآمد ما تضمین عملکرد نظری قوی دارد. با وجود پیچیدگی محاسباتی، الگوریتم ما همیشه یک راه‌حل پیدا می‌کند که حداقل در ۶۳ % بهینه است و اغلب یک راه‌حل بهینه (نزدیک)پیدا می‌کند. این روش به دو سیستم توزیع فرضی (۱۲۹ گره و ۱۲،۵۲۷ گره)اعمال می‌شود تا محل استقرار سنسور بهینه را برای یک شبکه حسگر از ۵ یا ۲۰ حسگر مشخص کند. بهینه‌سازی مبتنی بر چندین معیار از جمله: ۱)کمینه‌سازی زمان برای تشخیص، (۲)کمینه‌سازی جمعیت تحت‌تاثیر قبل از تشخیص، (۳)به حداقل رساندن تقاضای مورد انتظار برای آب آلوده قبل از تشخیص، و (۴)به حداکثر رساندن احتمال تشخیص بود. یک سناریوی مبنا و سه سناریوی مشتق برای آزمایش بهینه‌سازی محل سنسور برای سیستم‌های فرضی مورد استفاده قرار گرفتند. برای محاسبه دقیق معیارهای عینی، ما همه سناریوهای حمله ممکن را با استفاده از محاسبه توزیع‌شده شبیه‌سازی کردیم. پنج تابع هدف بهینه‌سازی به عنوان مثال بهینه‌سازی روی هر یک از چهار هدف به طور مستقل و سپس یک بهینه‌سازی چند هدفه وزنی در نظر گرفته شدند. این دو شبکه در این پروژه تحلیل شده‌اند که نشان می‌دهند که چگونه یک شبکه حسگر از ۲۰ حسگر بیشتر از "کافی" برای سیستم توزیع نمونه ۱۲۹ گره است، در حالی که یک شبکه حسگر بسیار بزرگ‌تر برای "تشخیص کافی" در شبکه بزرگ گره‌های ۱۲،۵۲۷ مورد نیاز است. الگوریتم های توسعه‌یافته به شبکه‌هایی از اندازه دل‌خواه تعمیم داده می‌شوند و می‌توانند توسط دانش تخصصی یا رتبه‌بندی احتمال سناریو محدود شوند. علاوه بر این، الگوریتم های بهینه‌سازی کاربردهای بالقوه برای جایگذاری حسگرها در سایر سیستم‌های پیچیده، دینامیک دارند. این مقاله در هشتمین کنفرانس تحلیل سیستم‌های توزیع آب سالانه ارایه شد که با حمایت سخاوتمندانه بنیاد تحقیقات awwa (AwwaRF)برگزار شد.
ترجمه شده با 
ترجمه کنید