i LỜI CAM ĐOAN Tôi cam đoan công trình nghiên cứu riêng tơi Các số liệu, kết nêu luận văn trung thực chưa cơng bố cơng trình khác Tác giả luận văn Ký tên Lê Văn Bé ii LỜI CẢM ƠN Sau thời gian học tập nghiên cứu, luận văn hoàn thành Với tình cảm chân thành, chúng tơi xin bày tỏ lịng biết ơn đến: Học viện Cơng nghệ Bưu Viễn thông , Khoa Quốc Tế & Đào Tạo Sau Đại học, Quý Thầy Cô giảng viên, cán bộ, công nhân viên Học viện tạo điều kiện cho tác giả tham gia khoá học Xin cảm ơn Quý Thầy Cơ tận tình giảng dạy, giúp đỡ, cung cấp tài liệu, hướng dẫn tác giả trình học tập nghiên cứu khoa học Đặc biệt, xin bày tỏ lòng biết ơn sâu sắc đến PGS.TS Trần Cơng Hùng tận tình giúp đỡ, hướng dẫn tác giả suốt q trình nghiên cứu hồn thành luận văn tốt nghiệp Xin cảm ơn Quý đồng nghiệp, gia đình, bạn bè động viên, giúp đỡ chúng tơi suốt q trình học tập nghiên cứu Mặc dù cố gắng hết sức, song chắn luận văn khơng tránh khỏi thiếu sót, mong nhận đóng góp, dẫn giúp đỡ Quý Thầy Cô giáo, Quý đồng nghiệp để luận văn hoàn thiện Xin trân trọng cảm ơn! Tác giả iii MỤC LỤC MỞ ĐẦU Chương 1: TỔNG QUAN VỀ MẠNG CẢM BIẾN KHÔNG DÂY .2 1.1 Giới Thiệu 1.2 Tổng quan kỹ thuật WSN 1.2.1 Các thành phần WSN 1.2.2 Cấu trúc mạng cảm biến không dây 1.2.3 Hệ điều hành cho WSN 1.3 Các đặc trưng mạng cảm biến không dây 12 1.3.1 Năng lượng tiêu thụ 12 1.3.2 Chi phí 12 1.3.3 Loại hình mạng 13 1.3.4 Tính bảo mật 13 1.3.5 Độ trễ 14 1.3.6 Tính di động 14 1.4 Các thách thức trở ngại 14 1.4.1 Giới hạn lượng 14 1.4.2 Giới hạn phần cứng 15 1.4.3 Ảnh hưởng nhiễu bên 15 1.5 Kết luận 15 Chương 2: PHƯƠNG PHÁP PHÂN CỤM TRUYỀN THỐNG 16 2.1 Giao Thức LEACH 16 2.1.1 Giới thiệu 16 2.1.2 Tự động cấu hình hình thành cụm 17 2.1.3 Lựa chọn node chủ cụm 17 2.1.4 Pha cài đặt 18 2.1.5 Pha ổn định 20 2.1.6 Tổng hợp liệu 24 2.2 Giao thức LEACH-C 25 iv 2.3 Giao thức PEGASIS 2.3.1 Tổng quan giao 2.3.2 Hoạt động gia 2.4 So sánh giao thức PEGASIS LEACH 2.4.1 Ưu điểm 2.4.2 Nhược điểm 2.5 Kết luận Chương 3: PHƯƠNG PHÁP PHÂN CỤM TỐI ƯU BẦY ĐÀN 3.1 Tổng quan thuật tốn tối ưu hóa bầy đàn (PSO: P OPTIMIZATION) 3.2 Lưu đồ thuật toán PSO 3.3 Thuật toán PSO cải tiến 3.4 Kết luận Chương 4: MÔ PHỎNG VÀ ĐÁNH GIÁ 4.1 Mơ hình mạng 4.2 Mơ hình lượng 4.3 Mô đánh giá 4.4 Kết luận hướng phát triển TÀI LIỆU THAM KHẢO v DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ADC ADV API BS CDMA CPU CSMA CH DS-SS GA ID I/O LEACH LEACH-C MAC OS PEGASIS PSO TDMA WSN vi DANH MỤC CÁC BẢNG SỐ HIỆU BẢNG 2.1 TÊN BẢNG So sánh giao thức PEGASIS LEACH TRANG 34 SỐ HIỆU HÌNH VẼ 1.1 1.2 1.3 1.4 1.5 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 2.12 2.13 3.1 3.2 3.3 4.1 4.2 MỞ ĐẦU Trong năm gần đây, tiến khoa học kỹ thuật, việc sản xuất thiết bị cảm biến nhỏ chi phí thấp trở nên khả thi mặt kỹ thuật mặt kinh tế Việc thiết kế thực có hiệu mạng cảm biến không dây (WSN) trở thành lĩnh vực thu hút nhiều quan tâm tiềm ứng dụng WSN lĩnh vực đời sống hàng ngày y tế, công nghiệp, quân sự… Với mục tiêu giảm giá thành tăng hiệu công nghiệp thương mại, mạng cảm biến không dây mang đến tiện nghi ứng dụng thiết thực nâng cao chất lượng sống cho người Tuy vậy, việc thiết kế thực có hiệu WSN phải đối mặt với nhiều thách thức Một thách thức lớn WSN nguồn lượng bị giới hạn Nguồn lượng cho WSN hệ thống pin, thời gian sống WSN tùy thuộc vào tiêu hao lượng nên vấn đề tiêu thụ lượng tiêu chí thiết kế quan trọng cho WSN Vấn đề đặt tìm giải pháp để cảm biến thu nhận tốt tín hiệu với tiêu hao lượng nhỏ Các giao thức phân cụm truyền thống phân cụm dựa vào thuật tốn tối ưu hóa bầy đàn (PSO) giải pháp mang lại hiệu việc tiết kiệm lượng Đề tài “Đánh giá mức độ hiệu lượng phương pháp tối ưu PSO so với phương pháp phân cụm truyền thống mạng cảm biến khơng dây” với mục đích so sánh mức độ tiêu thu lượng WSN áp dụng thuật toán phân cụm truyền thống thuật toán PSO Chương 1: TỔNG QUAN VỀ MẠNG CẢM BIẾN KHÔNG DÂY 1.1 Giới Thiệu WSN [1] cấu trúc, kết hợp khả xử lý thông tin thành phần liên lạc để tạo khả quan sát, phân tích phản ứng lại với kiện tượng xảy mơi trường cụ thể Mơi trường giới vật lý, hệ thống sinh học Các ứng dụng WSN chủ yếu bao gồm thu thập liệu, giám sát, theo dõi, ứng dụng y học Tuy nhiên, ứng dụng WSN tùy theo yêu cầu đa dạng khơng bị giới hạn Có thành phần cấu tạo nên WSN: Các cảm biến phân bố theo mơ hình tập trung hay phân bổ rải Mạng lưới liên kết cảm biến (có dây hay vơ tuyến) Điểm tập trung tập hợp liệu Bộ phận xử lý liệu trung tâm Một node cảm biến định nghĩa kết hợp cảm biến phận xử lý Ứng dụng WSN: Quân sự: theo dõi mục tiêu, chiến trường, nguy công nguyên tử, sinh hóa,… Mơi trường: giám sát cháy rừng, thay đổi khí hậu, bão, lũ lụt,… Y tế, sức khỏe: giám sát bệnh nhân bệnh viện, quản lý thuốc, điều khiển từ xa,… Gia đình: ngơi nhà thơng minh, điều khiển thiết bị điện, hệ thống sưởi ấm,… Thương mại: điều khiển mơi trường cơng nghiệp văn phịng, giám sát xe cộ, giao thông,… 1.2 Tổng quan kỹ thuật WSN 1.2.1 Các thành phần WSN Các thành phần cấu tạo [1,2] nên node WSN (hình 1.1) : Một cảm biến (có thể hay dãy cảm biến) đơn vị thực thi (nếu có) Đơn vị xử lý Đơn vị liên lạc vô tuyến Nguồn cung cấp Các phần ứng dụng khác… angten Đơn vị cảm biến #1 Đơn vị cảm biến #2 Cảm biến biến ADC Đơn vị Xử lý Bộ xử lý ADC Lưu trữ Bộ thu phát Đơn vị nguồn ADC: chuyển đổi analog sang digital Hình 1.1 Các thành phần Node 1.2.2 Cấu trúc mạng cảm biến không dây Cấu trúc mạng cảm biến không dây cần phải thiết kế cho sử dụng có hiệu nguồn tài nguyên hạn chế mạng, kéo dài thời gian sống mạng Vì thiết kế cấu trúc mạng cần phải quan tâm đến yếu tố sau: - Giao tiếp không dây đa chặng: Khi giao tiếp không dây kĩ thuật chính, giao tiếp trực tiếp hai node có nhiều hạn chế khoảng cách hay vật cản Đặc biệt node phát node thu cách xa cần cơng suất phát lớn.Vì cần node trung gian làm node chuyển tiếp để giảm công suất tổng thể Do mạng cảm biến không dây cần phải dùng giao tiếp đa chặng - Sử dụng hiệu lượng: để hỗ trợ kéo dài thời gian sống toàn mạng, sử dụng hiệu lượng kĩ thuật quan trọng mạng cảm biến không dây - Tự động cấu hình: Mạng cảm biến khơng dây cần phải cấu hình thơng số tự động Chẳng hạn node xác định vị trí địa lý thơng qua node khác (gọi tự định vị) - Cộng tác, xử lý mạng tập trung liệu: Trong số ứng dụng node cảm biến không thu thập đủ liệu mà cần phải có nhiều node cộng tác hoạt động thu thập đủ liệu, mà node thu liệu gửi đến trạm gốc tốn băng thơng lượng Cần phải kết hợp liệu nhiều node vùng gửi tới trạm gốc tiết kiệm băng thông lượng Chẳng hạn xác định nhiệt độ trung bình, hay cao vùng Do vậy, cấu trúc mạng thiết kế phải thỏa mãn: - Kết hợp vấn đề lượng khả định tuyến - Tích hợp liệu giao thức mạng - Truyền lượng hiệu qua phương tiện không dây - Chia sẻ nhiệm vụ node lân cận 34 Bảng 2.1 So sánh giao thức PEGASIS LEACH Feature Khoảng cách truyền liệu Lượng liệu node chủ nhận Số node truyền liệu đến trạm gốc Trễ Yêu cầu với node 2.5 Kết luận Trong chương giới thiệu tổng quan giao thức LEACH, cách hình thành cụm pha cài đặt trình trao đổi liệu pha ổn định vịng q trình hoạt động giao thức LEACH Bên cạnh trình bày nhược điểm giao thức LEACH để từ giới thiệu giao thức cải tiến LEACH C Trong chương trình bày giao thức PEGASIS bao gồm mô tả chi tiết hoạt động giao thức so sánh với giao thức LEACH Trong chương trình bày giao thức dựa thuật toán PSO 35 Chương 3: PHƯƠNG PHÁP PHÂN CỤM TỐI ƯU BẦY ĐÀN 3.1 Tổng quan thuật tốn tối ưu hóa bầy đàn (PSO: PARTICLE SWARM OPTIMIZATION) PSO kỹ thuật tối ưu hóa ngẫu nhiên dựa quần thể sau tìm nghiệm tối ưu cách cập nhật hệ, phát triển Dr.Eberhart Dr.Kennedy, theo hành vi bầy chim hay đàn cá [9,10] PSO có nhiều tương tự kỹ thuật tính tốn tiến hóa thuật tốn di truyền (GA: Genetic algorithm) Tuy nhiên, khơng giống GA, PSO khơng có thao tác tiến hóa lai ghép hay đột biến Trong hệ thống PSO, phần tử bầy đàn thay đổi vị trí cách di chuyển nhiều vị trí khác khơng gian tìm kiếm tìm vị trí tốt Khái niệm thay đổi điểm tìm kiếm thuật giải PSO biễu diễn hình 3.1 Hình 3.1 Khái niệm thay đổi điểm tìm kiếm PSO Trong đó: XiK: Vị trí cá thể thứ i hệ thứ k XiK+1: Vị trí cá thể thứ i hệ thứ k+1 ViK: Vận tốc cá thể thứ i hệ thứ k ViK+1: Vận tốc cá thể thứ i hệ thứ k+1 ViPbest : Vận tốc theo Pbest 36 Vi: Vận tốc theo Gbest Pbest: Vị trí tốt cá thể thứ i Gbest: Vị trí tốt cá thể quần thể Để cho dễ hiểu tư tưởng thuật tốn PSO Chúng ta xem xét ví dụ sau: giả sử có bầy chim tìm kiếm thức ăn vùng Tất chim thức ăn đâu Tuy nhiên, chúng biết thức ăn cách xa sau lần bay bay lại (lặp) Câu hỏi đặt là: cách tốt để tìm thức ăn gì? Câu trả lời đơn giản theo sau chim gần chỗ thức ăn PSO theo kịch sử dụng để giải toán tối ưu Trong PSO, giải pháp đơn ví dụ cá thể gọi particle, cụ thể môi trường WSN node cảm biến Mỗi node có giá trị thích nghi đánh giá hàm đo độ thích nghi vận tốc để định hướng việc bay tìm kiếm Các node duyệt khơng gian tốn cách theo sau node có điều kiện tốt thời PSO khởi tạo nhóm ngẫu nhiên node, sau tìm kiếm giải pháp tối ưu việc cập nhật hệ Trong hệ, particle cập nhật hai giá trị: giá trị thứ nhất, gọi PBest (là nghiệm tốt đạt thời điểm tại) giá trị thích nghi node tốt hệ thời Giá trị thứ hai, gọi GBest (là nghiệm tốt mà node lân cận node đạt thời điểm tại) giá trị thích nghi node tốt tất hệ từ trước đến Nói cách khác, node mạng cập nhật vị trí theo vị trí tốt node khác mạng tính tới thời điểm Quá trình cập nhật node dựa hai cơng thức sau [11]: vik+1=w vik +c1*rand()*(Pbesti-xik)+c2*rand()*(Gbestm- xik) xik+1=xik+vik+1 ; i=1,2,…,n; Trong - n: Số phần tử nhóm 37 - k: thứ tự lần lặp - vik: Vận tốc node i lần lập thứ k - vik+1: Vận tốc node i lần lập thứ k+1 - w : Trọng số quán tính - c1,c2: Hệ số gia tốc - Rand (): Là số ngẫu nhiên khoảng (kích cỡ cụm, số chiều khơng gian tìm kiếm) - xik: Vị trí node thứ i lần lặp thứ k - xik+1: Vị trí node thứ i lần lặp thứ k+1 - Pibest i : Vị trí tốt node thứ i - Gbest i : Vị trí tốt node mạng Thuật tốn PSO có giá trị trọng số quán tính từ 0.4 đến 0.9 hệ số gia tốc thiết lập Các lần thay đổi tính cơng thức sau: w=(weight-0.4)* +0.4 (3.3) Trong đó, MAXITER số lần lặp tối đa cho phép, iter số lần lặp weight số thiết lập 0.9 Cơng thức cập nhật tốc độ (3.1) có thành phần [12] sau: Thành phần gọi qn tính hay thói quen Nó định hướng node tiếp tục hướng vòng sau Thành phần thứ ảnh hưởng tuyến tính đến vị trí tốt tìm thấy node: Pi (có giá trị thích nghi tương ứng gọi node tốt Pbest) Thành phần gọi “nhớ” hay “tự nhận biết” Thành phần thứ công thức cập nhật tốc độ ảnh hưởng tuyến tính đến vị trí tốt tìm thấy node: Pg (có giá trị thích nghi tương ứng gọi tốt toàn cục: Gbest) Thành phần gọi “hợp tác” hay “nhận biết xã hội” hay “thông tin chia sẻ” 38 3.2 Lưu đồ thuật tốn PSO KHỞI TẠO Khởi tạo vị trí tốc độ node Tính tốn giá trị thích nghi node pbest = node tốt nhất, gbest = pbest Bước lặp = Bắt đầu lặp Cập nhật tốc độ node (3.1) Cập nhật vị trí node (3.2) Đánh giá giá trị thích nghi node Cập nhật pbest gbest n Hình 3.2 Lưu đồ thuật tốn PSO Hình 3.2 cho thấy sơ đồ thuật toán PSO Đối với WSN với n node K số xác định trước cụm, trình hình thành cụm gồm bước sau: Khởi tạo vị trí tốc độ node Tính tốn giá trị thích nghi node để tìm Pbest Gbest với công thức sau a Với node ni, i=1, 2,…, N 39 i Tính tốn khoảng cách d(ni, CHp,k) node ni tất cụm chủ CHp,k ii Gán node ni cho cụm chủ CHp,k (3.3) b Tính tốn hàm chi phí sử dụng phương trình sau: cos t = (3.5) (3.6) Trong đó, f1 khoảng cách trung bình tối đa node đến cụm chủ |Cp,k| số lượng node thuộc cụm Ck cá thể p Hàm f2 tỉ số toàn lượng khởi tạo tất node ni, i=1,2,…,N mạng với tồn lượng có cụm chủ vòng Hằng số số người dùng định nghĩa dùng để đo mức độ thích nghi mục tiêu nhỏ Hàm mục tiêu f1 xác định có mục tiêu đồng thời tối thiểu khoảng cách node cụm cụm chủ hàm f2 có mục tiêu tối ưu lượng mạng Cập nhật tốc độ, vị trí node cơng thức (3.1) (3.2) Tính tốn lại giá trị thích nghi node để từ tìm P best Gbest Lặp lại bước đến bước số bước lặp tối đa node hết lượng 40 3.3 Thuật toán PSO cải tiến Trong q trình tìm hiểu thuật tốn PSO nhận thấy rằng, thời điểm cập nhật tốc độ của cá thể xét Từ dẫn đến q trình tìm kiếm thức ăn (hội tụ) cá thể chậm lại Để hạn chế vấn đề đề xuất cần phải cập nhật tốc độ cho cá thể lân cận cá thể xét với công thức sau: vik+1=w.vik +c1*rand()*(Pbesti-xik)+c2*rand()*(Gbest-xik)+c3*rand()*(Bbesti-xik) (7) Trong đó: - n: Số phần tử nhóm - k: thứ tự lần lặp - vik: Vận tốc node i lần lập thứ k - vik+1: Vận tốc node i lần lập thứ k+1 - w : Trọng số quán tính - c1, c2, c3: Hệ số gia tốc - Rand (): Là số ngẫu nhiên khoảng (kích cỡ cụm, số chiều khơng gian tìm kiếm) - xik: Vị trí node thứ i lần lặp thứ k - xik+1: Vị trí node thứ i lần lặp thứ k+1 - Pibest i : Vị trí tốt node thứ i - Gbest : Vị trí tốt node mạng - Bbest : Vị trí tốt node so với lân cận khác i Ngồi ra, để q trình hội cá thể nhanh thuật toán chúng tơi cịn thiết lập giá trị tốc độ tối đa V max Nếu V >Vmax gán V=Vmax, V