Luận văn Nghiên cứu giải thuật định tuyến cân bằng tải nhằm nâng cao tuổi thọ cho mạng cảm biến không dây (Phần 1)

Nội dung text: Luận văn Nghiên cứu giải thuật định tuyến cân bằng tải nhằm nâng cao tuổi thọ cho mạng cảm biến không dây (Phần 1)

1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH LUẬN VĂN THẠC SĨ NGUYỄN THỊ THU TRANG NGHIÊN CỨU GIẢI THUẬT ĐỊNH TUYẾN CÂN BẰNG TẢI NHẰM NÂNG CAO TUỔI THỌ CHO MẠNG CẢM BIẾN KHÔNG DÂY NGÀNH: KỸ THUẬT ĐIỆN TỬ - 60520203 S K C0 0 4 6 0 8 Tp. Hồ Chí Minh, tháng 10/2015
2. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH LUẬN VĂN THẠC SĨ NGUYỄN THỊ THU TRANG NGHIÊN CỨU GIẢI THUẬT ĐỊNH TUYẾN CÂN BẰNG TẢI NHẰM NÂNG CAO TUỔI THỌ CHO MẠNG CẢM BIẾN KHÔNG DÂY NGÀNH: KỸ THUẬT ĐIỆN TỬ - 605020203 Hƣớng dẫn khoa học: PGS.TS. DƢƠNG HOÀI NGHĨA Tp. Hồ Chí Minh, Tháng 10/2015
3. LÝ LỊCH CÁ NHÂN I. LÝ LỊCH SƠ LƢỢC: Họ & tên: Nguyễn Thị Thu Trang Giới tính: Nữ Ngày, tháng, năm sinh: 23/10/1989 Nơi sinh: Bình Dƣơng Quê quán: BắcTân Uyên, Bình Dƣơng Dân tộc: Kinh Chỗ ở riêng hoặc địa chỉ liên lạc: Ấp 1, Tân Mỹ, Bắc Tân Uyên, Bình Dƣơng Điện thoại cơ quan: Điện thoại nhà riêng: Fax: E-mail: nguyentrang039@gmail.com II. QUÁ TRÌNH ĐÀO TẠO: 1. Trung học chuyên nghiệp: Hệ đào tạo: Thời gian đào tạo từ / đến / Nơi học (trƣờng, thành phố): Ngành học: 2. Đại học: Hệ đào tạo: Chính quy Thời gian đào tạo từ 10/2007 đến 2/2012 Nơi học (trƣờng, thành phố): Trƣờng Đại học sƣ phạm kỹ thuật TP. HCM Ngành học: Công nghệ điện tử viễn thông Tên đồ án, luận án hoặc môn thi tốt nghiệp:Giải pháp thoại VOIP cho trƣờng Đại học sƣ phạm kỹ thuật TP. HCM Ngày & nơi bảo vệ đồ án, luận án hoặc thi tốt nghiệp:2/2012 tại trƣờng Đại học sƣ phạm kỹ thuật TP. HCM Ngƣời hƣớng dẫn:Th.S Phan Thanh Toản III. QUÁ TRÌNH CÔNG TÁC CHUYÊN MÔN KỂ TỪ KHI TỐT NGHIỆP ĐẠI HỌC: Thời gian Nơi công tác Công việc đảm nhiệm 10/2012 – 1/2013 Trƣờng Trung cấp nghề Thủ Dầu Một Giáo viên 1/2013 – đến nay Trƣờng Trung cấp nghề Việt Hàn Bình Dƣơng Giáo viên i
4. LỜI CAM ĐOAN Tôi cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong luận văn là trung thực và chƣa từng đƣợc ai công bố trong bất kỳ công trình nào khác. Tp. Hồ Chí Minh, ngày 20 tháng 8 năm 2015 (Ký tên và ghi rõ họ tên) Nguyễn Thị Thu Trang ii
5. LỜI CẢM TẠ Trong suốt quá trình học tập, nghiên cứu và hoàn thành thành công luận văn này, tôi đã nhận đƣợc sự hƣớng dẫn, giúp đỡ quý báu của các thầy cô giáo, các anh chị và các bạn. Với lòng kính trọng và biết ơn sâu sắc, tôi xin đƣợc bày tỏ lời cám ơn chân thành tới tất cả mọi cá nhân và tập thể đã tận tình giúp đỡ, đóng góp ý kiến, khích lệ tinh thần để tôi hoàn thành luận văn của mình. Đầu tiên, tôi muốn bày tỏ sự biết ơn sâu sắc đến thầy PGS. TS Dƣơng Hoài Nghĩa đã tận tình, tận tâm chỉ bảo, hƣớng dẫn và định hƣớng cho tôi trong suốt quá trình nghiên cứu và hoàn thành luận văn. Tôi cũng muốn bày tỏ lòng biết ơn của mình đến Ban Giám Hiệu, Phòng Đào tạo sau đại học trƣờng Đại học Sƣ phạm Kỹ thuật TP. HCM đã tạo mọi điều kiện thuận lợi để tôi hoàn thành tốt khóa học và tốt nghiệp. Cuối cùng, tôi muốn gửi lời cám ơn đến gia đình, ngƣời thân và bạn bè đã quan tâm, động viên và giúp đỡ tôi về mọi mặt trong suốt quá trình nghiên cứu, hoàn thành luận văn này. Một lần nữa tôi xin chân thành gởi lời cảm ơn đến tất cả! Tp. Hồ Chí Minh, ngày 15 tháng 8 năm 2015 Nguyễn Thị Thu Trang iii
6. Tóm tắt Các điều kiện về môi trƣờng, năng lƣợng, băng thông, bộ nhớ và khả năng xử lý trong mạng cảm biến không dây làm cho nó luôn là thách thức của những nhà nghiên cứu. Trong đó làm thế nào để duy trì tối đa tuổi thọ mạng là vấn đề cấn thiết.Đề tài“Nghiên cứu giải thuật định tuyến cân bằng tải nhằm nâng cao tuổi thọ cho mạng cảm biến không dây”tập trung vào mô hình cân bằng tải với mức tiêu thụ năng lƣợng của các nút cảm biến của toàn mạng đƣợc phân bố đồng đều từ đó kéo dài tuổi thọ cho mạng cảm biến không dây. Qua các số liệu mô phỏng trên Matlab nhƣ sự phân bố năng lƣợng còn lại của các nút cảm biến khi có một nút cảm biến cạn kiệt năng lƣợng, sự thay đổi về bán kính phạm vi liên lạc hay số nút cảm biến trong một diện tích không đổi cũng nhƣ sử dụng mô phỏng Monte Carlo đã chứng minh đƣợc hiệu quả của phƣơng án định tuyến cân bằng tải.Giải pháp đƣợc đề xuất là bổ sung thêm vào giải thuật định tuyến đƣờng đi ngắn nhất với trọng số là tỉ lệ nghịch của năng lƣợng còn lại của mỗi nút cảm biến. Nhƣ vậy, việc một nút đƣợc lựa chọn là nút trung gian không chỉ dựa vào khoảng cách từ nút nguồn đến trạm gốc mà còn phụ thuộc vào năng lƣợng còn lại của nút đó. iv
7. Abstract Conditions of environment, energy, bandwidth, memory and processing capability in wireless sensor networks make it always a challenge of researchers.In particular, how to maintain the network's maximum lifetime isa necessary issues.Research topics routing algorithm load balancing to improve lifetime for wireless sensor networks focusing on load balancer models with energy consumption of sensor nodes are uniformly distributed to extend the life of wireless sensor network.Through the Matlab simulation data such as the distribution of the remaining energy of sensor nodes when a sensor node was energy depletion, the change in radius communication range or number of sensor nodes in a constant area, as well as using Monte Carlo simulations have demonstrated the effectiveness of the alternative load balancing routing.The proposed solution is added to the algorithm shortest path routing with weights that are inversely proportional to the residual energy of each sensor node.Thus, the selection of intermediate node is not only based on the distance from the source node to the base station but also depends on the remaining energy of the node. v
8. MỤC LỤC TRANG Trang tựa Lý lịch cá nhân i Lời cam đoan ii Lời cảm tạ iii Tóm tắt iv Danh sách chữ viết tắt/ký hiệu khoa học ix Danh sách các hình xi Danh sách các bảng xiii Chƣơng 1: TỔNG QUAN 1 1.1. Lý do chọn đề tài 1 1.2. Mục tiêu nghiên cứu 2 1.3. Nhiệm vụ nghiên cứu 2 1.4. Khách thể và đối tƣợng nghiên cứu 3 1.5. Giả thuyết nghiên cứu 3 1.6. Phạm vi nghiên cứu 3 1.7. Phƣơng pháp nghiên cứu 3 1.8. Kế hoạch thực hiện 4 Chƣơng 2: CƠ SỞ LÝ THUYẾT 5 2.1. Tổng quan về mạng cảm biến không dây 5 2.2. Giới thiệu về IEEE 802.15.4 MAC 8 2.2.1. Phƣơng thức mạng và cấu trúc siêu khung 8 a. Phƣơng thức mạng 8 b. Cấu trúc siêu khung 9 2.2.2. Quản lý khe thời gian đảm bảo 10 2.2.3. Chế độ truyền dữ liệu 10 2.3. Một số giao thức định tuyến trong mạng cảm biến không dây 11 vi
9. 2.4. Một số ví dụ triển khai 13 2.5. Kết luận chƣơng 14 Chƣơng 3: ĐỊNH TUYẾN CÂN BẰNG TẢI 15 3.1. Tổng quan 15 3.2. Khung định tuyến 15 3.3. Cấu hình và duy trì mạng 18 3.3.1. Sơ đồ định tuyến 18 3.3.2. Các giai đoạn thành lập định tuyến 20 3.3.3. Quá trình lựa chọn nút chuyển tiếp thích ứng 21 3.3.4. Phòng chống định tuyến vòng và khả năng thích ứng với các biến động liên kết 22 3.4. Tổng hợp và phân phối dữ liệu cân bằng 24 3.4.1. Tổng hợp nhận thức tại 24 3.4.2. Giới hạn thời hạn chuyển tiếp 26 3.5. Định tuyến cân bằng năng lƣợng 28 3.5.1. Năng lƣợng tiêu hao trung bình trên mỗi tuyến đƣờng 28 3.5.2. Năng lƣợng và xác suất tin cậy 30 3.5.3. Xác suất chuyển tiếp gói dữ liệu 31 3.5.4. Mô hình cân bằng năng lƣợng 32 3.5.5. Sự tiêu thụ năng lƣợng trên mỗi nút cảm biến chuyển tiếp 34 3.6. Kết luận chƣơng 37 Chƣơng 4:MÔ PHỎNG ĐỊNH TUYẾN CÂN BẰNG TẢI 38 4.1. Các thông số mô phỏng 38 4.2. Phƣơng pháp định tuyến 39 4.3. Các trƣờng hợp mô phỏng 41 4.3.1. Phân bố đều các nút cảm biến 41 4.3.1.1. Sự tổng hợp và chuyển tiếp các gói dữ liệu tại các nút cảm biến phân bố đều 41 4.3.1.2. Phân bố năng lƣợng còn lại tại các nút cảm biến phân bố đều 46 vii
10. 4.3.2. Phân bố ngẫu nhiên các nút cảm biến 47 4.3.2.1. Sự tổng hợp và chuyển tiếp các gói dữ liệu tại các nút cảm biến phân bố ngẫu nhiên 48 4.3.2.2. Phân bố năng lƣợng còn lại tại các nút cảm biến phân bố ngẫu nhiên 52 4.3.2.3. Ảnh hƣởng của số lƣợng nút cảm biến N và bán kính phạm vi liên lạc R trong phân bố ngẫu nhiên 53 4.4. Mô phỏng Monte Carlo 56 4.7. Kết luận chƣơng 58 Chƣơng 5:KẾT LUẬN 59 5.1. Kết luận 59 5.2. Hƣớng phát triển 59 TÀI LIỆU THAM KHẢO 60 PHỤ LỤC 62 Phụ lục 1: Thuật toán Floyd - Warshall 62 Phụ lục 2: Tổng số gói dữ liệu theo bán kính phạm vi liên lạc 64 Phụ lục 3: Số liệu mô phỏng Monte Carlo 64 viii
11. DANH SÁCH CHỮ VIẾT TẮT/KÝ HIỆU KHOA HỌC ADC: Analog to Digital Converter Bộ chuyển đổi tƣơng tự sang số APs: Access Points Các điểm truy cập AoA: Angle of Arrival Góc tới B-MAC: Bluetooth - MAC Giao thức MAC cho Bluetooth BS: Base Station Trạm gốc CSMA: Carrier Sense Multiple Access Đa truy cập cảm nhận sóng mang CSI: Channel State Information Thông tin trạng thái kênh DSP: Digital Signal Processing Bộ xử lý tín hiệu số EAR: Energy-Aware Routing Định tuyến nhận thức năng lƣợng HC: Hop Count Số chặng Institute of Electrical and Electronic IEEE: Viện kỹ thuật điện và điện tử Engineering LQI: Link Quality Indicator Chỉ số chất lƣợng liên kết MAC: Medium access control Điều khiển truy cập môi trƣờng MANET: Mobile ad hoc Network Mạng tùy biến không dây MTU: Maximum Transmission Unit Đơn vị truyền cực đại PDF: Probability Distribution Function Hàm phân bố xác suất SNR: Signal-to-Noise Ratio Tỉ số tín hiệu trên nhiễu SPR: Shortest Path Routing Định tuyến đƣờng đi ngắn nhất PRR: Packet Reception Ratio Tỉ lệ tiếp nhận gói dữ liệu PLR: Packet Loss Ratio Tỉ lệ mất gói dữ liệu QoS: Quality of Service Chất lƣợng dịch vụ ix
12. RF: Radio Frequency Tần số vô tuyến LBR: Load-Balancing Routing Định tuyến cân bằng tải Chỉ số báo hiệu cƣờng độ tín hiệu RSSI: Received Strength Signal Indicator thu Đa truy cập phân chia theo thời TDMA: Time Division Multiple Access gian THL: Time Has Lived Thời gian đã sống ToA: Time of Arrival Thời điểm đến WSNs: Wireless Sensor Networks Mạng cảm biến không dây x
13. DANH SÁCH CÁC HÌNH HÌNH TRANG Hình 2.1: Cấu trúc siêu khung 9 Hình 3. 1: Khung định tuyến của định tuyến cân bằng tải 16 Hình 3. 2: Sơ đồ định tuyến với 100 nút cảm biến 19 Hình 3. 3: Cấu trúc khung định tuyến của LBR 20 Hình 3. 4: Quá trình chọn nút chuyển tiếp 22 Hình 3. 5: Tổng hợp nhận thức tải 25 Hình 3. 6: Giới hạn thời hạn tổng hợp/chuyển tiếp 27 Hình 3. 7: Tính toán chi phí năng lƣợng trên tuyến đƣờng r 29 Hình 3. 8: Các thành phần mô hình liên lạc 35 Hình 4. 1: Mô hình xác định định tuyến 39 Hình 4. 2: Sơ đồ mô phỏng với 100 nút cảm biến phân bố đều 41 Hình 4. 3: Tổng số gói dữ liệu tại các nút cảm biến phân bố đều (LBR) 42 Hình 4. 4: Tổng số gói tin thu tại các nút cảm biến phân bố đều (LBR) 43 Hình 4. 5: Tổng số gói tin phát tại các nút cảm biến phân bố đều (LBR) 43 Hình 4. 6: Tổng số gói dữ liệu tại các nút cảm biến phân bố đều (SPR) 44 Hình 4. 7: Tổng số gói tin thu tại các nút cảm biến phân bố đều (SPR) 45 Hình 4. 8: Tổng số gói tin phát tại các nút cảm biến phân bố đều (SPR) 45 Hình 4. 9: Năng lƣợng còn lại của các nút cảm biến phân bố đều (LBR) 46 Hình 4. 10: Năng lƣợng còn lại của các nút cảm biến phân bố đều (SPR) 47 Hình 4. 11: Sơ đồ mô phỏng với 100 nút cảm biến phân bố ngẫu nhiên 47 Hình 4. 12: Tổng số gói dữ liệu tại các nút cảm biến phân bố ngẫu nhiên (LBR) 48 Hình 4. 13: Tổng số gói tin thu tại các nút cảm biến phân bố ngẫu nhiên (LBR) 49 Hình 4. 14: Tổng số gói tin phát tại các nút cảm biến phân bố ngẫu nhiên (LBR) 49 Hình 4. 15: Số gói dữ liệu tại các nút cảm biến phân bố ngẫu nhiên (SPR) 50 Hình 4. 16: Tổng số gói tin thu tại các nút cảm biền phân bố ngẫu nhiên (SPR) 51 Hình 4. 17: Tổng số gói tin phát tại các nút cảm biến phân bố ngẫu nhiên (SPR) 51 xi
14. Hình 4. 18: Năng lƣợng còn lại tại các nút cảm biến phân bố ngẫu nhiên (LBR) 52 Hình 4. 19: Năng lƣợng còn lại tại các nút cảm biến phân bố ngẫu nhiên (SPR) 53 Hình 4. 20: Mật độ phân bố ngẫu nhiên 80 nút cảm biến 54 Hình 4. 21: Mật độ phân bố 100 nút cảm biến 54 Hình 4. 22: Định tuyến đƣờng đi ngắn nhất theo N và R 55 Hình 4. 23: Định tuyến cân bằng tải theo N và R 55 Hình 4. 24: Hàm phân phối và hàm mật độ xác suất 57 xii
15. DANH SÁCH CÁC BẢNG BẢNG TRANG Bảng 4. 1: Các thông số mô phỏng 39 Bảng 4. 2: Thông số mô phỏng Monte Carlo 56 Bảng 4. 3: Kỳ vọng toán học và phƣơng sai 58 xiii
16. Chƣơng 1 TỔNG QUAN 1.1. Lý do chọn đề tài Một mạng cảm biến không dây (WSN) bao gồm một số nút, mỗi nút thƣờng có năng lƣợng nhỏ và không đƣợc nạp lại. Trong kiến trúc mạng WSN, dữ liệu đƣợc truyền từ nút nguồnđến trạm gốc thông qua các nút trung giansử dụng giao tiếp không dây, giao tiếp này đƣợc thực hiện bằng vô tuyến. Việc truyền hoặc nhận, ngay cả vô tuyến công suất thấp cũng tốn nhiều năng lƣợng nên vô tuyến phải đƣợc sử dụng một cách khôn ngoan để tránh sự suy giảm không cần thiết của năng lƣợng. Cuối cùng, cạn kiệt năng lƣợng tại mỗi nút làm cho nó ngừng hoạt động, dẫn đến mất mát của thu thập dữ liệu và cung cấp dữ liệu. Trong khi sự cạn kiệt của một số nút có thể chấp nhận đƣợc mặc dù không mong muốn, nhƣng sựcạn kiệt của một số nút quan trọng nhất định trong một môi trƣờng định tuyến multihop có thể gây ra phân vùng mạng làm cho dữ liệu có thể không đƣợc truyền đến trạm gốc, làm giảm tính hữu ích của mạng. Có nhiều giao thức định tuyến nhận thức năng lƣợng đƣợc đƣa ra trong [1], [2]. Một trong những giao thức nhận thức năng lƣợng phổ biến nhất là định tuyến nhận thức năng lƣợng EAR đã đƣợc đề xuất trong [2]. Giao thức định tuyến nhận thức năng lƣợng là giao thức tìm định tuyến có chi phí năng lƣợng thấp và sử dụng định tuyến đó cho tất cả quá trình truyền dẫn. Tuy nhiên, đây không phải là phƣơng án giải quyết tối ƣu để tăng thời gian sống của mạng bởi vì việc sử dụng định tuyến có chi phí năng lƣợng thấp thƣờng xuyên dẫn đến sự cạn kiệt năng lƣợng của các nút cảm biến dọc theo những tuyến đƣờng và dẫn đến phân vùng mạng. Giao thức định tuyến đƣờng đi ngắn nhất SPR [3], [4] là giao thức cung cấp một phƣơng pháp đơn giản trong quá trình lựa chọn nút chuyển tiếp bằng cách liên kết ngay lập tức với các nút lân cận có khoảng cách ngắn nhất trong phạm vi liên lạc của chúng. Đƣờng định tuyến là đƣờng ngắn nhất để các nút cảm biến chuyển các gói dữ liệu về trạm gốc và tránh đƣợc các vòng lặp. Định tuyến đƣờng đi ngắn 1
17. nhất cũng giúp cho các nút cảm biến tiết kiệm đƣợc năng lƣợng trong quá trình chuyển gói dữ liệu. Tuy nhiên, phƣơng pháp này cũng không thực sự tối ƣu cho việc tối đa thời gian sống của mạng do định tuyến đƣờng ngắn nhất chỉ phù hợp với cấu trúc mạng tĩnh, cấu trúc mạng động hoặc hỗn hợp thì hiệu quả sử dụng thấp. Quá trình định tuyến liên tục sử dụng các đƣờng định tuyến ngắn nhất dẫn đến các nút cảm biến dọc theo đƣờng định tuyến, đặc biệt là các nút gần trạm gốc đƣợc nhiều nút lựa chọn sẽ nhanh chóng cạn kiệt năng lƣợng làm cho mạng có thể phân vùng hoặc đột ngột dừng hoạt động. Để khắc phục sự cố này, đề tài nghiên cứu giải thuật định tuyến cân bằng tải nhằm nâng cao tuổi thọ cho mạng cảm biến không dây đƣợc đề xuất. Các tuyến đƣờng sử dụng năng lƣợng gần mức tối ƣu kết hợp với khoảng cách ngắn nhất từ nút nguồn đến trạm gốc nhằm đảm bảo sự cân bằng năng lƣợng cho mạng. Năng lƣợng của mạng sẽ tiêu hao đồng đều trên các nút cảm biến nhờ đó mà kéo dài đƣợc thời gian sống của toàn mạng. 1.2. Mục tiêu nghiên cứu Mục tiêu của luận văn làcân bằng sự tham gia vào quá trình định tuyến của các nút cảm biến sao cho tổng số gói dữ liệu nhận đƣợc tại trạm gốc là nhiều nhất hoặc tuổi thọ của mạng cảm biến không dây là lâu nhất. Luận văn này góp phần vào kiến thức học thuật trong các lĩnh vực phát triển đề án định tuyến đáng tin cậy và tiết kiệm năng lƣợng cho mạng cảm biến không dây. 1.3. Nhiệm vụ nghiên cứu Dựa trên thuật toán đƣờng đi ngắn nhất. Đề án bổ sung thêm trọng số là nghịch đảo của năng lƣợng còn lại của nút đó. Khi một tuyến đƣờng đƣợc thiết lập, chúng không chỉ dựa vào khoảng cách ngắn nhất để truyền dữ liệu đến trạm gốc mà còn dựa vào năng lƣợng còn lại của nút cảm biến. Những nút cảm biến có năng lƣợng còn lại lớn hơn sẽ đƣợc ƣu tiên hơn trong quá trình lựa chọn tuyến đƣờng. 2
18. 1.4. Khách thể và đối tƣợng nghiên cứu Đề án nghiên cứu dựa trên 100 nút cảm biến đƣợc phân bố ngẫu nhiên trên diện tích 500x500 m2 và một trạm gốc. Mỗi nút lần lƣợt truyền dữ liệu thu thập đƣợc về cho trạm gốc. Dựa trên định tuyến đƣờng đi ngắn nhất, đề án đề xuất bổ sung thêm trọng số là nghịch đảo năng lƣợng còn lại của mỗi nút nhằm cân bằng năng lƣợng của mỗi nút cảm biến từ đó duy trì đƣợc tuổi thọ cho mạng cảm biến không dây. 1.5. Giả thuyết nghiên cứu Với thuật toán định tuyến đƣờng đi ngắn nhất của Floyd-Warshall thì chúng chỉ dựa vào khoảng cách ngắn nhất mà thiết lập tuyến đƣờng. Từ đó một số nút quan trọng gần trạm gốc sẽ bị lạm dụng một cách đáng kể, làm cho tuổi thọ của mạng không đƣợc duy trì lâu. Giả thuyết đƣa thêm trọng số năng lƣợng còn lại vào trong điều kiện lựa chọn tuyến đƣờng. Tuyến đƣờng đƣợc lựa chọn với năng lƣợng cao hơn và khoảng cách ngắn hơn, giúp năng lƣợng của các nút đƣợc sử dụng một cách đồng đều hơn, từ đó tuổi thọ của toàn mạng đƣợc duy trì lâu hơn. 1.6. Phạm vi nghiên cứu Phạm vi nghiên cứu trên 100 nút cảm biến phân bố ngẫu nhiên trên diện tích 500x500m2 và một trạm gốc. Bán kính phạm vi liên lạc giữa hai nút cảm biến là 100m. Năng lƣợng ban đầu của mỗi nút cảm biến là 1 đơn vị năng lƣợng. Khi cảm biến tham gia vào quá trình định tuyến sẽ tiêu hao một mức năng lƣợng gọi là năng lƣợng phát bằng 0.0005 đvnl. Nút cảm biến sẽ tiêu hao một mức năng lƣợng thu 0.0001 đvnl nếu nút đó là nút trung gian giữa nút nguồn đến trạm gốc. 1.7. Phƣơng pháp nghiên cứu Luận văn đƣợc thực hiện theo mạng lƣới chuẩn 802.16. Luận văn mô phỏng, so sánh các thuật toán nhằm nâng cao tuổi thọ cho mạng cảm biến không dây. Luận văn dựa trên thuật toán tìm đƣờng đi ngắn nhất của Floyd-Warshall. Từ đó đề xuất thêm trọng số là tỷ lệ nghịch của năng lƣợng còn lại của nút cảm biến để tối đa hóa tuổi thọ cho mạng cảm biến không dây. 3
19. Dựa vào phần mềm mô phỏng Matlab 2013a, mô phỏng một mạng cảm biến với 100 nút và một trạm gốc. Mô phỏng cho lần lƣợt từ nút cảm biến truyền dữ liệu thu thập đƣợc về cho trạm gốc. Mô phỏng dừng lại khi một nút cảm biến đầu tiên hết hạn. 1.8. Kế hoạch thực hiện Thời gian thực hiện Nội dung thực hiện 23/2/2015 – 20/3/2015 Nghiên cứu định tuyến cân bằng tải 20/3/2015 – 20/6/2015 Mô phỏng thuật toán định tuyến cân bằng tải So sánh phƣơng pháp định tuyến cân bằng tải và 20/6/2015 – 20/7/2015 phƣơng pháp định tuyến đƣờng đi ngắn nhất 20/7/2015 – 20/8/2015 Viết báo cáo luận văn tốt nghiệp 4
20. Chƣơng 2 CƠ SỞ LÝ THUYẾT 2.1. Tổng quan về mạng cảm biến không dây Trong lịch sử, WSN đã đƣợc mô tả nhƣ là mạng không dây bao gồm rất nhiều nút, năng lƣợng hạn chế, chi phí thấp, và tự trị. Nó đƣợc phân phối trên một diện tích cho mục đích giám sát hoặc cảm biến. Truyền thông hoặc chuyển tiếp dữ liệu thƣờng thông qua định tuyến không dây multi-hop. Phần lớn WSN đƣợc mô tả trong chƣơng này trình bày kiến trúc, có thể bao gồm bất kỳ số lƣợng của: Nút source: tạo dữ liệu, thƣờng sử dụng cảm biến để đo yếu tố môi trƣờng nhƣ nhiệt độ, độ ẩm hoặc bức xạ. Nút sink: tập hợp các dữ liệu đã đƣợc tạo từ nút source. Nút intermediate: có thể bao gồm nút source, hỗ trợ việc truyền tải dữ liệu từ nút source đến nút sink. Việc tạo dữ liệu tại các nút nguồn có thể xảy ra hoặc chủ động hoặc đáp ứng từ một số yêu cầu. Có ý kiến cho rằng các nút sink thƣờng gọi là base station, có thể có công suất cao, đƣợc liên kết đến cơ sở dữ liệu thông qua kết nối vệ tinh hoặc có nhiều tài nguyên hơn các nút khác. Các nút trong WSN thƣờng đƣợc cung cấp năng lƣợng từ pin.Năng lƣợng của một nút đƣợc sử dụng lên quan đến năng lƣợng pin còn lại của nó. Năng lƣợng của pin phụ thuộc vào kích thƣớc của nó và khi các nút đƣợc dự kiến sẽ đƣợc thu nhỏ, pin không thể có năng lƣợnglớn. Vấn đề cạn kiệt pin là một trong những thách thức chính trong việc phát triển và làm việc với WSN, đặc biệt là khi mọi hoạt động đƣợc thực hiện bởi các nút đòi hỏi hao tốn năng lƣợng. Trong khi các nguồn tài nguyên khác nhƣ CPU, bộ nhớ hoặc lƣu trữ có thể ngay lập tức đƣợc tái sử dụng khi mất nguồn, điều này không đúng đối với pin. Trừ khi nút có một số phƣơng tiện bổ sung năng lƣợng, năng lƣợngcủa pin hạn chế cả về thời gian sống tối đa của nút và cả về tần số mà nút có thể thực hiện các hoạt động cụ thể. 5
21. Ngoài những đặc điểm này, rất khó để cung cấp một định nghĩa chính thức khả năng chính xác của WSN, đặc biệt là do số lƣợng ngày càng tăng của việc sử dụng các công nghệ. Có giả thuyết cho rằng, với WSN thƣờng phụ thuộc vào ứng dụng, nó sẽ không bao giờ tạo ra một kiến trúc duy nhất để sử dụng cho tất cả các ứng dụng. Nếu không có một kiến trúc xác định, nó không thể xác định chính xác các đặc tính. Romer đã tạo ra một không gian thiết kế, đề cập về số lƣợng lớn các kích thƣớc trong triển khai WSN, bao gồm: Loại khiển khai Nút chuyển động Kích thƣớc nút Giá thành nút (theo dollars) Năng lƣợng cho phép Tính không đồng nhất của nút Phƣơng pháp truyền thông không dây Cơ sở hạ tầng Cấu trúc liên kết mạng Mức độ bao phủ vật thể của cảm biến Loại kết nối Số lƣợng nút Ƣớc lƣợng thời gian hoạt động Chất lƣợng dịch vụ Loại triển khai đề cập đến bố trí vật lý của các nút đƣợc triển khai, tức là các nút đƣợc triển khai một lần hoặc lặp đi lặp lại và vị trí các nút là ngẫu nhiên hoặc bằng tay. Cơ sở hạ tầng quy định cách định tuyến xảy ra trong hệ thống; giá trị có thể là ad hoc trong đó các nút có thể giao tiếp với các nút khác và với base station, hoặc các nút có thể trực tiếp giao tiếp với một base station. Các cấu trúc liên kết mạng ảnh hƣởng đến các nút là liên kết với nhau, tức là các nút có thể giao tiếp với nhau. Mức độ bao phủ vật thể của cảm biến phản ánh mật độ của các nút source, nghĩa là thƣa thớt hoặc dày đặc. Trong trƣờng hợp lý tƣởng, mức độ bao phủ vật thể 6
22. S K L 0 0 2 1 5 4