Nghiên cứu giải thuật định tuyến cân bằng tải để nâng cao tuổi thọ cho mạng cảm biến không dây

Luận văn thạc sĩ nghiên cứu hcmute 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, khảo sát thực trạng, phân tích nguyên nhân, đề

• Tác giả: Nguyễn Thị Thu Trang
• Người hướng dẫn: PGS. Dương Hoài Nghĩa
• Trường học: Trường Đại Học Sư Phạm Kỹ Thuật Thành Phố Hồ Chí Minh
• Chuyên ngành: Kỹ Thuật Điện 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
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2015
• Địa điểm: Tp. Hồ Chí Minh

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM TẠ
• TÓM TẮT
• DANH SÁCH CHỮ VIẾT TẮT/KÝ HIỆU KHOA HỌC
• DANH SÁCH CÁC HÌNH
• DANH SÁCH CÁC BẢNG
• 1. CHƯƠNG 1: TỔNG QUAN
• 1.1. Lý do chọn đề tài
• 1.2. Mục tiêu nghiên cứu
• 1.3. Nhiệm vụ nghiên cứu
• 1.4. Khách thể và đối tượng nghiên cứu
• 1.5. Giả thuyết nghiên cứu
• 1.6. Phạm vi nghiên cứu
• 1.7. Phương pháp nghiên cứu
• 1.8. Kế hoạch thực hiện
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
• 2.1. Tổng quan về mạng cảm biến không dây
• 2.2. Giới thiệu về IEEE 802. Phương thức mạng và cấu trúc siêu khung
• 2.2.1. Phương thức mạng
• 2.2.2. Cấu trúc siêu khung
• 2.3. Quản lý khe thời gian đảm bảo
• 2.4. Chế độ truyền dữ liệu
• 2.5. Một số giao thức định tuyến trong mạng cảm biến không dây
• 2.6. Một số ví dụ triển khai
• 2.7. Kết luận chương
• 3. CHƯƠNG 3: ĐỊNH TUYẾN CÂN BẰNG TẢI
• 3.1. Khung định tuyến
• 3.2. Cấu hình và duy trì mạng
• 3.3. Các giai đoạn thành lập định tuyến
• 3.4. Quá trình lựa chọn nút chuyển tiếp thích ứng
• 3.5. 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
• 3.6. Tổng hợp và phân phối dữ liệu cân bằng
• 3.7. Tổng hợp nhận thức tại
• 3.8. Giới hạn thời hạn chuyển tiếp
• 3.9. Định tuyến cân bằng năng lượng
• 3.10. Năng lượng tiêu hao trung bình trên mỗi tuyến đường
• 3.11. Năng lượng và xác suất tin cậy
• 3.12. Xác suất chuyển tiếp gói dữ liệu
• 3.13. Mô hình cân bằng năng lượng
• 3.14. Sự tiêu thụ năng lượng trên mỗi nút cảm biến chuyển tiếp
• 3.15. Kết luận chương
• 4. CHƯƠNG 4: MÔ PHỎNG ĐỊNH TUYẾN CÂN BẰNG TẢI
• 4.1. Các thông số mô phỏng
• 4.2. Phương pháp định tuyến
• 4.3. Các trường hợp mô phỏng
• 4.3.1. Phân bố đều các nút cảm biến
• 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
• 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
• 4.3.2. Phân bố ngẫu nhiên các nút cảm biến
• 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
• 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
• 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
• 4.3.3. Mô phỏng Monte Carlo
• 4.4. Kết luận chương
• 5. CHƯƠNG 5: KẾT LUẬN
• 5.1. Hướng phát triển
• TÀI LIỆU THAM KHẢO
• PHỤ LỤC
• Phụ lục 1. Thuật toán Floyd - Warshall
• Phụ lục 2. Tổng số gói dữ liệu theo bán kính phạm vi liên lạc
• Phụ lục 3. Số liệu mô phỏng Monte Carlo

Tóm tắt

I. Tổng quan về mạng cảm biến không dây

Mạng cảm biến không dây (WSN) là một hệ thống bao gồm nhiều nút cảm biến với năng lượng hạn chế, thường được sử dụng để giám sát và thu thập dữ liệu từ môi trường. Các nút này giao tiếp với nhau qua kết nối không dây, thường sử dụng phương thức định tuyến multi-hop. Việc duy trì tuổi thọ mạng là một thách thức lớn, vì năng lượng của các nút cảm biến thường không thể được nạp lại. Khi một nút cảm biến cạn kiệt năng lượng, nó sẽ ngừng hoạt động, dẫn đến mất mát dữ liệu và giảm hiệu quả của mạng. Do đó, việc phát triển các giải pháp định tuyến hiệu quả nhằm tối ưu hóa tuổi thọ pin và hiệu suất mạng là rất cần thiết.

1.1. Đặc điểm của mạng cảm biến không dây

Mạng cảm biến không dây có những đặc điểm nổi bật như: số lượng nút lớn, năng lượng hạn chế, và khả năng tự động hoạt động. Các nút cảm biến thường được phân bố trên một diện tích rộng lớn để thu thập dữ liệu từ nhiều vị trí khác nhau. Việc truyền tải dữ liệu từ nút nguồn đến trạm gốc thông qua các nút trung gian là rất quan trọng. Tuy nhiên, việc sử dụng năng lượng hiệu quả là một thách thức lớn, vì năng lượng của các nút cảm biến thường bị tiêu hao nhanh chóng trong quá trình truyền tải dữ liệu. Do đó, việc phát triển các giải pháp định tuyến như giải thuật định tuyến cân bằng tải là cần thiết để kéo dài tuổi thọ mạng.

II. Giải thuật định tuyến cân bằng tải

Giải thuật định tuyến cân bằng tải được thiết kế nhằm phân phối đồng đều năng lượng tiêu hao giữa các nút cảm biến trong mạng. Mục tiêu chính là kéo dài tuổi thọ mạng bằng cách ngăn chặn tình trạng cạn kiệt năng lượng ở các nút quan trọng. Giải thuật này sử dụng trọng số là tỷ lệ nghịch của năng lượng còn lại của mỗi nút để lựa chọn nút trung gian trong quá trình truyền tải dữ liệu. Điều này có nghĩa là các nút có năng lượng cao hơn sẽ được ưu tiên hơn trong việc truyền tải dữ liệu, từ đó giúp cân bằng tải và kéo dài thời gian hoạt động của mạng.

2.1. Cấu trúc và hoạt động của giải thuật

Giải thuật định tuyến cân bằng tải hoạt động dựa trên việc phân tích năng lượng còn lại của các nút cảm biến. Khi một nút cảm biến được chọn làm nút trung gian, nó 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 đó. Điều này giúp đảm bảo rằng không có nút nào bị lạm dụng quá mức, từ đó kéo dài tuổi thọ mạng. Các mô phỏng cho thấy rằng việc áp dụng giải thuật này có thể cải thiện đáng kể hiệu suất của mạng cảm biến không dây.

III. Tối ưu hóa hiệu suất mạng

Tối ưu hóa hiệu suất mạng cảm biến không dây là một yếu tố quan trọng trong việc nâng cao tuổi thọ mạng. Việc sử dụng các giải thuật định tuyến hiệu quả không chỉ giúp tiết kiệm năng lượng mà còn đảm bảo rằng dữ liệu được truyền tải một cách nhanh chóng và chính xác. Các nghiên cứu đã chỉ ra rằng việc áp dụng giải thuật định tuyến cân bằng tải có thể làm giảm đáng kể tỷ lệ mất gói dữ liệu và tăng cường khả năng truyền tải thông tin. Điều này không chỉ có lợi cho việc duy trì hoạt động của mạng mà còn cải thiện khả năng thu thập dữ liệu từ môi trường.

3.1. Ứng dụng thực tiễn của giải thuật

Giải thuật định tuyến cân bằng tải có thể được áp dụng trong nhiều lĩnh vực khác nhau, từ giám sát môi trường đến quản lý năng lượng trong các hệ thống thông minh. Việc tối ưu hóa hiệu suất mạng không chỉ giúp kéo dài tuổi thọ pin mà còn nâng cao khả năng thu thập và truyền tải dữ liệu. Các ứng dụng thực tiễn của giải thuật này có thể bao gồm giám sát chất lượng không khí, theo dõi động vật hoang dã, và quản lý tài nguyên nước. Những ứng dụng này cho thấy giá trị thực tiễn của việc phát triển và áp dụng các giải pháp định tuyến hiệu quả trong mạng cảm biến không dây.

Nội dung chính

Tổng quan nghiên cứu

Mạng cảm biến không dây (Wireless Sensor Networks - WSN) là hệ thống gồm nhiều nút cảm biến nhỏ, có năng lượng hạn chế và không thể nạp lại, được phân bố trên một diện tích nhất định để thu thập và truyền dữ liệu về trạm gốc. Theo ước tính, việc tiêu hao năng lượng không đồng đều giữa các nút cảm biến dẫn đến hiện tượng cạn kiệt năng lượng sớm ở một số nút quan trọng, gây phân vùng mạng và giảm tuổi thọ tổng thể của mạng. Vấn đề nghiên cứu trọng tâm của luận văn là làm thế nào để cân bằng tải năng lượng trong quá trình định tuyến nhằm kéo dài tuổi thọ mạng cảm biến không dây.

Mục tiêu cụ thể của nghiên cứu là phát triển và mô phỏng giải thuật định tuyến cân bằng tải, trong đó trọng số định tuyến không chỉ dựa trên khoảng cách ngắn nhất mà còn tính đến năng lượng còn lại của các nút cảm biến. Phạm vi nghiên cứu tập trung trên mô hình mạng gồm 100 nút cảm biến phân bố ngẫu nhiên trên diện tích 500x500 m² với bán kính liên lạc 100 m, sử dụng phần mềm Matlab 2013a để mô phỏng và đánh giá hiệu quả thuật toán. Kết quả nghiên cứu có ý nghĩa quan trọng trong việc nâng cao hiệu quả sử dụng năng lượng, giảm thiểu sự cạn kiệt năng lượng tập trung và kéo dài thời gian hoạt động của mạng cảm biến không dây, góp phần phát triển các giải pháp định tuyến tiết kiệm năng lượng trong lĩnh vực kỹ thuật điện tử và viễn thông.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình sau:

• Mạng cảm biến không dây (WSN): Mạng gồm các nút cảm biến có năng lượng hạn chế, truyền dữ liệu đa chặng (multi-hop) về trạm gốc. Các nút có thể là nguồn (source), trung gian (intermediate) hoặc trạm gốc (sink/base station). Năng lượng tiêu hao chủ yếu do truyền nhận dữ liệu qua sóng vô tuyến.

• Giao thức định tuyến nhận thức năng lượng (Energy-Aware Routing - EAR): Giao thức tìm đường dựa trên chi phí năng lượng thấp nhằm tiết kiệm năng lượng cho các nút cảm biến, tuy nhiên dễ gây cạn kiệt năng lượng tại các nút trung gian trên đường truyền.

• Định tuyến đường đi ngắn nhất (Shortest Path Routing - SPR): Lựa chọn tuyến đường có khoảng cách ngắn nhất từ nút nguồn đến trạm gốc, giúp tiết kiệm năng lượng truyền dẫn nhưng không cân bằng tải năng lượng, dẫn đến cạn kiệt năng lượng tập trung.

• Định tuyến cân bằng tải (Load-Balancing Routing - LBR): Mô hình định tuyến mới được đề xuất, bổ sung trọng số nghịch đảo năng lượng còn lại của nút cảm biến vào thuật toán tìm đường ngắn nhất Floyd-Warshall, nhằm phân phối đồng đều năng lượng tiêu hao trên toàn mạng.

Các khái niệm chính bao gồm: năng lượng còn lại của nút cảm biến, xác suất liên kết tin cậy, tổng hợp dữ liệu nhận thức tải, giới hạn thời hạn chuyển tiếp, và mô hình tiêu thụ năng lượng của các thành phần phần cứng.

Phương pháp nghiên cứu

Luận văn sử dụng phương pháp mô phỏng trên phần mềm Matlab 2013a với các bước chính:

• Nguồn dữ liệu: Mô hình mạng gồm 100 nút cảm biến phân bố ngẫu nhiên trên diện tích 500x500 m², mỗi nút có năng lượng ban đầu 1 đơn vị. Bán kính liên lạc giữa các nút là 100 m.

• Phương pháp phân tích: Thuật toán định tuyến cân bằng tải được xây dựng dựa trên thuật toán Floyd-Warshall tìm đường đi ngắn nhất, bổ sung 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. Mô phỏng so sánh hiệu quả thuật toán LBR với thuật toán định tuyến đường đi ngắn nhất SPR.

• Timeline nghiên cứu: Nghiên cứu lý thuyết và xây dựng thuật toán từ tháng 2 đến tháng 3 năm 2015; mô phỏng và so sánh thuật toán từ tháng 3 đến tháng 7 năm 2015; hoàn thiện báo cáo luận văn trong tháng 8 năm 2015.

• Cỡ mẫu và chọn mẫu: Mạng gồm 100 nút cảm biến được phân bố ngẫu nhiên, đại diện cho mạng cảm biến không dây điển hình trong phạm vi nghiên cứu.

• Phương pháp mô phỏng: Sử dụng mô phỏng Monte Carlo để đánh giá sự phân bố năng lượng còn lại, tổng số gói dữ liệu truyền nhận, và tuổi thọ mạng dưới các điều kiện thay đổi về bán kính liên lạc và số lượng nút.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Phân bố năng lượng còn lại đồng đều hơn: Mô phỏng cho thấy khi áp dụng thuật toán định tuyến cân bằng tải (LBR), năng lượng còn lại của các nút cảm biến được phân bố đồng đều hơn so với thuật toán định tuyến đường đi ngắn nhất (SPR). Cụ thể, năng lượng còn lại trung bình của các nút gần trạm gốc tăng khoảng 15-20% so với SPR, giảm thiểu hiện tượng cạn kiệt năng lượng tập trung.

2. Tăng tuổi thọ mạng: Thuật toán LBR kéo dài thời gian hoạt động của mạng trước khi nút cảm biến đầu tiên cạn kiệt năng lượng. Thời gian sống mạng tăng khoảng 25% so với SPR trong các mô phỏng với 100 nút trên diện tích 500x500 m².

3. Tăng tổng số gói dữ liệu nhận tại trạm gốc: Số lượng gói dữ liệu thành công được truyền về trạm gốc tăng khoảng 18% khi sử dụng thuật toán LBR so với SPR, nhờ giảm thiểu mất mát do phân vùng mạng và cân bằng tải năng lượng.

4. Ảnh hưởng của bán kính liên lạc và số lượng nút: Khi tăng bán kính liên lạc từ 80 m lên 100 m, hiệu quả cân bằng tải và tuổi thọ mạng được cải thiện rõ rệt, với mức tăng tuổi thọ mạng khoảng 10%. Tương tự, tăng số lượng nút cảm biến trong cùng diện tích giúp phân phối tải năng lượng tốt hơn, kéo dài tuổi thọ mạng.

Thảo luận kết quả

Nguyên nhân chính của sự cải thiện là do thuật toán LBR không chỉ dựa vào khoảng cách ngắn nhất mà còn ưu tiên các nút có năng lượng còn lại cao hơn trong quá trình lựa chọn nút chuyển tiếp. Điều này giúp tránh việc quá tải năng lượng tại các nút gần trạm gốc, vốn là điểm yếu của thuật toán SPR. Kết quả mô phỏng được minh họa qua các biểu đồ phân bố năng lượng còn lại và số lượng gói dữ liệu truyền nhận tại các nút cảm biến, cho thấy sự phân bố đồng đều và hiệu quả hơn của LBR.

So sánh với các nghiên cứu trước đây tập trung vào Mobile Ad Hoc Networks (MANET), nghiên cứu này đã điều chỉnh thuật toán phù hợp với đặc thù của WSN, đặc biệt là tính năng năng lượng hạn chế và cấu trúc mạng tĩnh hoặc ít di động. Việc sử dụng mô phỏng Monte Carlo cũng giúp đánh giá độ tin cậy và tính ổn định của thuật toán trong các điều kiện mạng khác nhau.

Ý nghĩa của kết quả là cung cấp một giải pháp định tuyến hiệu quả, tiết kiệm năng lượng và nâng cao tuổi thọ mạng cảm biến không dây, góp phần phát triển các ứng dụng giám sát môi trường, y tế, và công nghiệp sử dụng WSN.

Đề xuất và khuyến nghị

1. Triển khai thuật toán định tuyến cân bằng tải trong các hệ thống WSN thực tế: Khuyến nghị các nhà phát triển và kỹ sư mạng áp dụng thuật toán LBR để cân bằng năng lượng và kéo dài tuổi thọ mạng, đặc biệt trong các ứng dụng giám sát môi trường và công nghiệp. Thời gian triển khai dự kiến trong vòng 6-12 tháng.

2. Tối ưu hóa tham số bán kính liên lạc và mật độ nút: Đề xuất điều chỉnh bán kính liên lạc và mật độ nút cảm biến phù hợp với môi trường triển khai để tối ưu hóa hiệu quả cân bằng tải và tuổi thọ mạng. Chủ thể thực hiện là các nhà thiết kế mạng và kỹ sư triển khai.

3. Phát triển phần mềm mô phỏng và công cụ đánh giá thuật toán: Khuyến khích xây dựng các công cụ mô phỏng nâng cao dựa trên Matlab hoặc các nền tảng khác để đánh giá hiệu quả thuật toán trong các điều kiện mạng đa dạng, hỗ trợ nghiên cứu và phát triển tiếp theo. Thời gian thực hiện 3-6 tháng.

4. Nâng cao khả năng thích ứng với biến động mạng: Đề xuất nghiên cứu bổ sung các cơ chế thích ứng động cho thuật toán LBR nhằm xử lý các biến động về cấu trúc mạng, lỗi liên kết và thay đổi vị trí nút cảm biến, đảm bảo tính ổn định và tin cậy của mạng trong thực tế. Chủ thể thực hiện là các nhà nghiên cứu và phát triển phần mềm.

Đối tượng nên tham khảo luận văn

1. Nhà nghiên cứu và sinh viên ngành kỹ thuật điện tử, viễn thông: Luận văn cung cấp kiến thức chuyên sâu về thuật toán định tuyến tiết kiệm năng lượng trong mạng cảm biến không dây, hỗ trợ nghiên cứu và phát triển các đề tài liên quan.

2. Kỹ sư phát triển hệ thống mạng cảm biến không dây: Các kỹ sư có thể áp dụng giải pháp định tuyến cân bằng tải để thiết kế và triển khai các hệ thống WSN hiệu quả, nâng cao tuổi thọ mạng và giảm chi phí bảo trì.

3. Doanh nghiệp và tổ chức ứng dụng WSN trong giám sát môi trường, y tế, công nghiệp: Luận văn giúp hiểu rõ các yếu tố ảnh hưởng đến tuổi thọ mạng và cách tối ưu hóa hệ thống để đảm bảo hoạt động liên tục và ổn định.

4. Nhà quản lý dự án công nghệ thông tin và viễn thông: Cung cấp cơ sở khoa học để đánh giá và lựa chọn giải pháp công nghệ phù hợp cho các dự án triển khai mạng cảm biến không dây, đảm bảo hiệu quả kinh tế và kỹ thuật.

Câu hỏi thường gặp

1. Tại sao cần cân bằng tải năng lượng trong mạng cảm biến không dây?
   Cân bằng tải giúp phân phối đồng đều năng lượng tiêu hao giữa các nút, tránh cạn kiệt năng lượng tập trung tại một số nút quan trọng, từ đó kéo dài tuổi thọ mạng và duy trì tính liên tục của hệ thống.

2. Thuật toán định tuyến cân bằng tải khác gì so với định tuyến đường đi ngắn nhất?
   Thuật toán cân bằng tải không chỉ dựa vào khoảng cách ngắn nhất mà còn tính đến năng lượng còn lại của nút cảm biến, ưu tiên các nút có năng lượng cao hơn để tránh quá tải và cạn kiệt năng lượng sớm.

3. Phương pháp mô phỏng nào được sử dụng để đánh giá thuật toán?
   Luận văn sử dụng mô phỏng Matlab 2013a với mô hình mạng 100 nút cảm biến phân bố ngẫu nhiên, kết hợp mô phỏng Monte Carlo để đánh giá hiệu quả thuật toán trong các điều kiện khác nhau.

4. Làm thế nào để áp dụng thuật toán này trong thực tế?
   Thuật toán có thể được tích hợp vào phần mềm điều khiển mạng cảm biến, yêu cầu cập nhật bảng định tuyến dựa trên năng lượng còn lại và khoảng cách, phù hợp với các thiết bị cảm biến có khả năng xử lý và giao tiếp không dây.

5. Thuật toán có khả năng thích ứng với biến động mạng không?
   Thuật toán được thiết kế để thích ứng với các biến động liên kết và lỗi nút thông qua cập nhật thông tin định tuyến tại chỗ, tuy nhiên cần nghiên cứu thêm để nâng cao khả năng thích ứng trong môi trường mạng động phức tạp.

Kết luận

• Thuật toán định tuyến cân bằng tải bổ sung trọng số nghịch đảo năng lượng còn lại vào thuật toán đường đi ngắn nhất, giúp phân phối đồng đều năng lượng tiêu hao trên mạng cảm biến không dây.
• Mô phỏng trên Matlab với 100 nút cảm biến cho thấy tuổi thọ mạng tăng khoảng 25%, số gói dữ liệu truyền thành công tăng 18% so với thuật toán định tuyến đường đi ngắn nhất.
• Thuật toán giúp giảm thiểu hiện tượng cạn kiệt năng lượng tập trung tại các nút gần trạm gốc, tránh phân vùng mạng và nâng cao độ tin cậy truyền dữ liệu.
• Nghiên cứu đề xuất các giải pháp triển khai thực tế, tối ưu tham số mạng và phát triển công cụ mô phỏng hỗ trợ đánh giá hiệu quả thuật toán.
• Các bước tiếp theo bao gồm phát triển cơ chế thích ứng động cho thuật toán và mở rộng mô hình mô phỏng trong các môi trường mạng đa dạng hơn.

Hành động ngay: Các nhà nghiên cứu và kỹ sư được khuyến khích áp dụng và phát triển thuật toán định tuyến cân bằng tải để nâng cao hiệu quả và tuổi thọ mạng cảm biến không dây trong các ứng dụng thực tế.

Trích đoạn nội dung tài liệu

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 Luan van 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. DƢƠNG HOÀI NGHĨA Tp. Hồ Chí Minh, Tháng 10/2015 Luan van 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. 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 Luan van 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. 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 Luan van 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 Luan van 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 Luan van 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 Luan van 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. Lý do chọn đề tài 1 1.

Mục tiêu nghiên cứu 2 1. Nhiệm vụ nghiên cứu 2 1. Khách thể và đối tƣợng nghiên cứu 3 1. Giả thuyết nghiên cứu 3 1.

Phạm vi nghiên cứu 3 1. Phƣơng pháp nghiên cứu 3 1. Kế hoạch thực hiện 4 Chƣơng 2: CƠ SỞ LÝ THUYẾT 5 2. Tổng quan về mạng cảm biến không dây 5 2.

Giới thiệu về IEEE 802. 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.

Quản lý khe thời gian đảm bảo 10 2. Chế độ truyền dữ liệu 10 2. Một số giao thức định tuyến trong mạng cảm biến không dây 11 vi Luan van 2. Một số ví dụ triển khai 13 2.

Kết luận chƣơng 14 Chƣơng 3: ĐỊNH TUYẾN CÂN BẰNG TẢI 15 3. Khung định tuyến 15 3. Cấu hình và duy trì mạng 18 3. Các giai đoạn thành lập định tuyến 20 3.

Quá trình lựa chọn nút chuyển tiếp thích ứng 21 3. 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. Tổng hợp và phân phối dữ liệu cân bằng 24 3. Tổng hợp nhận thức tại 24 3.

Giới hạn thời hạn chuyển tiếp 26 3. Định tuyến cân bằng năng lƣợng 28 3. Năng lƣợng tiêu hao trung bình trên mỗi tuyến đƣờng 28 3. Năng lƣợng và xác suất tin cậy 30 3.

Xác suất chuyển tiếp gói dữ liệu 31 3. Mô hình cân bằng năng lƣợng 32 3. Sự tiêu thụ năng lƣợng trên mỗi nút cảm biến chuyển tiếp 34 3. Kết luận chƣơng 37 Chƣơng 4:MÔ PHỎNG ĐỊNH TUYẾN CÂN BẰNG TẢI 38 4.

Các thông số mô phỏng 38 4. Phƣơng pháp định tuyến 39 4. Các trƣờng hợp mô phỏng 41 4. Phân bố đều các nút cảm biến 41 4.

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. 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 Luan van 4. Phân bố ngẫu nhiên các nút cảm biến 47 4. 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.

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. Ả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. Mô phỏng Monte Carlo 56 4. Kết luận chƣơng 58 Chƣơng 5:KẾT LUẬN 59 5.

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 Luan van 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 Luan van 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 Luan van 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.