›
›

Đồ án Đánh giá một số giao thức trong mạng cảm nhận không dây bằng mô phỏng NS2

pdf 62 trang huongle 2970
Download
Bạn đang xem 20 trang mẫu của tài liệu "Đồ án Đánh giá một số giao thức trong mạng cảm nhận không dây bằng mô phỏng NS2", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfdo_an_danh_gia_mot_so_giao_thuc_trong_mang_cam_nhan_khong_da.pdf

Nội dung text: Đồ án Đánh giá một số giao thức trong mạng cảm nhận không dây bằng mô phỏng NS2

  1. Báo cáo đồ án tốt nghiệp LỜI CẢM ƠN Trước hết em xin được bày tỏ lòng biết ơn sâu sắc đối với thầy giáo hướng dẫn Thạc sĩ Nguyễn Trọng Thể, Khoa Công Nghệ Thông Tin - Trường Đại học Dân lập Hải Phòng; cô giáo hướng dẫn Thạc sĩ Đào Thị Kiên, Khoa Công Nghệ Thông Tin - Trường Cao đẳng Cộng đồng Hải Phòng đã tận tình giúp đỡ, chỉ bảo em trong những năm học qua và đã dành rất nhiều thời gian quí báu để giúp em hoàn thành báo cáo thực tập được giao. Em xin gửi lời cảm ơn đến Ban giám hiệu, các Thầy cô giáo của Trường Đại học Dân Lập Hải Phòng đã giảng dạy chúng em trong suốt quãng thời gian qua, cung cấp cho chúng em những kiến thức chuyên môn cần thiết và quý báu giúp chúng em hiểu rõ hơn các lĩnh vực đã nghiên cứu để hoàn thành đề tài được giao . Xin cảm ơn các bạn bè và gia đình đã động viên cổ vũ, đóng góp ý kiến, trao đổi, động viên trong suốt quá trình học cũng như làm tốt nghiệp, giúp em hoàn thành đề tài đúng thời hạn. Hải Phòng, tháng 7 năm 2009 Sinh viên Đỗ Đức Hưng Sinh viên: Đỗ Đức Hưng - Lớp CT902 1 Trường ĐHDL Hải Phòng
  2. Báo cáo đồ án tốt nghiệp MụC LỤC LỜI NÓI ĐẦU 4 DANH SÁCH TỪ VIẾT TẮT 5 CHƢƠNG 1: GIỚI THIỆU VỀ MẠNG CẢM BIẾN KHÔNG DÂY 7 1.1. Giới thiệu 7 1.2. Cấu trúc mạng cảm biến không dây 7 1.2.1 Cấu trúc phẳng 8 1.2.2 Cấu trúc phân cấp 9 1.3. Các đặc trưng của mạng cảm biến không dây 11 1.3.1 Năng lượng tiêu thụ 11 1.3.2 Chi phí 11 1.3.3 Loại hình mạng 11 1.3.4 Tính bảo mật 12 1.3.5 Độ trễ 12 1.3.6 Tính di động 12 1.4 Những khó khăn trong việc phát triển mạng không dây 13 1.4.1 Giới hạn năng lượng 13 1.4.2 Giới hạn về giải thông 13 1.4.3 Giới hạn về phần cứng 13 1.4.4 Ảnh hưởng của nhiễu bên ngoài 13 CHƢƠNG 2: ĐỊNH TUYẾN TRONG MẠNG CẢM BIẾN KHÔNG DÂY 14 2.1 Các vấn đề cần lưu ý đối với giao thức định tuyến 14 2.1.1 Đặc tính thay đổi thời gian và trật tự sắp xếp của mạng 14 2.1.2. Ràng buộc về tài nguyên 14 2.1.3 Mô hình dữ liệu trong mạng cảm biến 14 2.1.4. Cách truyền dữ liệu 15 2.2 Các giao thức định tuyến trong mạng cảm biến không dây 15 2.2.1 Các giao thức xét theo cấu trúc mạng 16 2.2.1.1 Giao thức định tuyến ngang hàng 16 Sinh viên: Đỗ Đức Hưng - Lớp CT902 2 Trường ĐHDL Hải Phòng
  3. Báo cáo đồ án tốt nghiệp 2.2.1.2 Các giao thức phân cấp 18 2.2.1.3 Giao thức định tuyến dựa theo vị trí 22 2.2.2 Các giao thức định tuyến xét theo hoạt động 23 CHƢƠNG 3: MÔ PHỎNG MỘT SỐ GIAO THỨC ĐỊNH TUYẾN VÀ ĐÁNH GIÁ KẾT QUẢ 27 3.1 Phần mềm mô phỏng mạng NS-2 27 3.1.1 Giới thiệu về NS2 27 3.1.2 C++ và OTcl 30 3.1.3 Các đặc tính của NS-2 33 3.2 Mô phỏng mạng cảm biến không dây trên NS-2 33 3.2.1 Bài toán mô phỏng 33 3.2.2 Mô hình phần mềm 34 3.2.3 Các giao thức mô phỏng 35 3.2.3.1 LEACH 35 3.2.3.2 LEACH-C (LEACH-Centralized) 43 3.2.3.3 Phân cụm cố định (Stat-Cluster) 44 3.2.3.4 Năng lượng truyền tối thiểu (Minimum Transmit Energy) 45 3.2.4 Mô phỏng 46 KẾT LUẬN 61 CÁC TÀI LIỆU THAM KHẢO 62 Sinh viên: Đỗ Đức Hưng - Lớp CT902 3 Trường ĐHDL Hải Phòng
  4. Báo cáo đồ án tốt nghiệp LỜI NÓI ĐẦU Trong những năm gần đây, do sự tiến bộ của khoa học kỹ thuật, việc sản xuất các thiết bị cảm biến nhỏ và chi phí thấp trở nên khả thi về mặt kỹ thuật và mặt kinh tế. Việc thiết kế và thực hiện có hiệu quả mạng cảm biến không dây trở thành lĩnh vực thu hút được nhiều sự quan tâm vì tiềm năng ứng dụng của mạng cảm biến trong các lĩnh vực trong đời sống hàng ngày như trong y tế, trong công nghiệp, trong quân sự Tuy vậy, việc thiết kế và thực hiện có hiệu quả mạng cảm biến không dây phải đối mặt với rất nhiều thách thức, một trong những thách thức lớn nhất trong mạng cảm biến là nguồn năng lượng bị giới hạn và không thể nạp lại, chính vì thế hiện nay rất nhiều nghiên cứu đang tập trung vào việc cải thiện khả năng sử dụng hiệu quả năng lượng của toàn mạng. Xuất phát từ những phát từ những yêu cầu thực tế đó, đề tài “Đánh giá một số giao thức trong mạng cảm nhận không dây bằng mô phỏng NS2” thực hiện việc giới thiệu một cách tổng quan về mạng cảm biến không dây, các giao thức cũng như các giải thuật định tuyến thường được dùng: LEACH, LEACH-C, MTE, STAT- CLUSTER, đồng thời sử dụng phần mềm NS-2 để mô phỏng, đánh giá 4 giao thức đó. Đồ án gồm có 3 chương: Chƣơng 1: Tổng quan về mạng cảm biến không dây (WSN): đưa ra định nghĩa, cấu trúc mạng WSN, các yếu tố ảnh hưởng đến cấu trúc mạng WSN, các thách thức mà mạng WSN phải đối mặt. Chƣơng 2: Định tuyến trong mạng cảm biến không dây: đưa ra các vấn đề phải đối mặt khi định tuyến, đưa ra các giao thức định tuyến đang được dùng trong mạng cảm biến và trình bày cách phân loại các cách tiếp cận với vấn đề này. Ba loại định tuyến chính được đưa ra trong chương này là giao thức trung tâm dữ liệu, giao thức phân cấp và giao thức dựa vào vị trí. Chƣơng 3: Mô phỏng một số giao thức định tuyến và đánh giá kết quả: Khái quát về phần mềm mô phỏng mạng NS-2 và xây dựng mô hình phần mềm mô phỏng cho các giao thức mạng. Phân tích và nghiên cứu các vấn đề về năng lượng, thời gian sống, dữ liệu truyền và thời gian trễ trên trạm gốc. Sinh viên: Đỗ Đức Hưng - Lớp CT902 4 Trường ĐHDL Hải Phòng
  5. Báo cáo đồ án tốt nghiệp DANH SÁCH TỪ VIẾT TẮT Chữ viết tắt Chữ đầy đủ Nghĩa tiếng Việt ACK Acknowledgement Bản tin phúc đáp ADC Analog-to-Digital Converter Bộ chuyển đổi tương tự - Số ADV Advertise Bản tin quảng bá AoA Angle of Arrival Góc đến BS Base Station (Sink) Trạm gốc CDMA Code Division Multiple Access Đa truy nhập phân chia theo mã DD Directed Diffusion Truyền tin trực tiếp EDD Enhanced Directed Diffusion Truyền tin trực tiếp nâng cao GAF Geographic adaptive fidelity Giải thuật chính xác theo địa lý GEAR Geographic and Energy-Aware Định tuyến theo vùng địa lý sử Routing dụng hiệu quả năng lượng GPS Global Positioning System Hệ thống định vị toàn cầu LEACH Low-energy adaptive clustering Giao thức phân cấp theo cụm hierarchy thích ứng năng lượng thấp MAC Media Access Control Điều khiển truy nhập môi trường PEGASIS Power-efficient Gathering in Tổng hợp năng lượng trong các Sensor Information Systems hệ thống thông tin cảm biến QoS Quality of Service Chất lượng dịch vụ REQ Request Bản tin yêu cầu RSS Received Signal Strength Độ mạnh tín hiệu thu được RSSI Received Signal Strength Bộ chỉ thị độ mạnh tín hiệu thu Indicator được SAR Sequential Assignment Routing Định tuyến phân phối tuần tự Sinh viên: Đỗ Đức Hưng - Lớp CT902 5 Trường ĐHDL Hải Phòng
  6. Báo cáo đồ án tốt nghiệp SMP Sensor Management Protocol Giao thức quản lí mạng cảm biến SPIN Sensor protocols for information Giao thức cho thông tin dữ liệu via negotiation thông qua đàm phán SQDDP Sensor Query and Data Giao thức phân phối dữ liệu và Dissemination Protocol truy vấn cảm biến TADAP Task Assignment and Data Giao thức quảng bá dữ liệu và chỉ Advertisement Protocol định nhiệm vụ cho từng cảm biến TCP Transmission Control Protocol Giao thức điều khiển truyền dẫn TDMA Time Division Multiple Access Đa truy nhập phân chia theo thời gian TEEN Threshold sensitive Energy Giao thức hiệu quả về năng lượng Efficient sensor Network protocol nhạy cảm với mức ngưỡng ToA Time of Arrival Thời gian đến UDP User Datagram Protocol Giao thức gói dữ liệu người dùng WINS Wireless Integrated Network Cảm biến mạng tích hợp không Sensors dây WSN Wireless Sensor Network Mạng cảm biến không dây Sinh viên: Đỗ Đức Hưng - Lớp CT902 6 Trường ĐHDL Hải Phòng
  7. Báo cáo đồ án tốt nghiệp CHƢƠNG 1: GIỚI THIỆU VỀ MẠNG CẢM BIẾN KHÔNG DÂY 1.1. Giới thiệu Mạng cảm biến không dây (WSN - Wireless Sensor Network) là mạng có hai chức năng: mạng và cạm nhận thông tin từ môi trường. Mạng WSN có dặc điểm các nút liên kết với nhau bằng kết nối sóng vô tuyến trong đó các nút mạng thường là các thiết bị đơn giản, nhỏ gọn, giá thành thấp Mạng loại này có thể có số lượng lớn, được phân bố một cách không có hệ thống trên một diện, sử dụng nguồn năng lượng hạn chế, có thời gian hoạt động lâu dài khoảng vài tháng đến vài năm, có thể hoạt động trong môi trường khắc nghiệt như: chất độc, ô nhiễm, nhiệt độ Các nút mạng thường có chức năng cảm nhận, quan sát môi trường xung quanh như nhiệt độ, độ ẩm, ánh sáng theo dõi hay định vị các mục tiêu cố định hoặc di động Các nút giao tiếp với nhau và truyền dữ liệu về trung tâm (base station) một cách gián tiếp bằng kỹ thuật đa chặng (multi-hop). 1.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ế sao cho sử dụng có hiệu quả nguồn tài nguyên hạn chế của mạng, kéo dài thời gian sống của mạng. Vì vậy thiết kế cấu trúc mạng và kiến trúc mạng phải cần phải quan tâm đến các yếu tố sau: - Giao tiếp không dây đa chặng: Khi giao tiếp không dây là kĩ thuật chính, thì giao tiếp trực tiếp giữa hai nút sẽ có nhiều hạn chế do khoảng cách hay các vật cản. Đặc biệt là khi nút phát và nút thu cách xa nhau thì cần công suất phát lớn.Vì vậy cần các nút trung gian làm nút chuyển tiếp để giảm công suất tổng thể. Do vậy các 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 quả năng lượng: để hỗ trợ kéo dài thời gian sống của toàn mạng, sử dụng hiệu quả năng lượng là 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 các thông số một các tự động. Chẳng hạn như các nút có thể xác định vị trí địa lý của nó thông qua các nút khác (gọi là tự định vị). Sinh viên: Đỗ Đức Hưng - Lớp CT902 7 Trường ĐHDL Hải Phòng
  8. Báo cáo đồ án tốt nghiệp - Cộng tác, xử lý trong mạng và tập trung dữ liệu: Trong một số ứng dụng một nút cảm biến không thu thập đủ dữ liệu mà cần phải có nhiều nút cùng cộng tác hoạt động thì mới thu thập đủ dữ liệu, khi đó mà từng nút thu dữ liệu gửi ngay đến trạm gốc thì sẽ rất tốn băng thông và năng lượng. Cần phải kết hợp các dữ liệu của nhiều nút trong một vùng rồi mới gửi tới trạm gốc thì sẽ tiết kiệm băng thông và năng lượng. Chẳng hạn như khi xác định nhiệt độ trung bình, hay cao nhất của một vùng. Do vậy, cấu trúc mạng được thiết kế sẽ phải thỏa mãn: - Kết hợp vấn đề năng lượng và khả năng định tuyến. - Tích hợp dữ liệu và giao thức mạng. - Truyền năng lượng hiệu quả qua các phương tiện không dây. - Chia sẻ nhiệm vụ giữa các nút lân cận. Các nút cảm biến được phân bố trong một vùng cảm biến như hình 1.1. Mỗi một nút cảm biến có khả năng thu thập dữ liệu và định tuyến lại đến các trạm gốc. Dữ liệu được định tuyến lại đến các trạm gốc bởi một cấu trúc đa điểm như hình vẽ trên. Các trạm gốc có thể giao tiếp với các nút quản lý nhiệm vụ (task manager node) qua mạng Internet hoặc vệ tinh. Hình 1.1 Cấu trúc mạng cảm biến không dây Có thể phân chia cấu trúc của mạng cảm biến thành 2 loại: cấu trúc phẳng và cấu trúc phân cấp 1.2.1 Cấu trúc phẳng Trong cấu trúc phẳng (flat architecture) (hình 1.2), tất cả các nút đều ngang hàng và đồng nhất trong hình dạng và chức năng. Các nút giao tiếp với trạm gốc qua Sinh viên: Đỗ Đức Hưng - Lớp CT902 8 Trường ĐHDL Hải Phòng
  9. Báo cáo đồ án tốt nghiệp đa chặng sử dụng các nút ngang hàng làm bộ tiếp sóng. Với phạm vi truyền cố định, các nút gần trạm gốc hơn sẽ đảm bảo vai trò của bộ tiếp sóng đối với một số lượng lớn nguồn. Giả thiết rằng tất cả các nguồn đều dùng cùng một tần số để truyền dữ liệu, vì vậy có thể chia sẻ thời gian. Tuy nhiên cách này chỉ có hiệu quả với điều kiện là có nguồn chia sẻ đơn lẻ, ví dụ như thời gian, tần số Hình 1.2 Cấu trúc phẳng 1.2.2 Cấu trúc phân cấp Trong cấu trúc phân cấp (tiered architecture) như hình 1.3, mạng phân thành các cụm, mỗi cụm có nút chủ cụm (cluster head). Các nút trong cụm thu thập dữ liệu, rồi gửi đơn chặng hay đa chặng tới nút chủ cụm (tùy theo kích thước của cụm). Hình 1.3 Cấu trúc phân cấp Trong cấu trúc này các nút tạo thành một hệ thống cấp bậc mà ở đó mỗi nút ở một mức xác định thực hiện các nhiệm vụ đã định sẵn. Trong cấu trúc phân cấp thì chức năng cảm nhận, tính toán và phân phối dữ liệu không đồng đều giữa các nút. Những chức năng này có thể phân theo cấp, cấp thấp nhất thực hiện tất cả nhiệm vụ cảm nhận, cấp giữa thực hiện tính toán, và cấp trên cùng thực hiện phân phối dữ liệu (hình 1.4) Sinh viên: Đỗ Đức Hưng - Lớp CT902 9 Trường ĐHDL Hải Phòng
  10. Báo cáo đồ án tốt nghiệp Hình 1.4 Cấu trúc mạng phân cấp chức năng theo lớp Các nhiệm vụ xác định có thể được chia không đồng đều giữa các lớp, ví dụ mỗi lớp có thể thực hiện một nhiệm vụ xác định trong tính toán. Trong trường hợp này, các nút ở cấp thấp nhất đóng vai trò một bộ lọc thông dải đơn giản để tách nhiễu ra khỏi dữ liệu, trong khi đó các nút ở cấp cao hơn ngừng việc lọc dữ liệu này, và thực hiện các nhiệm vụ khác như tính toán, phân phối dữ liệu. Mạng cảm biến xây dựng theo cấu trúc phân cấp hoạt động hiệu quả hơn cấu trúc phẳng, do các lý do sau: - Cấu trúc phân cấp có thể giảm chi phí chi mạng cảm biến bằng việc định vị các tài nguyên ở vị trí mà chúng hoạt động hiệu quả nhất. Rõ ràng là nếu triển khai các phần cứng thống nhất, mỗi nút chỉ cần một lượng tài nguyên tối thiểu để thực hiện tất cả các nhiệm vụ. Vì số lượng các nút cần thiết phụ thuộc vào vùng phủ sóng xác định, chi phí của toàn mạng vì thế sẽ không cao. Thay vào đó, nếu một số lượng lớn các nút có chi phí thấp được chỉ định làm nhiệm vụ cảm nhận, một số lượng nhỏ hơn các nút có chi phí cao hơn được chỉ định để phân tích dữ liệu, định vị và đồng bộ thời gian, chi phí cho toàn mạng sẽ giảm đi. - Mạng cấu trúc phân cấp sẽ có tuổi thọ cao hơn mạng phẳng. Khi cần phải tính toán nhiều thì một bộ xử lý nhanh sẽ hiệu quả hơn, phụ thuộc vào thời gian yêu cầu thực hiện tính toán. Tuy nhiên, với các nhiệm vụ cảm nhận cần hoạt động trong khoảng thời gian dài, các nút tiêu thụ ít năng lượng phù hợp với yêu cầu xử lý tối thiểu sẽ hoạt động hiệu quả hơn. Do vậy với cấu trúc phân cấp mà các chức năng mạng phân chia giữa các phần cứng đã được thiết kế riêng cho từng chức năng sẽ làm tăng tuổi thọ của mạng. Sinh viên: Đỗ Đức Hưng - Lớp CT902 10 Trường ĐHDL Hải Phòng
  11. Báo cáo đồ án tốt nghiệp 1.3. Các đặc trƣng của mạng cảm biến không dây 1.3.1 Năng lƣợng tiêu thụ Các ứng dụng trong mạng cảm biến không dây thường đòi hỏi các thành phần có công suất tiêu thụ thấp hơn rất nhiều so với các công nghệ không dây hiện tại (như Bluetooth). Ví dụ như các cảm biến dùng trong công nghiệp và y tế được cung cấp năng lượng từ những cục pin nhỏ, có thể sống được vài tháng đến vài năm. Với các ứng dụng theo dõi môi trường, khi mà số lượng lớn cảm biến được rải trên diện tích rất rộng thì việc thường xuyên phải thay pin để cung cấp nguồn năng lượng là điều không khả thi. Chính vì thế trong mạng cảm biến không dây, ngoài việc quản lý năng lượng để sử dụng một cách hiệu quả nhất cần kết hợp các thuật toán định tuyến tối ưu. 1.3.2 Chi phí Khi thiết kế một ứng dụng không dây thì giá thành cũng là một yếu tố chính cần được quan tâm. Để có thể đạt được mục tiêu này thì khi thiết kế cấu hình mạng và giao thức truyền thông cần tránh sử dụng các thành phần đắt tiền và tối thiểu hóa độ phức tạp của giao thức truyền thông. Trong mạng cảm biến, số lượng các nút mạng sử dụng là khá lớn và khi chi phí để sản xuất từng nút con được giảm đi thì giá thành của toàn bộ hệ thống giảm đi đáng kể. Hiện nay trong các ứng dụng cơ bản các nút mạng có giá khoảng 5-10USD. Ngoài các yếu tố trên thì một phần khá lớn tác động tới giá thành đó là chi phí quản trị và bảo trì hệ thống. Mạng cảm biến không dây đã làm tốt hai chức năng cơ bản đó là tự cấu hình và tự bảo trì. Tự cấu hình có nghĩa là tự động dò tìm vị trí các nút lân cận và tổ chức thành một cấu trúc xác định. Tự bảo trì có nghĩa là tự động phát hiện và sửa lỗi nếu phát sinh trong hệ thống (ở các nút mạng hoặc các liên kết giữa các nút) mà không cần sự tác động của con người. Với các tính năng ưu việt này thì mạng cảm biến không dây ngày càng tỏ rõ những ưu việt của mình. 1.3.3 Loại hình mạng Với một số ứng dụng đơn giản trong phạm vi hẹp thì mạng hình sao (star network) có thể đáp ứng được các yêu cầu truyền nhận và xử lý dữ liệu. Trong mạng hình sao, 1 nút sẽ đóng vai trò nút chủ các nút còn lại là nút con kết nối tới nút chủ. Tuy nhiên khi mạng được mở rộng thì cấu trúc hình sao đơn thuần sẽ không đáp ứng Sinh viên: Đỗ Đức Hưng - Lớp CT902 11 Trường ĐHDL Hải Phòng
  12. Báo cáo đồ án tốt nghiệp được, mạng sẽ phải có cấu hình đa chặng (multi-hop). Cấu hình này sẽ đòi hỏi nhiều tài nguyên bộ nhớ và xử lý tính toán hơn do mật độ của các nút mạng tăng và diện tích của mạng được phủ trên một phạm vi lớn. 1.3.4 Tính bảo mật Trong các ứng dụng của mạng cảm biến không dây thì tính bảo mật rất quan trọng, đặc biệt là các ứng dụng trong quân sự. Không giống như các mạng có dây rất khó có thể lấy được thông tin khi truyền đi giữa 2 đối tượng, khi truyền tín hiệu không dây được truyền đi trong không gian và có thể được thu lại bởi bất kỳ ai. Những mối hiểm họa không chỉ là việc đánh cắp thông tin mà còn ở chỗ những thông tin đó có thể bị chỉnh sửa và phát lại để phía thu nhận được những thông tin không chính xác. Như vậy bảo mật trong mạng cảm biến không dây cần đảm bảo các yếu tố: dữ liệu được mã hóa, có mã xác thực và nhận dạng giữa người gửi và người nhận. Việc này sẽ được thực hiện kết hợp giữa cả phần mềm và phần cứng bằng việc mã hóa các tập tin, điều chỉnh các bít thông tin, thêm các bít xác thực Các chức năng này sẽ làm tiêu tốn thêm tài nguyên của hệ thống về mặt năng lượng và băng thông tuy nhiên bảo mật là một yếu tố bắt buộc trong truyền tin. Do vậy cần đạt được sự cân bằng giữa 2 yếu tố này để đảm bảo cho hệ thống tối ưu nhất. 1.3.5 Độ trễ Các ứng dụng thông thường của mạng cảm biến không có yêu cầu cao về thời gian thực khi truyền mà chủ yếu chú trọng vào chất lượng nguồn tin (trừ một số trường hợp đặc biệt như hệ thống báo cháy). Tuy nhiên trong một mạng lưới khá lớn, các thông tin của các nút con được tập hợp ở một nút chủ để xử lý và đưa về trạm trung tâm thì yếu tố đồng bộ hóa là rất quan trọng. 1.3.6 Tính di động Nhìn chung các ứng dụng trong mạng cảm biến không dây không đòi hỏi tính di động nhiều vì khi triển khai các nút mạng thường ở các vị trí cố định. Các phương thức định tuyến trong mạng cảm biến không dây cũng đơn giản hơn so với các mạng ad-hoc khác (như MANET). Sinh viên: Đỗ Đức Hưng - Lớp CT902 12 Trường ĐHDL Hải Phòng
  13. Báo cáo đồ án tốt nghiệp 1.4 Những khó khăn trong việc phát triển mạng không dây Tuy rằng mạng cảm biến không dây có rất nhiều ưu điểm và ứng dụng hữu ích, nhưng khi triển khai trên thực tế sẽ gặp phải một số hạn chế và khó khăn về mặt kỹ thuật. Khi nắm rõ được những khó khăn này chúng ta sẽ có điều kiện để cải tạo nhằm tối ưu hơn nữa. 1.4.1 Giới hạn năng lƣợng Thông thường, các thiết bị trong mạng cảm biến không dây thường sử dụng các nguồn năng lượng có sẵn (pin). Khi số lượng nút mạng là lớn, yêu cầu tính toán là nhiều, khoảng cách truyền lớn thì sự tiêu thụ năng lượng là rất lớn. Chính vì vậy cần tìm các giải pháp để có thể tối ưu việc xử lý & truyền dữ liệu với một năng lượng ban đầu của các nút nhằm kéo dài thời gian sống cho mạng. 1.4.2 Giới hạn về giải thông Hiện nay tốc độ truyền thông vô tuyến bị giới hạn trong tốc độ khoảng 10-100 Kbits/s. Sự giới hạn về dải thông này ảnh hưởng trực tiếp đến việc truyền thông tin giữa các nút. 1.4.3 Giới hạn về phần cứng Yêu cầu của mạng cảm biến không dây là kích thước của các nút phải nhỏ vì có một số ứng dụng đòi hỏi phải triển khai một số lượng lớn các nút trên một phạm vi hẹp. Điều này đã hạn chế về năng lực tính toán cũng như không gian lưu trữ trên mỗi nút. 1.4.4 Ảnh hƣởng của nhiễu bên ngoài Do trong mạng cảm biến không dây sử dụng đường truyền vô tuyến nên bị ảnh hưởng bởi những can nhiễu bên ngoài, có thể bị mất mát hoặc sai lệch thông tin khi truyền từ nút về trạm gốc. Sinh viên: Đỗ Đức Hưng - Lớp CT902 13 Trường ĐHDL Hải Phòng
  14. Báo cáo đồ án tốt nghiệp CHƢƠNG 2: ĐỊNH TUYẾN TRONG MẠNG CẢM BIẾN KHÔNG DÂY 2.1 Các vấn đề cần lƣu ý đối với giao thức định tuyến 2.1.1 Đặc tính thay đổi thời gian và trật tự sắp xếp của mạng Các nút cảm biến hoạt động với sự giới hạn về khả năng tính toán, lưu trữ và truyền dẫn, dưới ràng buộc về năng lượng khắt khe. Tùy thuộc vào ứng dụng, mật độ các nút cảm biến trong mạng có thể từ thưa thớt đến rất dày. Hơn nữa trong nhiều ứng dụng số lượng các nút cảm biến có thể lên đến hàng trăm, thậm chí hàng ngàn nút được triển khai tùy ý bao phủ một vùng rộng lớn. Trong mạng này, đặc tính của các cảm biến là có tính thích nghi động và cao, các yêu cầu tự tổ chức và bảo toàn năng lượng buộc các nút cảm biến phải điều chỉnh liên tục để thích ứng hoạt động hiện tại. 2.1.2. Ràng buộc về tài nguyên Các nút cảm biến được thiết kế với độ phức tạp nhỏ nhất cho triển khai trong phạm vi lớn để giảm chi phí toàn mạng. Năng lượng là mối quan tâm chính trong mạng cảm biến không dây, làm thế nào để đạt được thời gian sống kéo dài trong khi các nút hoạt động với sự giới hạn về năng lượng dự trữ. Việc truyền gói đa chặng (multihop) chính là nguồn tiêu thụ năng lượng chính trong mạng. Việc giảm năng lượng tiêu thụ có thể đạt được bằng cách điều khiển tự động chu kỳ năng lượng của mạng cảm biến. Tuy nhiên vấn đề quản lý năng lượng đã trở thành một thách thức chiến lược trong nhiều ứng dụng quan trọng. 2.1.3 Mô hình dữ liệu trong mạng cảm biến Mô hình dữ liệu mô tả luồng thông tin giữa các nút cảm biến và các trạm gốc. Mô hình này phụ thuộc nhiều vào bản chất của ứng dụng, các dữ liệu được yêu cầu và sử dụng. Có một vài mô hình dữ liệu được đề xuất nhằm tập trung vào yêu cầu tương tác và nhu cầu tập hợp dữ liệu của các ứng dụng khác nhau. Một loại ứng dụng của mạng cảm biến là mô hình thu thập dữ liệu dựa trên việc lấy mẫu theo chu kỳ hay sự xảy ra của sự kiện trong môi trường quan sát. Trong các ứng dụng khác dữ liệu có thể được lấy và lưu trữ hoặc có thể được xử lý, tập hợp tại một nút trước khi chuyển tiếp dữ liệu đến trạm gốc. Một loại thứ 3 đó là mô hình dữ liệu tương tác hai chiều giữa các nút cảm biến và trạm gốc. Sinh viên: Đỗ Đức Hưng - Lớp CT902 14 Trường ĐHDL Hải Phòng
  15. Báo cáo đồ án tốt nghiệp 2.1.4. Cách truyền dữ liệu Các truy vấn và dữ liệu được truyền giữa các trạm gốc và các vị trí quan sát hiện tượng là một khía cạnh quan trọng trong mạng cảm biến không dây. Một phương pháp cơ bản để thực hiện việc này là mỗi nút cảm biến có thể truyền dữ liệu trực tiếp đến trạm gốc. Tuy nhiên phương pháp dựa trên kỹ thuật đơn chặng có chi phí rất đắt và các nút mà xa trạm gốc thì sẽ nhanh chóng bị tiêu hao năng lượng và do đó làm giảm thời gian sống của mạng. Nhằm giảm thiểu lỗi của phương pháp này thì dữ liệu trao đổi giữa các nút cảm biến và trạm gốc có thể được thực hiện bằng việc sử dụng truyền gói đa chặng qua phạm vi truyền ngắn. Phương pháp này tiết kiệm năng lượng đáng kể và cũng giảm đáng kể sự giao thoa truyền dẫn giữa các nút khi cạnh tranh nhau để truy cập kênh, đặc biệt là trong mạng cảm biến không dây mật độ cao. Để đáp ứng các truy vấn từ các trạm gốc hoặc các sự kiện đặc biệt xảy ra tại môi trường thì dữ liệu thu thập được sẽ được truyền đến các trạm gốc thông qua nhiều đường dẫn đa chặng. Trong định tuyến đa chặng của mạng cảm biến không dây, các nút trung gian đóng vai trò chuyển tiếp dữ liệu giữa nguồn và đích. Việc xác định xem tập hợp các nút nào tạo thành đường dẫn chuyển tiếp dữ liệu giữa nguồn và đích là một nhiệm vụ quan trọng trong thuật toán định tuyến. Nói chung việc định tuyến trong mạng kích thước lớn vốn đã là một vấn đề khó khăn, các thuật toán phải nhằm vào nhiều yêu cầu thiết kế thách thức bao gồm sự chính xác, ổn định, tối ưu hóa và chú ý đến sự thay đổi của các thông số. Với đặc tính bên trong của mạng cảm biến bao gồm sự ràng buộc về dải thông và năng lượng đã tạo thêm thách thức cho các giao thức định tuyến là phải nhằm vào việc thỏa mãn yêu cầu về lưu lượng trong khi vẫn mở rộng được thời gian sống của mạng. 2.2 Các giao thức định tuyến trong mạng cảm biến không dây Có nhiều cách phân loại các giao thức định tuyến trong WSN như: phân loại theo cấu trúc, phân loại theo hoạt động, phân loại theo cách thức mà nguồn tìm tới đích. Sinh viên: Đỗ Đức Hưng - Lớp CT902 15 Trường ĐHDL Hải Phòng
  16. Báo cáo đồ án tốt nghiệp 2.2.1 Các giao thức xét theo cấu trúc mạng 2.2.1.1 Giao thức định tuyến ngang hàng Giao thức định tuyến ngang hàng (Flat Routing) là loại đầu tiên kể đến khi xét các loại giao thức định tuyến. Trong mạng ngang hàng mỗi nút cảm biến có một vai trò giống nhau và các nút cảm biến kết hợp với nhau để thực hiện nhiệm vụ của mạng. Các giao thức: SPIN và directed diffusion là các giao thức dựa trên định tuyến tập trung dữ liệu và tiết kiệm năng lượng thông qua việc tích hợp dữ liệu và loại bỏ sự dư thừa dữ liệu. Giao thức SPIN SPIN (Sensor Protocol for Information via Negotiation) dựa trên ý tưởng là đặt tên dữ liệu sử dụng ký hiệu mô tả ở mức độ cao hay còn gọi là thông tin về dữ liệu (meta-data). Trước khi truyền, thông tin về dữ liệu được trao đổi giữa các nút qua một cơ chế thông báo dữ liệu, đó chính là đặc điểm chính của SPIN. Mỗi một nút nhận dữ liệu mới, thông báo tới các nút lân cận của nó và các nút lân cận quan tâm đến dữ liệu này, ví dụ như các nút mà không có dữ liệu, lấy được dữ liệu nhờ gửi bản tin yêu cầu. Sự dàn xếp các thông tin về dữ liệu của SPIN giải quyết được các vấn đề của flooding như là thông tin dư thừa, chồng chéo các vùng cảm nhận, vì vậy đạt được hiệu quả về mặt năng lượng. Có 3 bản tin được xác định trong SPIN dùng để trao đổi dữ liệu giữa các nút, đó là bản tin ADV cho phép các nút thông báo một meta-data cụ thể, bản tin REQ để yêu cầu các dữ liệu đặc biệt và bản tin DATA để mang thông tin thực. Hình 2.1 tổng kết lại các quá trình của SPIN. Nút A bắt đầu quảng bá dữ liệu tới nút B (a). Nút B trả lời bằng cách gửi yêu cầu tới nút A (b). Nút B nhận dữ liệu yêu cầu từ nút A (c). Nút B phát bản tin quảng bá đến các nút lân cận (d), sau đó các nút này gửi yêu cầu lại cho B (e-f) Sinh viên: Đỗ Đức Hưng - Lớp CT902 16 Trường ĐHDL Hải Phòng
  17. Báo cáo đồ án tốt nghiệp Hình 2.1 Cơ chế của SPIN Giao thức truyền tin trực tiếp Giao thức truyền tin trực tiếp (Directed Diffusion) sử dụng lược đồ tập trung dữ liệu và các nút đều biết về ứng dụng. Tất cả các dữ liệu phát ra bởi nút cảm biến được đặt tên sử dụng các cặp giá trị thuộc tính và sử dụng quá trình xử lí trong mạng như tích hợp dữ liệu (aggregation). Giao thức này loại bỏ sự dư thừa dữ liệu nhờ quá trình xử lí nội mạng, và tối thiểu số lần truyền nên tiết kiệm được năng lượng, kéo dài thời gian sống của mạng. Hình 2.2 mô tả các quá trình diễn ra trong mạng khi dùng giao thức Directed Diffusion. Ban đầu trạm gốc tạo ra một yêu cầu được xác định dùng các cặp giá trị thuộc tính như là tên vật thể, vị trí địa lý, khoảng thời gian Các thông tin này được phát quảng bá thông qua các nút trung gian đến nguồn. Mỗi một nút nhận được thông tin đó sẽ giữ lại để so sánh dữ liệu nhận được với giá trị trong thông tin đó. Các thông tin này cũng bao gồm các trường gradient. Gradient là đường trả lời đến nút lân cận từ nơi mà nhận được thông tin yêu cầu. Nó được mô tả bởi tốc độ dữ liệu, khoảng thời gian và thời gian mãn hạn nhận được từ các thông tin yêu cầu. Vì thế nhờ việc sử dụng các thông tin yêu cầu và gradient thiết lập được các đường truyền giữa trạm gốc và các nguồn. Trạm gốc gửi lại các bản tin gốc qua những đường đã được chọn với khoảng thời gian giữa hai sự kiện ngắn hơn vì vậy tăng cường nút nguồn trên đường đó để gửi dữ liệu đều đặn hơn. Sinh viên: Đỗ Đức Hưng - Lớp CT902 17 Trường ĐHDL Hải Phòng
  18. Báo cáo đồ án tốt nghiệp Hình 2.2 Các pha trong Directed Diffusion Giao thức GBR Giao thức GBR (Gradient based Routing) là giao thức chỉnh sửa của Directed Diffusion. Ý tưởng của giao thức này là lưu số chặng khi phân tán qua mạng. Do đó, mỗi nút có thể tìm ra số chặng tối thiểu tới Trạm gốc (khoảng cách tới Trạm gốc). Sự khác nhau giữa khoảng cách tới Trạm gốc của nút và của nút lân cận được xem xét trong gradient trên kết nối đó. Một gói được chuyển tiếp trên kết nối đó với gradient lớn nhất. Trong giao thức này có thể dùng một số kĩ thuật như tích hợp dữ liệu và phân tán lưu lượng (traffic spreading) để chia đều thông lượng trên toàn mạng. 2.2.1.2 Các giao thức phân cấp Trong kiến trúc phân cấp, các nút có vai trò khác nhau: các nút có năng lượng cao hơn được sử dụng để xử lý và gửi thông tin trong khi các nút có năng lượng thấp được sử dụng để cảm nhận, thu thập dữ liệu. Điều này có nghĩa là tạo ra các cluster và chỉ định các nhiệm vụ đặc biệt cho các nút chủ cụm (nút mà có nhiều năng lượng). Mục đích chính của định tuyến phân cấp là để duy trì hiệu quả việc tiêu thụ năng lượng của các nút cảm biến bằng việc đặt chúng trong giao tiếp đa chặng trong một cụm cụ thể và bằng việc thực hiện tập trung và hợp nhất dữ liệu để giảm số bản tin được truyền đến trạm gốc. Sự hình thành các cụm chủ yếu dựa trên năng lượng dự trữ của nút và vùng lân cận của nút so với các nút chủ của cụm. Sinh viên: Đỗ Đức Hưng - Lớp CT902 18 Trường ĐHDL Hải Phòng
  19. Báo cáo đồ án tốt nghiệp Phần này sẽ trình bày một số giao thức tiêu biểu trong loại giao thức định tuyến phân cấp. 2.2.1.2.1 Giao thức LEACH LEACH (Low-energy adaptive clustering hierarchy) là một trong số những cách tiếp cận định tuyến phân cấp đầu tiên cho mạng cảm biến .Ý tưởng là để hình thành các cụm nút cảm biến dựa vào cường độ tín hiệu nhận và dùng các nút chủ của cụm như là các router đến các trạm gốc. Việc này sẽ tiết kiệm năng lượng vì quá trình truyền chỉ có thể thực hiện bằng các nút chủ của cụm thay cho việc sử dụng tất cả các nút cảm biến. Số lượng các nút chủ tối ưu của cụm là vào khoảng 5% tổng số lượng các nút. Trong giao thức LEACH, nhờ việc lựa chọn ngẫu nhiên một số nút làm nút chủ cụm và sau đó quay vòng vai trò nút chủ cụm cho các nút khác trong cụm, do đó việc tiêu hao năng lượng khi liên lạc với trạm gốc được trải đều cho tất cả các nút cảm biến trong mạng. Nhờ đó góp phần vào việc kéo dài thời gian sống cho mạng. Quá trình hoạt động của LEACH được chia thành hai pha là pha thiết lập và pha ổn định. Thời gian của pha ổn định kéo dài hơn so với thời gian của pha thiết lập để giảm thiểu phần điều khiển. Pha thiết lập Các cụm được hình thành và các nút chủ cụm được lựa chọn. Các nút chủ được lựa chọn như sau:Mỗi nút cảm biến lựa chọn một số ngẫu nhiên giữa 0 và 1. Nếu số này nhỏ hơn ngưỡng T(n) thì nút cảm biến là nút chủ. T(n) được tính như sau: p T(n) 1 p *(r mod1/ p) nếu n G T(n) 0 còn lại Trong đó p: tỉ lệ phần trăm nút chủ r: chu kì hiện tại G: tập hợp các nút không được lựa chọn làm nút chủ trong 1/P chu kì cuối. Sinh viên: Đỗ Đức Hưng - Lớp CT902 19 Trường ĐHDL Hải Phòng
  20. Báo cáo đồ án tốt nghiệp Mỗi nút chủ cụm được lựa chọn sẽ truyền thông tin quảng bá cho các nút còn lại trong mạng bản tin thông báo rằng chúng là nút chủ cụm mới. Các nút còn lại không là nút chủ, khi nhận được bản tin quảng bá, chúng sẽ quyết định chúng thuộc về cụm của nút chủ nào. Quyết định này dựa trên độ mạnh của tín hiệu của bản tin quảng bá các nút chủ cụm phát đi mà chúng nhận được. Các nút không phải chủ cụm này sẽ thông báo cho nút chủ cụm rằng chúng sẽ thuộc về cụm nào. Sau khi các nút chủ cụm nhận được hết các thông báo của các nút thuộc về cụm của chúng, căn cứ vào số nút trong cụm, nút chủ cụm sẽ chỉ định thời gian mà các nút trong cụm gửi dữ liệu đến cho nó dựa trên TDMA. Pha ổn định Các nút bắt đầu thu thập dữ liệu và gửi dữ liệu đến các nút chủ cụm. Các nút chủ cụm sẽ tích hợp dữ liệu của các nút trong cụm gửi đến trước khi gửi dữ liệu đến Trạm gốc. Sau một khoảng thời gian trong pha ổn định, mạng sẽ trở lại pha thiết lập và vào bước lựa chọn nút chủ cụm mới. Các nút có thể ngừng hoạt động ngẫu nhiên và các cụm động sẽ làm tăng thời gian sống của mạng. Tuy nhiên LEACH dùng định tuyến đơn điểm, các nút có thể truyền trực tiếp đến các nút chủ và trạm gốc. Vì thế nó sẽ không thích hợp với mạng mà triển khai trên diện rộng. Hơn nữa, ý tưởng về các cụm động đòi hỏi số lượng mào đầu lớn, ví dụ như các sự thay đổi nút chủ, quảng bá 2.2.1.2.2 Giao thức PEGASIS PEGASIS (Power-efficient Gathering in Sensor Information Systems) là giao thức cải tiến lên từ LEACH. Thay vì việc hình thành các cụm, PEGASIS tạo thành chuỗi từ các nút cảm biến để mỗi nút truyền và nhận từ nút lân cận và chỉ có một nút được chọn từ chuỗi đó để truyền đến trạm gốc (trạm gốc). Dữ liệu tập hợp được truyền từ nút này sang nút kia, tập trung lại và dần dần truyền đến trạm gốc. Ví dụ như hình 2.3. Nút c0 truyền dữ liệu của nó đến nút c1. Nút c1 tập hợp dữ liệu của nút c0 và dữ liệu của nó, sau đó truyền đến nút chính. Sau khi nút c2 chuyển thẻ bài cho nút c4, nút c4 truyền dữ liệu của nó cho nút c3. Nút c3 tập hợp dữ liệu của c4 với dữ liệu của chính nó và sau đó truyền đến nút chính. Nút c2 đợi để nhận dữ liệu từ cả hai nút lân cận và sau đó tập hợp dữ liệu của nó với dữ liệu của các nút lân cận. Cuối cùng, c2 truyền một bản tin đến trạm gốc. Sinh viên: Đỗ Đức Hưng - Lớp CT902 20 Trường ĐHDL Hải Phòng
  21. Báo cáo đồ án tốt nghiệp Hình 2.3 Chuỗi trong PEGASIS Sự khác biệt so với LEACH là ở chỗ dùng định tuyến đa chặng bằng việc hình thành chuỗi và và chọn mỗi một nút để truyền đến trạm gốc thay cho dùng nhiều nút. Dùng PEGASIS sẽ giải quyết được vấn đề về mào đầu gây ra bởi việc hình thành các cụm động trong LEACH và giảm được số lần truyền và nhận bằng việc tập hợp dữ liệu. Tuy nhiên PEGASIS lại có độ trễ đường truyền lớn đối với các nút ở xa trong chuỗi, vì vậy cũng khó áp dụng cho mạng có quy mô lớn, số nút cảm biến lớn. Hơn nữa ở nút chính có thể xảy ra hiện tượng thắt cổ chai. 2.2.1.2.3 Giao thức hiệu quả năng lƣơng cảm nhận mức ngƣỡng Giao thức hiệu quả năng lương cảm nhận mức ngưỡng TEEN (Threshold- sensitive Energy Efficient sensor Network protocol) được đưa ra cho các ứng dụng phụ thuộc thời gian. Trong giao thức này các nút cảm biến liên tục cảm nhận môi trường, nhưng gửi dữ liệu không thường xuyên. Nút chủ cụm gửi cho các thành viên trong cụm của nó một giá trị ngưỡng cứng (hard threshold)- là giá trị ngưỡng của thuộc tính được cảm nhận và một giá trị ngưỡng mềm-là lượng thay đổi nhỏ về giá trị của thuộc tính làm cho nút chuyển sang chế độ phát dữ liệu. Giá trị ngưỡng cứng là để giảm sự truyền dẫn bằng cách chỉ cho phép nút truyền khi thuộc tính cảm nhận trong một phạm vi thích hợp. Ngưỡng mềm để giảm thêm nữa số lần truyền dẫn khi có sự thay đổi rất ít của thuộc tính cần đo (khí sự thay đổi nhỏ hơn ngưỡng mềm thì không truyền dữ liệu). Giá trị ngưỡng mềm càng nhỏ thì độ chính xác của mạng càng cao, nhưng chí phí năng lượng cũng tăng. Do đó cần phải hài hòa giữa độ chính xác và sự tiêu thụ năng lượng. Khi các nút chủ cụm thay đổi, các giá trị ngưỡng sẽ thay đổi và được broadcast. Hoạt động của TEEN được thể hiện trong hình vẽ 2.4. Sinh viên: Đỗ Đức Hưng - Lớp CT902 21 Trường ĐHDL Hải Phòng
  22. Báo cáo đồ án tốt nghiệp Các thông số Thuộc tính > ngưỡng Thời gian Thời gian thay đổi Nút chủ cụm nhận cluster bản tin Hình 2.4 Time line cho hoạt động của TEEN Nhược điểm chính của giao thức này là nếu các nút không nhận được các giá trị ngưỡng của nút chủ cụm gửi tới thì nút này sẽ không gửi dữ liệu, vì user sẽ không thể nhận dữ liệu toàn mạng. Ngoài ra, nó còn khó phân định khe thời gian khi tất cả các nút đều bật bộ phát và gửi dữ liệu cùng lúc và không phân biệt được nút bị hư hỏng hay nó không cảm nhận được sự thay đổi lớn giá trị thuộc tính. 2.2.1.3 Giao thức định tuyến dựa theo vị trí Trong loại giao thức này, vị trí các nút được sử dụng để định tuyến dữ liệu. Các nút cảm biến được đánh địa chỉ theo vị trí của chúng. Khoảng cách giữa các nút được ước tính dựa theo cường độ tín hiệu thu được. Vị trí của các nút có thể thu được bằng cách trao đổi các bản tin giữa các nút lân cận hoặc lấy trực tiếp thông qua hệ thống định vị toàn cầu. Nếu nút được trang bị một bộ thu GPS công suất nhỏ. Việc dùng thông tin vị trí vào định tuyến góp phần sử dụng hiệu quả năng lượng và tiết kiệm năng lượng cho toàn mạng. 2.2.1.3.1 Giao thức GAF Giao thức GAF ( Geographic Adaptive Fidelity) dựa trên vị trí có hiệu quả về mặt năng lượng được thiết kế chủ yếu cho các mạng ad-hoc di động, nhưng cũng có thể áp dụng cho mạng cảm biến. Trong giao thức này, toàn bộ mạng sẽ được chia thành các khu vực cố định và hình thành lưới ảo. Trong mỗi khu vực, các nút kết hợp với nhau để giữ các vai trò khác nhau. Ví dụ như, các nút sẽ bầu ra một nút ở trạng thái hoạt động trong một khoảng thời gian nhất định và sau đó đi vào chế độ nghỉ. Các nút này chịu trách nhiệm giám sát và báo cáo dữ liệu về Trạm gốc thay cho các nút trong cùng khu vực. Do đó GAF dự trữ năng lượng bằng cách tắt các nút không cần thiết trong mạng mà không ảnh hưởng đến mức độ chính xác của định tuyến. Mỗi nút dùng Sinh viên: Đỗ Đức Hưng - Lớp CT902 22 Trường ĐHDL Hải Phòng
  23. Báo cáo đồ án tốt nghiệp GPS của nó – vị trí xác định để kết hợp với cùng một điểm trên lưới mà được coi là tương đương khi tính đến giá của việc định tuyến gói. Sự tương đương như vậy được tận dụng để giữ các nút định vị trong vùng lưới xác định trong trạng thái nghỉ để tiết kiệm năng lượng. Vì vậy GAF có thể tăng đáng kể thời gian sống của mạng cảm biến khi mà số lượng các nút tăng lên. Một ví dụ cụ thể được đưa ra ở hình 2.5. Trong hình vẽ này, nút 1 có thể truyền đến bất kì nút nào trong số các nút 2, 3 và 4 và các nút 2, 3, 4 có thể truyền tới nút 5. Do đó các nút 2, 3, và 4 là tương đương và 2 trong số 3 nút đó có thể ở trạng thái nghỉ. Hình 2.5 Ví dụ về lƣới ảo trong GAF 2.2.1.3.2 Giao thức GEAR Giao thức GEAR (Geographic and Energy-Aware Routing) là giao thức sử dụng thông tin vị trí trong quá trình truyền bản tin truy vấn tới vùng thích hợp vì trong các truy vấn thường chứa các thuộc tính mang thông tin vị trí. Giao thức này dùng sự nhận biết về năng lượng và và thông tin vị trí của các nút lân cận để định tuyến bản tin truy vấn về vùng đích. Việc định tuyến thông tin theo vùng địa lý rất có ích trong các hệ thống xác định vị trí, và đặc biệt là trong mạng cảm biến. Ý tưởng chính của giao thức là hạn chế số lượng các yêu cầu ở Directed Diffusion bằng cách quan tâm đến một vùng xác định hơn là gửi các yêu cầu tới toàn mạng. Nhờ đó, mà GEAR cải tiến hơn Directed Diffusion ở điểm này và vì thế dự trữ được nhiều năng lượng hơn. 2.2.2 Các giao thức định tuyến xét theo hoạt động Phần này sẽ trình bày phân loại các giao thức theo hoạt động của giao thức. Sinh viên: Đỗ Đức Hưng - Lớp CT902 23 Trường ĐHDL Hải Phòng
  24. Báo cáo đồ án tốt nghiệp 2.2.2.1 Các giao thức định tuyến đa đƣờng Các giao thức loại này sử dụng nhiều đường để truyền dữ liệu để tăng cường hiệu năng của mạng: như khả năng chịu lỗi (fault tolerance), sự cân bằng trong việc tiêu thụ năng lượng giữa các đường cũng như toàn mạng, hiệu quả năng lượng và độ tin cậy. Khả năng chịu lỗi của một giao thức là khả năng có thể dùng một đường thay thế khi đường sơ cấp giữa nguồn và trạm gốc bị lỗi. Điều này có thể có được bằng cách duy trì nhiều đường từ nguồn tới Trạm gốc nhưng làm tăng sự tiêu thụ năng lượng và thông lượng trong mạng. Các đường thay thế này được duy trì bằng cách gửi các bản tin định kỳ. Do đó độ tin cậy của mạng có thể tăng nhưng cũng tăng thêm chi phí năng lượng khi duy trì nhiều đường. Khi duy trì nhiều đường, nếu xảy ra lỗi ở đường sơ cấp, việc có sẵn các đường thay thế sẽ làm giảm chi phí và độ trễ khi thiết lập lại đường khác. Các giao thức tiêu biểu cho loại này gồm Maximum Lifetime Routing, Multipath Directed Diffusion . 2.2.2.2 Giao thức định tuyến thời gian sống cực đại Giao thức định tuyến thời gian sống cực đại (Maximum Lifetime Routing) là giao thức định tuyến dữ liệu qua một đường mà các nút trên đường đó có năng lượng còn lại lớn. Đường sẽ được chuyển bất cứ khi nào có một đường khác tốt hơn được tìm ra. Đường sơ cấp được sử dụng cho đến khi năng lượng của nó giảm dưới năng lượng của một đường dự trữ (backup). Bằng cách này các nút trên đường sơ cấp sẽ không bị giảm năng lượng nhanh chóng so với khi sử dụng đường này liên tục. Do đó thời gian sống của mạng sẽ tăng. 2.2.2.3 Multipath Directed Diffusion Giao thức này dựa trên Directed Diffusion nhưng thay vì tăng cường cho một đường tối ưu, nó thiết lập và tăng cường cho vài đường. Giao thức đa đường này có ưu điểm là khắc phục được lỗi hư hỏng nút cảm biến trên đường sơ cấp, do nó chọn luôn đường còn lại. Tuy nhiên, phải tốn năng lượng để duy trì nhiều đường. 2.2.2.4 Các giao thức dựa trên truy vấn Trong loại giao thức này, các nút đích truyền một bản tin truy vấn dữ liệu từ một nút qua mạng và các nút có dữ liệu phù hợp với truy vấn sẽ gửi dữ liệu trở lại nút Sinh viên: Đỗ Đức Hưng - Lớp CT902 24 Trường ĐHDL Hải Phòng
  25. Báo cáo đồ án tốt nghiệp đích. Thường các truy vấn này được mô tả bằng ngôn ngữ tự nhiên hoặc ngôn ngữ bậc cao. Các giao thức tiêu biểu cho loại này như Directed Diffusion, Rumor routing protocol. 2.2.2.5 Giao thức Directed Diffusion Như mô tả ở phần trên, Directed Diffusion là một giao thức thuộc loại giao thức định tuyến này. Trong giao thức này, Trạm gốc gửi bản tin interest tới các nút cảm biến trong mạng. Khi interest được truyền qua mạng, gradient từ nguồn tới trạm gốc được thiết lập. Khi nguồn có dữ liệu, chúng sẽ gửi dữ liệu theo các đường đã thiết lập đến Trạm gốc. Để giảm năng lượng tiêu thụ, tích hợp dữ liệu được thực hiện. 2.2.2.6 Giao thức định tuyến Rumor Giao thức định tuyến Rumor kết hợp flooding truy vấn và flooding sự kiện. Giao thức này sử dụng một tập các agent để thiết lập đường trực tiếp về phía sự kiện khi chúng chúng xảy ra. Khi một nút dò thấy sự kiện, nó phát ra một agent theo một đường ngẫu nhiên. Mỗi nút duy trì một danh sách các nút lân cận và một bảng các sự kiện được cập nhật khi sự kiện mới xảy ra. Các nút có agent đi qua sẽ hình thành gradient về phía sự kiện. Khi agent đến từ những đường ngắn hơn hay hiệu quả hơn, chúng tối ưu các đường trong bảng định tuyến tương ứng. Khi Trạm gốc cần một sự kiện, chúng sẽ gửi một truy vấn vào mạng theo một hướng ngẫu nhiên. Truy vấn này có thể theo đường ngẫu nhiên vào vùng có sự kiện hoặc gặp nút trên đường mà agent đã thiết lập. Khi đó sẽ hình thành các đường để gửi dữ liệu (hoặc theo một đường riêng hoặc qua đường mà agent đã thiết lập). 2.2.2.7 Giao thức dựa trên thƣơng lƣợng Giao thức dựa trên thương lượng sử dụng bản mô tả dữ liệu để loại bỏ việc truyền dữ liệu dư thừa qua việc hỏi đáp.Việc quyết định truyền gói cũng dựa vào tài nguyên có trong các nút. Giao thức SPIN là giao thức tiêu biểu cho loại giao thức này. Flooding và Gossiping là hai cơ chế cổ điển để truyền dữ liệu trong mạng cảm biến mà không cần bất cứ một giải thuật định tuyến hoặc sự duy trì cấu hình nào. Trong Flooding, mỗi nút nhận được gói dữ liệu, rồi quảng bá nó tới tất cả các nút lân cận và quá trình này cứ tiếp diễn cho đến khi gói dữ liệu đến được đích hoặc gói đã đi qua số lượng lớn nhất các chặng. Gossiping có cải tiến hơn Flooding một chút, trong đó các Sinh viên: Đỗ Đức Hưng - Lớp CT902 25 Trường ĐHDL Hải Phòng
  26. Báo cáo đồ án tốt nghiệp nút nhận dữ liệu gửi gói đến một nút lân cận ngẫu nhiên, sau đó lại chọn ngẫu nhiên một nút lân cận tiếp theo để truyền gói, và cứ tiếp tục như vậy. Mặc dù Flooding triển khai tương đối dễ dàng nhưng nó có một số nhược điểm. Đó là khi xảy ra trường hợp các bản tin kép gửi đến cùng một nút; hay hiện tượng chồng chéo khi hai nút cảm nhận cùng một vùng, gửi những gói tương tự nhau đến cùng một nút lân cận. Do vậy Flooding và Gossiping tiêu tốn năng lượng và phải xử lí nhiều. Giao thức SPIN được thiết kế để phân phối dữ liệu từ một nút tới tất các các nút khác trong toàn mạng để loại bỏ dữ liệu dư thừa. 2.2.2.8 Giao thức dựa trên chất lƣợng dịch vụ Trong các giao thức này, mạng phải cân bằng giữa tiêu thụ năng lượng và chất lượng dữ liệu. Nhìn chung mạng phải thỏa mãn các thông số nhất định như trễ, năng lượng, băng thông, khi phân phối dữ liệu tới Trạm gốc. 2.2.2.9 Giao thức xử lí kết hợp và không kết hợp Xử lí dữ liệu là một thành phần trong hoạt động của mạng cảm biến không dây. Do đó các kĩ thuật định tuyến sử dụng các kĩ thuật xử lí dữ liệu khác nhau. Nhìn chung các nút cảm biến sẽ kết hợp với nhau trong quá trình xử lí dữ liệu khác nhau khi truyền trong mạng. Hai kĩ thuật được đưa ra trong các mạng cảm biến là định tuyến dựa trên xử lí kết hợp và không kết hợp. Trong định tuyến xử lí dữ liệu không kết hợp, các nút sẽ xử lí dữ liệu thô cục bộ trước khi gửi đi cho các nút khác xử lí thêm. Các nút thực hiện việc xử lí thêm được gọi là các nút tích hợp. Trong định tuyến xử lí dữ liệu, dữ liệu được chuyển tới cho các nút tích hợp sau khi đã xử lí tối ưu. Quá trình xử lí tối ưu bao gồm các nhiệm vụ như là đánh dấu, loại bỏ bản tin sao Để thực hiện định tuyến hiệu quả năng lượng, định tuyến kết hợp thường được lựa chọn. Sinh viên: Đỗ Đức Hưng - Lớp CT902 26 Trường ĐHDL Hải Phòng
  27. Báo cáo đồ án tốt nghiệp CHƢƠNG 3: MÔ PHỎNG MỘT SỐ GIAO THỨC ĐỊNH TUYẾN VÀ ĐÁNH GIÁ KẾT QUẢ Chương trước đã nghiên cứu các giao thức định tuyến về mặt lý thuyết. Mỗi giao thức có những ưu điểm và nhược điểm riêng tác động đến quá trình tiêu thụ năng lượng của các nút và lượng dữ liệu truyền về trạm gốc. Tuy nhiên, trên thực tế trước khi triển khai một mạng bất kỳ người ta thường phải đánh giá tính hiệu quả của các giao thức dựa trên những số liệu cụ thể. Để thực hiện điều này người ta thường dùng các phần mềm mô phỏng để xây dựng các mô hình lý thuyết. Qua đó chúng ta có thể thu được các kết quả trực quan giúp cho việc triển khai trong thực tế được tối ưu hơn và tiết kiệm rất nhiều chi phí. Có khá nhiều phần mềm mô phỏng mạng, tuy nhiên trong đồ án này, phần mềm mô phỏng được chọn là NS-2 (network simulation) bởi đây là một công cụ hỗ trợ rất tốt cho việc mô phỏng các giao thức trong mạng cảm biến không dây. 3.1 Phần mềm mô phỏng mạng NS-2 3.1.1 Giới thiệu về NS2 NS-2 là phần mềm mô phỏng mạng điều khiển sự kiện riêng rẽ hướng đối tượng, được phát triển tại UC Berkely, viết bằng ngôn ngữ C++ và OTcl. Bốn lợi ích lớn nhất của NS-2 phải kể đến đầu tiên là: - Khả năng kiểm tra tính ổn định của các giao thức mạng thường dùng. - Khả năng đánh giá các giao thức mạng mới trước khi đưa vào sử dụng. - Khả năng thực thi những mô hình mạng lớn mà gần như ta không thể thực thi được trong thực tế. - Khả năng có thể mô phỏng nhiều loại mạng khác nhau. NS thực thi các giao thức mạng như Giao thức điều khiển truyền tải (TCP) và Giao thức gói người dùng (UDP); các dịch vụ nguồn lưu lượng như Giao thức truyền tập tin (FTP), Telnet, Web, Tốc độ bit cố định (CBR) và Tốc độ bit thay đổi (VBR); các kỹ thuật quản lý hàng đợi như Vào trước Ra trước (Drop Tail), Dò sớm ngẫu nhiễn (RED) và CBQ; các thuật toán định tuyến như Dijkstra NS cũng thực thi Sinh viên: Đỗ Đức Hưng - Lớp CT902 27 Trường ĐHDL Hải Phòng
  28. Báo cáo đồ án tốt nghiệp multicasting và vài giao thức lớp Điều khiển truy cập đường truyền (MAC) đối với mô phỏng LAN. Hình 3.1: Tổng quan về NS dƣới góc độ ngƣời dùng OTcl Script Kịch bản OTcl Simulation Program Chương trình mô phòng OTcl Bộ biên dịch Tcl mở rộng hướng đối tượng NS Simulation Library Thư viện mô phỏng NS Event Scheduler Objects Các đối tượng bộ lập lịch sự kiện Network Component Objects Các đối tượng thành phần mạng Network Setup Helping Modules Các mô đun trợ giúp thiết lập mạng Plumbling Modules Các mô đun Plumbling Simulation Results Các kết quả mô phỏng Analysis phân tích NAM Network Animator Minh họa mạng NAM Trong hình trên, NS là Bộ biên dịch Tcl mở rộng hướng đối tượng; bao gồm các đối tượng bộ lập lịch sự kiện, các đối tượng thành phần mạng và các module trợ giúp thiết lập mạng. Để sử dụng NS-2, người dùng lập trình bằng ngôn ngữ kịch bản OTcl. Người dùng có thể thêm các mã nguồn Otcl vào NS-2 bằng cách viết các lớp đối tượng mới trong Sinh viên: Đỗ Đức Hưng - Lớp CT902 28 Trường ĐHDL Hải Phòng
  29. Báo cáo đồ án tốt nghiệp OTcl. Những lớp này khi đó sẽ được biên dịch cùng với mã nguồn gốc. Kịch bản OTcl có thể thực hiện những việc sau: Khởi tạo bộ lập lịch sự kiện Thiết lập mô hình mạng dùng các đối tượng thành phần mạng Báo cho nguồn traffic khi nào bắt đầu truyền và ngưng truyền packet trong bộ lập lịch sự kiện Thuật ngữ plumbing được dùng để chỉ việc thiết lập mạng, vì thiết lập một mạng nghĩa là xây dựng các đường dữ liệu giữa các đối tượng mạng bằng cách thiết lập con trỏ “neighbour” cho một đối tượng để chỉ đến địa chỉ của đối tượng tương ứng. mô đun plumbing OTcl trong thực tế thực hiện việc trên rất đơn giản. Plumbing làm nên sức mạnh của NS. Thành phần lớn khác của NS bên cạnh các đối tượng thành phần mạng là bộ lập lịch sự kiện. Bộ lập lịch sự kiện trong NS-2 thực hiện những việc sau: Tổ chức bộ định thời mô phỏng Huỷ các sự kiện trong hàng đợi sự kiện Lời gọi các thành phần mạng trong mô phỏng Phụ thuộc vào mục đích của ứng dụng người dùng sử dụng kịch bản mô phỏng OTcl mà kết quả mô phỏng có thể được lưu trữ như file trace. Định dạng file trace sẽ được tải vào trong các ứng dụng khác để thực hiện phân tích: File nam trace (file.nam) được dùng cho công cụ minh họa mạng NAM File Trace (file.tr) được dùng cho công cụ lần vết và giám sát mô phỏng XGRAPH hay TRACEGRAPH Sinh viên: Đỗ Đức Hưng - Lớp CT902 29 Trường ĐHDL Hải Phòng
  30. Báo cáo đồ án tốt nghiệp Hình 3.2: Luồng các sự kiện cho file Tcl chạy trong NS NAM Visual Simulation Mô phỏng trực quan Tracing and Monitoring Simulation Mô phỏng lần vết và giám sát 3.1.2 C++ và OTcl Hình sau biểu diễn kiến trúc chung của NS. Người dùng có thể tưởng tượng mình đang đứng ở góc trái dưới, thiết kế và chạy các mô phỏng trong Tcl. Tcl dùng các đối tượng mô phỏng trong OTcl. Các đối tượng Bộ lập lịch Sự kiện và hầu hết các đối tượng thành phần mạng thực thi bằng C++ và sẵn có cho OTcl qua một liên kết OTcl. Liên kết OTcl này được thực thi dùng TclCL. Tất cả đã làm nên NS, bộ biên dịch Tcl mở rộng hướng đối tượng và các thư viện mô phỏng mạng. Network Components Scheduler Event TclCL OTcl Tcl C/C++ ns-2 Hình 3.3: Kiến trúc của NS-2 NS sử dụng hai ngôn ngữ lập trình: ngôn ngữ kịch bản và ngôn ngữ lập trình hệ thống (C/C++) NS là tầng biên dịch Tcl để chạy các kịch bản Tcl Bằng cách sử dụng C++/OTcl, bộ mô phỏng mạng phải hoàn toàn là hướng đối tượng Sinh viên: Đỗ Đức Hưng - Lớp CT902 30 Trường ĐHDL Hải Phòng
  31. Báo cáo đồ án tốt nghiệp Hình sau chỉ ra các đối tượng C++ có liên kết OTcl. Khi đó, nếu chúng tạo nên một phân cấp thì các đối tượng OTcl cũng có một phân cấp tương ứng như vậy. Hình 3.4: C++ và OTcl: Sự đối ngẫu TclCL là ngôn ngữ được sử dụng để cung cấp liên kết giữa C++ và OTcl. Các kịch bản Tcl/OTcl được viết để thiết lập và cấu hình topology của mạng. TclCL cung cấp liên kết giữa phân cấp lớp, khởi tạo đối tượng, nối kết biến và gửi lệnh. Hình 3.5: TclCL hoạt động nhƣ liên kết giữa A và B Vậy, tại sao NS lại cần sử dụng đến hai ngôn ngữ? Lý do là vì bộ mô phỏng cần thực hiện hai việc khác nhau. Một mặt là vì các mô phỏng cho các giao thức yêu cầu một ngôn ngữ lập trình hệ thống có thể tính toán một cách hiệu quả các byte, các tiêu đề packet và các thuật toán thực thi đang chạy trên một tập dữ liệu lớn. Với tác vụ này, run-time speed (tốc độ thời gian chạy thực) là quan trọng trong khi turn-around time (thời gian quay vòng) thì ít quan trọng hơn. Turn-around time bao gồm thời gian chạy mô phỏng, thời gian tìm lỗi, thời gian sửa lỗi, thời gian biên dịch lại và thời gian chạy lại. Mặt khác, khi nghiên cứu mạng thì rất cần quan tâm đến các tham số và các cấu hình có thay đổi nhưng không đáng kể, hay quan tâm đến các tình huống (scenarios) Sinh viên: Đỗ Đức Hưng - Lớp CT902 31 Trường ĐHDL Hải Phòng
  32. Báo cáo đồ án tốt nghiệp cần khám phá thật nhanh chóng. Trong tác vụ này thì thời gian lặp lại (iteration time) tức là thời gian hay đổi mô hình và chạy lại là quan trọng hơn. Vì cấu hình chỉ chạy một lần lúc bắt đầu mô phỏng nên run-time trong tác vụ này rõ ràng kém quan trọng hơn. Theo giải thích trên, từng ngôn ngữ sẽ được dùng cho những việc gì? Dùng C++ để: Mô phỏng giao thức chi tiết yêu cầu ngôn ngữ lập trình hệ thống o Thao tác trên byte, xử lý gói, thực thi thuật toán o Tốc độ thời gian thực là quan trọng nhất Thực hiện bất kỳ việc gì mà cần phải xử lý từng packet của một luồng. Thay đổi hành vi của lớp C++ đang tồn tại theo những hướng đã không được lường trước. Và dùng OTcl để: Mô phỏng những thông số hay cấu hình thay đổi o Tham dò nhanh một số tình huống o Thời gian tương tác (thay đổi mô hình hay chạy lại) là quan trọng Cấu hình, thiết lập hay những gì chỉ làm một lần. Thực hiện những cái ta muốn bằng cách thao tác trên các đối tượng C++ đang tồn tại. Ví dụ như các link là những đối tượng OTcl liên kết các mô đun về độ trễ (delay), sắp hàng đợi (queueing) và khả năng mất mát (possibly loss). Còn nếu muốn thực hiện những việc chuyên nghiệp hơn thì cần phải tạo ra đối tượng C++ mới. Hầu hết định tuyến được viết bằng OTcl (dù thuật toán Dijkstra lõi viết bằng C++). Mô phỏng HTTP có từng luồng bắt đầu tại OTcl nhưng việc xử lý từng gói lại được viết bằng C++. Phương pháp này chạy tốt cho đến khi có đến 100 luồng bắt đầu thời gian mô phỏng mỗi giây. Nói chung, nếu phải triệu gọi Tcl nhiều lần mỗi giây thì có lẽ nên chuyển sang C++. Sinh viên: Đỗ Đức Hưng - Lớp CT902 32 Trường ĐHDL Hải Phòng
  33. Báo cáo đồ án tốt nghiệp Về phương diện mã nguồn, NS-2 được viết với 100kB dòng mã lệnh C++, 70k dòng mã Tcl và 20k dòng tài liệu. 3.1.3 Các đặc tính của NS-2 NS-2 thực thi những tính năng sau: Các kỹ thuật quản lý hàng đợi Router như DropTail, RED, CBQ, Phát sóng đa chiều (multicasting) Mô phỏng mạng không dây o Được phát triển bởi Sun Microsystems + UC Berkeley (Dự án Daedalus) o Thuộc mặt đất (di động, ad-hoc, GPRS, WLAN, BLUETOOTH), vệ tinh o Chuẩn IEEE 802.11 có thể được mô phỏng, các giao thức Mobile-IP và ad-hoc như DSR, TORA, DSDV và AODV Hành vi nguồn lưu lượng (traffic) – www, CBR, VBR Các tác nhân (agent) truyền tải – UDP, TCP Định tuyến Luồng packet Mô hình mạng Các ứng dụng – Telnet, FTP, Ping Các packet tracing trên tất cả các link và trên các link xác định 3.2 Mô phỏng mạng cảm biến không dây trên NS-2 3.2.1 Bài toán mô phỏng Để xây dựng mô hình một mạng cảm biến không dây chúng ta cần quan tâm đến các tham số chính: topo của mạng, số lượng các nút mạng, năng lượng ban đầu của các nút, kích thước mỗi gói tin, các thông số vật lý của kênh vô tuyến. Kết quả của phần mềm mô phỏng thu được sẽ là: - Tổng năng lượng tiêu thụ bởi mỗi nút - Tổng số dữ liệu truyền từ mỗi nút đến trạm gốc - Số nút còn sống sau một thời gian xác định. Sinh viên: Đỗ Đức Hưng - Lớp CT902 33 Trường ĐHDL Hải Phòng
  34. Báo cáo đồ án tốt nghiệp 3.2.2 Mô hình phần mềm Hình 3.6 Mô hình cấu trúc phần mềm xây dựng trên NS-2 Các thành phần chính trong mô hình: - Wireless.tcl: lưu trữ các thông số chính của môi trường truyền sóng vô tuyến như tốc độ kênh truyền, năng lượng tổn hao trên kênh truyền - uAMPS.tcl: lưu trữ các thông số vật lý, các thông số giả thiết đầu vào của bài toán mô phỏng như: số lượng, vị trí các nút trong toàn mạng, mức ngưỡng năng lượng để truyền, nhận tín hiệu thành công, kích thước, năng lượng ban đầu của gói tin, các thông số của anten - ns-leach.tcl: thưc hiện các chứ năng của giao thức LEACH như chọn nút chủ cụm, phân chia cluster, truyền, nhận các bản tin của các nút. - start.tcl: lưu trữ các thông số của quá trình mô phỏng, các thông số này có thể dùng các chương trình đồ họa để hiển thị trực quan thông qua các đồ thị - Các file Resource Adaptive Node: lưu trữ các thông số của nút như: năng lượng, trạng thái hoạt động. Sinh viên: Đỗ Đức Hưng - Lớp CT902 34 Trường ĐHDL Hải Phòng
  35. Báo cáo đồ án tốt nghiệp 3.2.3 Các giao thức mô phỏng 3.2.3.1 LEACH Giới thiệu LEACH là giao thức phân cấp theo cụm thích ứng năng lượng thấp. Nó dựa trên thuật toán phân nhóm và có những đặc trưng sau: - Các nút có thể phân bố ngẫu nhiên và tự hình thành cụm - Việc truyền dữ liệu được điều khiển ở trong cụm. Tức là nút chủ cụm sẽ điều khiển các nút trong cụm gửi dữ liệu đến nó - Có quá trình xử lý dữ liệu như việc nút chủ cụm tổng hợp dữ liệu từ các nút gửi đến nó rồi gửi tới trạm gốc. Hình 3.7 Giao thức LEACH Trong LEACH, các nút tự tổ chức thành các cụm, trong đó một nút sẽ đóng vai trò là nút chủ cụm. Tất cả các nút không phải là nút chủ sẽ phải truyền dữ liệu của nó tới nút chủ. Nút chủ cụm phải nhận dữ liệu từ tất cả các nút thành viên trong cụm, thực hiện xử lý dữ liệu cục bộ rồi truyền tới trạm gốc. Bởi vậy, việc trở thành nút chủ sẽ tiêu hao nhiều năng lượng hơn các nút không được chọn là nút chủ. Trong bối cảnh mà năng lượng của các nút là giới hạn, nếu nút chủ được chọn cố định trong suốt thời gian sống của mạng, như trong giải thuật phân nhóm tĩnh (static clustering), thì các nút chủ sẽ hết năng lượng rất nhanh. Một khi nút chủ hết năng lượng, nó sẽ không hoạt động nữa. Khi nút chủ chết, tất cả các nút trong cụm sẽ không có khả năng trao đổi thông tin nữa. Vì thế, LEACH thực hiện ngẫu nhiên hóa, quay vòng vị trí các nút chủ có năng lượng cao trong số tất cả các nút để tránh sự tiêu hao năng lượng trên một nút cụ Sinh viên: Đỗ Đức Hưng - Lớp CT902 35 Trường ĐHDL Hải Phòng
  36. Báo cáo đồ án tốt nghiệp thể trong mạng. Theo cách này, năng lượng tải liên quan đến việc trở thành nút chủ sẽ được phân bố đều cho tất cả các nút. Hoạt động của LEACH được chia thành các vòng (round). Mỗi vòng bắt đầu cùng với pha thiết lập khi mà các cụm được hình thành, sau đó đến pha ổn định khi mà các khung dữ liệu được gửi tới các nút chủ và gửi tới trạm gốc. Tất cả các nút phải đồng bộ về mặt thời gian để bắt đầu pha thiết lập tại thời điểm giống nhau. Pha ổn định thường dài hơn rất nhiều so với pha thiết lập. Hình 3.8 Time-line hoạt động của LEACH Tự động cấu hình hình thành cụm (Self-configuring Cluster Formation): LEACH thực hiện phân cụm bằng việc sử dụng giải thuật phân tán, các nút tự quyết định mà không cần bất cứ sự điều khiển nào. Ưu điểm của phương pháp này là không yêu cầu việc giao tiếp với trạm gốc, do đó tránh được việc tiêu hao năng lượng nếu các nút ở xa trạm gốc. Đồng thời việc hình thành các cụm phân tán có thể được thực hiện mà không cân biết chính xác vị trí của các nút trong mạng. Thêm vào đó, nó không yêu cầu sự liên lạc toàn cục trong pha thiết lập cụm và không có giả thiết nào về trạng thái hiện tại của các nút khác trong quá trình hình thành cụm. Lựa chọn nút chủ cụm Khi các cụm đươc tạo ra, mỗi nút tự động quyết định nó có là nút chủ cho vòng tiếp theo hay không. Quá trình chọn lựa diễn ra như sau: mỗi nút cảm biến chọn một số ngẫu nhiên giữa 0 và 1. Nếu con số này nhỏ hơn ngưỡng T(n) thì nút đó trở thành nút chủ. T(n) được xác định theo phương trình sau: P T (n)= (3.1) 1 1 1Pr *( mod ) p Ở đây P quyết định số lượng trung bình các nút chủ trong một vòng, r là số vòng hiện tại. Dùng thuật toán này thì mỗi nút sẽ là nút chủ đúng một lần trong 1/P Sinh viên: Đỗ Đức Hưng - Lớp CT902 36 Trường ĐHDL Hải Phòng
  37. Báo cáo đồ án tốt nghiệp vòng. Chú ý rằng sau 1/P-1 vòng, T1(n)=1 với tất cả các nút chưa được làm nút chủ. Khi một nút được chọn làm nút chủ, nó sẽ thông báo tới tất cả các nút khác. Các nút không phải là nút chủ dùng những bản tin này từ các nút chủ để chọn cụm mà chúng muốn tham gia dựa trên cường độ tín hiệu nhận được bản tin này. Sau khi các nút chủ đã được hình thành, nó sẽ quyết định mô hình TDMA cho các nút tuỳ thuộc từng cụm, quảng bá mô hình và sau đó pha trạng thái tĩnh bắt đầu. Pha thiết lập Mỗi nút sẽ được chọn làm nút chủ cụm nếu xác suất của nó thỏa mãn phương trình (3.1). Nút chủ phải thông báo cho các nút khác trong mạng biết rằng nó được chọn làm nút chủ ở vòng hiện tại. Để thực hiện điều này, mỗi nút chủ sẽ phát bản tin quảng bá (ADV) dùng thuật toán CSMA (carrier sense multiple access). Bản tin này là một bản tin nhỏ bao gồm ID của nút và header để phân biệt bản tin này là bản tin quảng bá. Tuy nhiên, bản tin này phải được truyền quảng bá tới tất cả các nút trong mạng. Có hai lý do cho điều này, thứ nhất là để đảm bảo tất cả các nút lắng nghe bản tin quảng bá để tránh xảy ra đụng độ khi CSMA được dùng. Thứ hai là không có cơ chế để đảm bảo rằng các nút được chọn là nút chủ cụm sẽ được phân bố đều trên toàn mạng. Nếu công suất phát bản tin quảng bá bị giảm đi, một số nút ở biên có thể sẽ không nhận được thông báo và do đó có thể sẽ không là một thành phần trong vòng này. Hơn nữa, bản tin quảng bá rất nhỏ, do đó việc tăng công suất phát bản tin này để nó đến được tất cả các nút trong mạng không phải là một trở ngại. Bởi vậy công suất được thiết lập ở mức cao vừa đủ để tất cả các nút trong mạng có thể lắng nghe được bản tin ADV này. Những nút không phải là nút chủ sẽ quyết định nó sẽ nằm trong cụm nào bằng việc chọn xem nút chủ nào yêu cầu năng lượng giao tiếp thấp nhất dựa trên cường độ của tín hiệu nhận được từ bản tin quảng bá của mỗi nút chủ. Sau khi mỗi nút quyết định nó là thành viên của cụm nào, nó sẽ báo cho nút chủ của cụm đó biết. Mỗi nút sẽ phát bản tin join-request (Join-REQ) tới nút chủ và cũng dùng giao thức CSMA. Bản tin này cũng là một bản tin nhỏ, nó bao gồm ID của nút, ID nút chủ và header để phân biệt với các bản tin khác. Sinh viên: Đỗ Đức Hưng - Lớp CT902 37 Trường ĐHDL Hải Phòng
  38. Báo cáo đồ án tốt nghiệp Các nút chủ trong LEACH hoạt động như khối điều khiển trung tâm cục bộ để liên kết các dữ liệu trong cụm mà nó làm nút chủ. Nút chủ thiết lập bản tin định thời TDMA và truyền tới các nút trong cụm. Điều này đảm bảo sẽ không có đụng độ xảy ra và cho phép phần phát sóng radio của các nút không phải nút chủ sẽ ở trạng thái nghỉ. Nó chỉ thức dậy tại thời điểm mà nó truyền dữ liệu. Như vậy sẽ tiết kiệm được năng lượng cho các nút. Sau khi bản tin TDMA được truyền đến tất cả các nút trong cụm, pha thiết lập đã hoàn thành và bắt đầu pha ổn định (steady state phase). Hình 3.9 Giải thuật hình thành cluster trong LEACH Hình 3.9 mô tả sơ đồ giải thuật của quá trình hình thành cụm trong LEACH. Sau mỗi vòng thì lại bắt đầu pha thiết lập mới để chọn ra cụm mới phù hợp với mô hình mạng. Sinh viên: Đỗ Đức Hưng - Lớp CT902 38 Trường ĐHDL Hải Phòng
  39. Báo cáo đồ án tốt nghiệp Hình 3.10 Sự hình thành cụm ở 2 vòng khác nhau (nút đen là nút chủ) Pha ổn định Hoạt động của pha ổn định được chia ra thành các khung (frame). Mỗi nút sẽ gửi dữ liệu của nó tới nút chủ cụm một lần trên một khung trong khe định vị của nó. Mỗi nút sẽ có một khe thời gian cố định, cứ đến khe thời gian đó thì nút truyền dữ liệu tới nút chủ cụm. Số khe thời gian cho một khung dữ liệu phụ thuộc vào số lượng nút ở trong cụm. Tức là có bao nhiêu nút trong cụm (trừ nút chủ) thì sẽ có bấy nhiêu khe thời gian. Trong khi giải thuật phân tán để xác định nút chủ mong đợi rằng số cụm trong mỗi vòng là k, nhưng nó lại không có cơ chế đảm bảo rằng sẽ có k cụm trong mỗi vòng. Thêm vào đó giao thức trong pha thiết lập không đảm bảo rằng các nút sẽ phân bố đều cho mỗi nút chủ. Do đó, số nút trong mỗi cụm là khác nhau và tổng dữ liệu mà mỗi nút gửi đến nút chủ phụ thuộc vào số nút trong cụm. Để giảm sự tiêu thụ năng lượng, mỗi nút không phải là nút chủ sẽ điều khiển công suất phát dựa trên cường độ của bản tin quảng bá nhận được từ nút chủ. Hơn nữa là kênh phát sóng của nút sẽ ở trạng thái nghỉ cho đến khe thời gian được cấp phát cho nó. Các nút chủ sẽ phải giữ lại các dữ liệu mà các nút trong cụm gửi đến nó. Khi đã nhận được hết dữ liệu từ tất cả các nút, nó tiến hành xử lý dữ liệu cục bộ như nén, tổng hợp dữ liệu, Dữ liệu đã được tổng hợp sau đó được gửi tới trạm gốc. Khoảng cách từ nút chủ tới trạm gốc có thể xa và kích cỡ bản tin dữ liệu thường khá lớn, do đó mà năng lượng tiêu thụ do quá trình truyền này thường là cao. Nhìn vào hình 3.11 ta sẽ hiểu rõ hơn về hoạt động của pha ổn định. Sinh viên: Đỗ Đức Hưng - Lớp CT902 39 Trường ĐHDL Hải Phòng
  40. Báo cáo đồ án tốt nghiệp Hình 3.11 Mô hình LEACH sau khi đã ổn định trạng thái Hình 3.12 Hoạt động của pha ổn định trong LEACH Sinh viên: Đỗ Đức Hưng - Lớp CT902 40 Trường ĐHDL Hải Phòng
  41. Báo cáo đồ án tốt nghiệp Hình 3.12 chỉ ra time-line trong một vòng của LEACH, từ khi các cụm được hình thành trong pha thiết lập, qua hoạt động của pha ổn định khi dữ liệu được truyền từ các nút tới nút chủ cụm rồi truyền đến trạm gốc. Hình 3.13 Time-line hoạt động của LEACH trong một vòng Để mô tả về việc trao đôi thông tin trong phạm vi một cụm. Giao thức MAC và giao thức định tuyến được thiết kế để đảm bảo cho các nút tiêu thụ năng lượng thấp và không xảy ra đụng độ trong cụm. Tuy nhiên, kênh phát sóng không dây vốn là có phạm vi phát bản tin quảng bá ở mức trung bình. Do đó, sự phát sóng của một cụm cũng sẽ ảnh hưởng đến các cụm gần nó. Ví dụ như hình 3.14, sự phat sóng của nút A đến nút B cũng ảnh hưởng đến nút C Hình 3.14 Sự ảnh hƣởng của kênh phát sóng Để giảm thiểu sự ảnh hưởng này, mỗi cluster trong LEACH sẽ trao đổi thông tin dùng cơ chế trải phổ dãy trực tiếp (DS-SS - directed-sequence spread spectrum) hay đa truy nhập phân chia theo mã (CDMA – code division multiple access). Mỗi cụm sẽ dùng một mã trải phổ duy nhất, tất cả các nút trong cụm phát dữ liệu của chúng Sinh viên: Đỗ Đức Hưng - Lớp CT902 41 Trường ĐHDL Hải Phòng
  42. Báo cáo đồ án tốt nghiệp tới nút chủ sẽ dùng mã trải phổ này và nút chủ sẽ lọc tất cả các nút có mã trải phổ này. Chú ý rằng mỗi nút chủ chỉ cần một mã trải phổ đơn để lọc cho tất cả các tín hiệu đến nón mà sử dung mã trải phổ giống nhau. Điều này cũng hơi khác với cơ chế CDMA mà mỗi nút sẽ có một mà trải phổ duy nhất. Dữ liệu từ các nút chủ được gửi tới trạm gốc sẽ dùng một mã trải phổ cố định, và cũng dùng cơ chế CSMA để tránh xảy ra đụng độ với các nút khác. Tuy là kênh truyền vô tuyến, nhưng khi một nút chủ có dữ liệu để gửi tới BS, nó sẽ phải lắng nghe xem có nút chủ nào phát dữ liệu không. Nếu không có nút nào phát thì nó sẽ phát dữ liệu tới trạm gốc, còn nếu có nút đang phát dữ liệu thì nó sẽ đợi để phát dữ liệu. Tổng hợp dữ liệu Tổng hợp dữ liệu trong mạng cảm biến giúp loại trừ đi những thông tin dư thừa để thu được thông tin có ích về môi trường cảm biến. Việc tổng hợp dữ liệu có thể được thực hiện tại trạm gốc hoặc thực hiện cục bộ tại nút chủ của một cụm, điều này tùy thuộc vào năng lương tiêu thụ để tổng hợp dữ liệu so với năng lượng sử dụng để truyền những thông tin đó đi. Khi mà năng lượng cho truyền tin lớn hơn, thực hiện tổng hợp dữ liệu cục bộ tại nút chủ giúp giảm năng lượng tiêu thụ cho toàn hệ thống do có ít dữ liệu hơn phải truyền về trạm gốc. Nếu giả sử năng lượng cho tổng hợp dữ liệu đối với mỗi bit là EDA và năng lượng để truyền một bit về trạm gốc là ETX. Thêm vào đó, giả sử thuật tổng hợp dữ liệu giúp nén dữ liệu với tỉ lệ L:1. Ta thu được công thức biểu diễn năng lượng để tổng hợp L bit dữ liệu cục bộ tại nút chủ, sau đó được gửi về trạm gốc như sau: ELocal-DA=L*EDA+ETX Năng lượng để truyền thẳng L bit dữ liệu về trạm gốc: ENo-DA=L*ETX L 1 Ta thấy, ELocal-DA<ENo-DA khi EDA< *ETX, từ đó ta có thể nhận định được khi nào L thì việc tổng hợp dữ liệu cục bộ mang lại sự hiệu quả về mặt năng lượng cho toàn mạng. Sinh viên: Đỗ Đức Hưng - Lớp CT902 42 Trường ĐHDL Hải Phòng
  43. Báo cáo đồ án tốt nghiệp Hình 3.15 Đồ thị so sánh năng lƣợng sử dụng khi có và không có tổng hợp dữ liệu cục bộ -6 L=20 (tương ứng 20 nút trong cụm), ETX=1,05x10 J, khoảng cách đến trạm gốc là 100m. 3.2.3.2 LEACH-C (LEACH-Centralized) Trong khi có những ưu điểm của giải thuật hình thành cụm phân tán của LEACH, tức là mỗi nút tự nó quyết định sẽ ở trong cụm nào. Nhưng giải thuật này lại không đảm bảo được vị trí cũng như số lượng nút chủ trong toàn mạng. Tuy nhiên, việc dùng một giải thuật điều khiển trung tâm để hình thành cụm có thể tạo ra các cụm tốt hơn với các nút chủ phân tán trên toàn mạng. Giải thuật này gọi là LEACH-C. LEACH-C có pha ổn định giống với LEACH (các nút gửi dữ liệu tới nút chủ và nút chủ tổng hợp dữ liệu rồi gửi về trạm gốc), nó chỉ khác LEACH ở pha thiết lập. Trong pha thiết lập của LEACH-C, các nút sẽ gửi thông tin về trạng thái hiện tại của nó (bao gồm vị trí và năng lượng) về trạm gốc. Trạm gốc sau đó sẽ dùng thuật toán tối ưu để xác định ra các cụm và nút chủ cho vòng đó. Sinh viên: Đỗ Đức Hưng - Lớp CT902 43 Trường ĐHDL Hải Phòng
  44. Báo cáo đồ án tốt nghiệp Hình 3.16 Pha thiết lập của LEACH-C Việc dùng trạm gốc để xác định cụm nói chung là tốt hơn so với việc hình thành cụm dùng giải thuật phân tán. Tuy nhiên, LEACH-C yêu cầu các nút phải gửi thông tin về vị trí của nó về trạm gốc tại thời điểm bắt đầu của mỗi vòng, thông tin này có thể bao gồm việc phải sử dụng hệ thống định vị toàn cầu (GPS-Global positioning system) để xác định vị trí hiện tại của mỗi nút. Để xác định được các cụm có tính thích ứng tốt, trạm gốc cần chắc chắn rằng tải năng lượng được phân bố đều trên tất cả các nút trong mạng. Để làm được điều này trạm gốc tính toán năng lượng trung bình của các nút. Nút nào mà có năng lượng nhỏ hơn năng lượng trung bình này sẽ không được chọn làm nút chủ ở vòng đó, những nút còn lại có năng lượng lớn hơn giá trị trung bình đó có thể là nút chủ. Trạm gốc sẽ chạy giải thuật nhiều lần để chọn ra k nút tốt nhất trở thành nút chủ cũng như chọn ra được k cụm tối ưu. Khi chọn được các nút chủ và các cụm tối ưu, trạm gốc sẽ gửi thông tin này tới tất cả các nút trong mạng. Việc này được thực hiện bằng việc phát quảng bá bản tin bao gồm ID của nút chủ cho mỗi nút. Nếu nút nào có ID trùng với ID trong bản tin nó sẽ trở thành nút chủ, các nút khác sẽ xác định khe thời gian của nó cho việc phát dữ liệu, và sẽ ở trạng thái nghỉ cho đến thời điểm nó phát dữ liệu về nút chủ. Pha ổn đinh của LEACH-C giống hệt LEACH. 3.2.3.3 Phân cụm cố định (Stat-Cluster) Nguyên tắc hoạt động tương tự với LEACH-C. Trạm gốc sẽ căn cứ vào tọa độ và năng lượng hiện tại của các nút để phân chia cấu hình mạng. Tuy nhiên ở Stat-Cluster trạm gốc chỉ chia nhóm một lần và giữ nguyên cấu hình mạng đó để gửi dữ liệu. Sinh viên: Đỗ Đức Hưng - Lớp CT902 44 Trường ĐHDL Hải Phòng
  45. Báo cáo đồ án tốt nghiệp Ƣu điểm: Các nút chủ cụm là cố định nên không tốn thời gian và năng lượng cho quá trình phân chia lại. Nhƣợc điểm: Thời gian sống ngắn vì quá trình chọn nút chủ cụm ban đầu là ngẫu nhiên và nếu các nút chủ cụm này ở quá xa trạm gốc thì mạng sẽ hết năng lượng rất nhanh. 3.2.3.4 Năng lƣợng truyền tối thiểu (Minimum Transmit Energy) Hình 3.17 Hoạt động của giao thức MTE Trong phương pháp định tuyến này dữ liệu được truyền đi theo đường ngắn nhất, sử dụng cơ chế CSMA. Ƣu điểm: - Thời gian sống của mạng có lúc rất lâu vì các nút chỉ tốn năng lượng trao đổi dữ liệu với các nút gần nhau nhất. - Khi xảy ra đụng độ thì các nút sẽ đợi và truyền lại dữ liệu theo cơ chế CSMA. Nhƣợc điểm: - Khi số nút lớn thì mạng sẽ thường xuyên xảy ra lặp và đụng độ. - Dữ liệu sẽ không thu được hoặc sẽ không như mong muốn khi mà nút ở quá xa so với trạm gốc. - Thời gian sống lâu nhưng dữ liệu thu được phụ thuộc vào vị trí đặt trạm gốc - Trong thực tế trạm gốc sẽ đặt cách xa các vùng cảm biến nên nếu dùng MTE thì rất có thể mạng vẫn trao đổi thông tin nhưng ta sẽ không thu được dữ liệu gì về trạm gốc. Sinh viên: Đỗ Đức Hưng - Lớp CT902 45 Trường ĐHDL Hải Phòng
  46. Báo cáo đồ án tốt nghiệp 3.2.4 Mô phỏng Tiến hành mô phỏng 4 giao thức định tuyến: LEACH, LEACH-C, MTE, STAT-CLUSTER với các thông số đầu vào: - Tổng số nút: 101 (bao gồm 1 trạm gốc) - Phạm vi đặt các nút: 100m x 100m (các nút được đặt ngẫu nhiên) - Năng lượng ban đầu của mỗi nút: 2J - Trạm gốc đặt tại vị trí có tọa độ: (50,100) - Thời gian mô phỏng: 300s - Số cụm khởi tạo: 5 Kết quả thu đƣợc: Hình 3.18 Số nút mạng còn sống theo thời gian Sinh viên: Đỗ Đức Hưng - Lớp CT902 46 Trường ĐHDL Hải Phòng
  47. Báo cáo đồ án tốt nghiệp Đánh giá: - Với giao thức Stat-Cluster (đường màu vàng) thì các nút mạng chết rất nhanh sau một thời gian ngắn vì thuật toán của Stat-Cluster là chỉ phân chia cụm một lần nên nếu các nút chủ cụm ở xa trạm gốc thì năng lượng để truyền dữ liệu về trạm gốc là rất lớn. - Với giao thức MTE (đường màu xanh đậm) thì thời gian sống của mạng lâu hơn vì các nút chỉ tốn năng lượng trao đổi dữ liệu với các nút ở gần nhất. Hình 3.19 Năng lƣợng tiêu thụ của toàn mạng theo thời gian Đánh giá: Trong khoảng 100s đầu tiên, mức tiêu thụ năng lượng của cả 4 giao thức xấp xỉ nhau. Tuy nhiên, càng về sau thì mức tiêu thụ năng lượng của MTE càng giảm chậm hơn. LEACH tiêu tốn nhiều năng lượng hơn LEACH-C. Stat-Cluster tiêu tốn năng lượng nhiều nhất. Sinh viên: Đỗ Đức Hưng - Lớp CT902 47 Trường ĐHDL Hải Phòng
  48. Báo cáo đồ án tốt nghiệp Hình 3.20 Tỉ lệ nút/số bytes nhận đƣợc ở trạm gốc Đánh giá: - Với MTE dữ liệu từ các nút gửi thành công về trạm gốc rất nhỏ do cơ chế truyền của MTE là CSMA nên khi có đụng độ trên mạng thì các nút sẽ đợi và truyền lại dữ liệu. - LEACH-C tỏ rõ ưu thế vượt trội nếu tính trên lượng dữ liệu được các nút gửi thành công về trạm gốc. Sinh viên: Đỗ Đức Hưng - Lớp CT902 48 Trường ĐHDL Hải Phòng
  49. Báo cáo đồ án tốt nghiệp Hình 3.21 Tỉ lệ dữ liệu / năng lƣợng Đánh giá: - MTE: Mặc dù thời gian sống của mạng lâu nhưng lượng dữ liệu nhận được ở trạm gốc là rất nhỏ. Có thể nói trong giao thức định tuyến này mức hao phí năng lượng tính trên lượng dữ liệu nhận được là rất lớn và kém hiệu quả. - LEACH-C: có lượng dữ liệu gửi về trạm gốc tính trên một đơn vị năng lượng hiệu quả nhất trong 4 giao thức. Sinh viên: Đỗ Đức Hưng - Lớp CT902 49 Trường ĐHDL Hải Phòng
  50. Báo cáo đồ án tốt nghiệp Hình 3.22 Biểu đồ trễ tín hiệu tại trạm gốc Đánh giá: Có khá nhiều biến động trong quá trình dữ liệu được gửi từ các nút về trạm gốc ở giao thức LEACH Để có thể đánh giá một cách toàn diện ảnh hưởng của các tham số tới hoạt động của mạng, tác giả đã thay đổi 1 thông số giả thiết ban đầu, các thông số khác giữ nguyên. - Kết quả thu đƣợc khi thay đổi vùng đặt các nút mạng từ diện tích 100x100 thành 1000x1000: Sinh viên: Đỗ Đức Hưng - Lớp CT902 50 Trường ĐHDL Hải Phòng
  51. Báo cáo đồ án tốt nghiệp Hình 3.23 Số nút mạng còn sống theo thời gian Sinh viên: Đỗ Đức Hưng - Lớp CT902 51 Trường ĐHDL Hải Phòng
  52. Báo cáo đồ án tốt nghiệp Hình 3.24 Năng lƣợng tiêu thụ của toàn mạng theo thời gian Sinh viên: Đỗ Đức Hưng - Lớp CT902 52 Trường ĐHDL Hải Phòng
  53. Báo cáo đồ án tốt nghiệp Hình 3.25 Tỉ lệ nút/số bytes nhận đƣợc ở trạm gốc Sinh viên: Đỗ Đức Hưng - Lớp CT902 53 Trường ĐHDL Hải Phòng
  54. Báo cáo đồ án tốt nghiệp Hình 3.26 Tỉ lệdữ liệu / năng lƣợng Sinh viên: Đỗ Đức Hưng - Lớp CT902 54 Trường ĐHDL Hải Phòng
  55. Báo cáo đồ án tốt nghiệp Hình 3.27 Biểu đồ trễ tín hiệu tại trạm gốc Nhận xét: Khi tăng diện tích của vùng các nút mạng, đồng nghĩa với việc các nút mạng nằm cách xa nhau hơn và khoảng cách tới trạm gốc cũng tăng theo. Điều đó dẫn tới năng lượng để truyền dữ liệu giữa các nút cũng tăng. Qua các đồ thị cho thấy thời gian sống của mạng bị giảm đi đáng kể: Xét với giao thức LEACH thì ở giả thiết ban đầu (diện tích 100x100) sau 300s có 60 nút mạng còn sống nhưng khi tăng diện tích lên 1000x1000 thì sau 300s chỉ còn 22 nút mạng còn sống (hình 3.18 và hình 3.23). Sinh viên: Đỗ Đức Hưng - Lớp CT902 55 Trường ĐHDL Hải Phòng
  56. Báo cáo đồ án tốt nghiệp Bên cạnh đó thời gian trễ tại trạm gốc cũng tăng lên đáng kể (hình 3.22 và hình 3.27), trễ lớn nhất trong trường hợp đầu tiên (hình 3.22) chỉ là 0.9s nhưng trong trường hợp thứ 2 (hình 3.27) đã là 9s. Qua đó có thể thấy rằng yếu tố diện tích đặt nút mạng ảnh hưởng rất lớn đến thời gian sống, cũng như khả năng truyền dữ liệu của mạng. - Kết quả thu đƣợc khi thay đổi năng lƣợng ban đầu của mỗi nút mạng từ 2J lên 10J: Hình 3.28 Số nút mạng còn sống theo thời gian Sinh viên: Đỗ Đức Hưng - Lớp CT902 56 Trường ĐHDL Hải Phòng
  57. Báo cáo đồ án tốt nghiệp Hình 3.29 Năng lƣợng tiêu thụ của toàn mạng theo thời gian Sinh viên: Đỗ Đức Hưng - Lớp CT902 57 Trường ĐHDL Hải Phòng
  58. Báo cáo đồ án tốt nghiệp Hình 3.30 Tỉ lệ nút/số bytes nhận đƣợc ở trạm gốc Sinh viên: Đỗ Đức Hưng - Lớp CT902 58 Trường ĐHDL Hải Phòng
  59. Báo cáo đồ án tốt nghiệp Hình 3.31 Tỉ lệ dữ liệu / năng lƣợng Sinh viên: Đỗ Đức Hưng - Lớp CT902 59 Trường ĐHDL Hải Phòng
  60. Báo cáo đồ án tốt nghiệp Hình 3.32 Biểu đồ trễ tín hiệu tại trạm gốc Nhận xét: Khi tăng năng lượng ban đầu của mỗi nút lên 5 lần (từ 2J -> 10J) thì thời gian sống và độ trễ trên trạm gốc của mạng được cải thiện rõ rệt: Xét với giao thức LEACH: trong 300s đầu tiên tất cả 100 nút mạng vẫn còn sống (hình 3.28) và thời gian trễ trên trạm gốc giảm (từ 0.9s -> 0.17s) (hình 3.32). Tuy nhiên trên thực tế thì chỉ có thể tăng nguồn năng lượng cấp cho mỗi nút mạng đến một mức độ nào đó. Vì thế nên chúng ta cần phải nghiên cứu các thuật toán định tuyến mới để có thể sử dụng hiệu quả nguồn năng lượng hạn chế này. Sinh viên: Đỗ Đức Hưng - Lớp CT902 60 Trường ĐHDL Hải Phòng
  61. Báo cáo đồ án tốt nghiệp KẾT LUẬN Mạng cảm biến không dây có những ưu điểm trong việc thu thập dữ liệu, xử lí và phân phối dữ liệu về các môi trường khác nhau. Với những tính năng ưu việt và khả năng ứng dụng to lớn mạng cảm biến không dây đã mau chóng giành được sự quan tâm của các nhà nghiên cứu nhiều nơi. Nhờ những tiến bộ khoa học kĩ thuật, việc chế tạo các thiết bị cảm biến nhỏ gọn, giá thành thấp, tiêu thụ ít năng lượng có khả năng cảm nhận dữ liệu, tính toán và giao tiếp vô tuyến trở nên khả thi. Vì vậy mạng cảm biến không dây đang phát triển nhanh chóng. Tuy vậy, việc thiết kế và thực hiện có hiệu quả gặp rất nhiều khó khăn do những đặc điểm riêng biệt và những hạn chế. Các giao thức dùng trong mạng cảm biến phải tính đến các khó khăn, thử thách này. Định tuyến trong mạng cảm biến là một lĩnh vực mới thu hút nhiều sự quan tâm nghiên cứu của các nhà khoa học, đặc biệt là xét về khía cạnh tối ưu nguồn năng lượng sử dụng trong mạng. Chính vì thế đồ án đã trình bày các thuật toán và đánh giá dựa trên lý thuyết và các kết quả mô phỏng. Dựa vào đó có thể lựa chọn một giao thức định tuyến phù hợp nhất với từng ứng dụng cụ thể. Sinh viên: Đỗ Đức Hưng - Lớp CT902 61 Trường ĐHDL Hải Phòng
  62. Báo cáo đồ án tốt nghiệp CÁC TÀI LIỆU THAM KHẢO [1]-Bhaskar Krishnamachari, “Networking Wireless Sensors”, Cambridge University Press, 2005. [2]-HolgerKarl and AndreasWillig, “Protocols and Architectures for Wireless Sensor Networks”, John Wiley & Sons, Ltd, 2005. [3]-I.F. Akyildiz, W. Su*, Y. Sankarasubramaniam, E. Cayirci, “Wireless sensor networks: a survey”, Broadband and Wireless Networking Laboratory, School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA, Received 12 December 2001; accepted 20 December 2001 [4]-Jamal N. Al-Karaki Ahmed E. Kamal, “Routing Techniques in Wireless Sensor Networks”, Dept. of Electrical and Computer Engineering Iowa State University, Ames, Iowa 50011. [5]-Kazem Sohraby, Daniel Minoli, Taieb Znati, “Wireless sensor networks technology protocols and applications”, John Wiley & Sons, Ltd, 2007. [6]-K. Kalpakis, K. Dasgupta, and P. Namjoshi, “Maximum Lifetime Data Gathering and Aggregation in Wireless Sensor Networks”, In the Proceedings of the 2002 IEEE International Conference on Networking (ICN'02), Atlanta, Georgia, August 26-29, 2002. pp. 685-696. [7]-“The NS Manual”: Sinh viên: Đỗ Đức Hưng - Lớp CT902 62 Trường ĐHDL Hải Phòng