Đồ án Tổng quan mạng cảm nhận không dây WSN và mô phỏng giao thức định tuyến Leach

Nội dung text: Đồ án Tổng quan mạng cảm nhận không dây WSN và mô phỏng giao thức định tuyến Leach

1. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN TỔNG QUAN MẠNG CẢM NHẬN KHÔNG DÂY WSN VÀ MÔ PHỎNG GIAO THỨC ĐỊNH TUYẾN LEACH MỤC LỤC CHƢƠNG I: Tổng quan mạng cảm nhận không dây 3 1.1 Giới thiệu 3 1.2 Khái niệm , ứng dụng mạng WSN 3 1.3 Cấu tạo một nút mạng 5 1.3.1 Phần cứng 5 1.3.2 Phần mềm 8 1.4 Quản lý năng lƣợng của các thiết bị 8 1.4.1 Chế độ hoạt động và năng lƣợng tiêu thụ 8 1.4.2 Tiết kiệm năng lƣợng trong vi điều khiển 8 1.4.3 Tiết kiệm năng lƣợng trong bộ nhớ 8 1.4.4 Tiết kiệm năng lƣợng trong truyền nhận vô tuyến. 9 1.4.5 Tiết kiệm năng lƣợng của cảm biến. 9 1.4.6 Mối liên hệ giữa việc tiền xử lý và truyền – nhận dữ liệu. 9 1.5 Chế độ hoạt động và tiếp kiệm năng lƣợng 9 1.6 Kiến trúc mạng 9 1.6.1 Mô hình mạng 10 1.6.2 Hai cấu trúc cơ bản của mạng cảm nhận không dây 11 1.6.3 Mục tiêu thiết kế mạng cảm nhận và tiêu chí đánh giá 12 1.7 Mô hình phân lớp trong mạng WSN 14 1.7.1 Lớp vật lý 14 1.7.1.1 Giới thiệu chung 14 1.7.2 Lớp liên kết dữ liệu và thủ tục thâm nhập môi trƣờng 17 CHƢƠNG II: Phân tuyến trong mạng WSN 25 2.1. Giới thiệu 25 2.2. Thách thức trong vấn đề phân tuyến 25 2.3.1. Đặc tính thay đổi thời gian và trật tự sắp xếp của mạng 25 2.3.2. Ràng buộc về tài nguyên 26 2.3.3. Mô hình dữ liệu trong mạng cảm biến 26 2.3.4. Cách truyền dữ liệu 26 2.4. Phân loại và so sánh các giao thức phân tuyến 27 2.4.1 Giao thức phân tuyến ngang hàng 29 2.4.2 Nhóm giao thức phân cấp 32 2.4.3 Giao thức dựa trên vị trí 34 CHƢƠNG III : Các cấu trúc giao thức phân tuyến LEACH 38 3.1 Giới thiệu 38 3.2.1. Xác định nút cluster-head 40 3.2.2. Giai đoạn thiết lập 40 3.2.3. Giai đoạn ổn định 42 3.2.5 Nhƣợc điểm 44 3.3. Leach-C: thành lập cụm trạm cơ sở 44 3.4. Leach-F: nhóm cố định, luân phiên cluster-head 45 CHƢƠNG IV: Phân tích và mô phỏng LEACH 48 4.1 Tổng quan về NS2 48 4.1.1 Giới thiệu về NS2 48 1
2. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN 4.1.2 Cơ cấu tổ chức NS2 48 4.2 Mã MIT 50 4.3. Giả thiết mô phỏng 51 4.4.1. Câu lệnh 52 4.4.2 Các nút bắt đầu với mức năng lƣợng bằng nhau 52 4.4.4. Nút bắt đầu bằng năng lƣợng không cân nhau. 58 4.4.5. Mở rộng kích cỡ của mạng lƣới 58 4.4.6. Gia tăng năng lƣợng nút 59 4.5. Tóm tắt 59 Chƣơng V: Kết luận và dự kiến trong tƣơng lai 61 5.1. Thu đƣợc kết quả 61 5.2. Dự kiến trong tƣơng lai 62 TÀI LIỆU THAM KHẢO 63 2
3. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN CHƢƠNG I: Tổng quan mạng cảm nhận không dây 1.1 Giới thiệu Trong những năm gần đây, rất nhiều mạng cảm nhận không dây đã và đang đƣợc phát triển và triển khai cho nhiều các ứng dụng khác nhau nhƣ: theo dõi sự thay đổi của môi trƣờng, khí hậu, giám sát các mặt trận quân sự, phát hiện và do thám việc tấn công bằng hạt nhân, sinh học và hoá học, chuẩn đoán sự hỏng hóc của máy móc, thiết bị, theo dấu và giám sát các bác sỹ, bệnh nhân cũng nhƣ quản lý thuốc trong các bệnh viên, theo dõi và điều khiển giao thông, các phƣơng tiện xe cộ Hơn nữa với sự tiến bộ công nghệ gần đây và hội tụ của hệ thống các công nghệ nhƣ kỹ thuật vi điện tử, công nghệ nano, giao tiếp không dây, công nghệ mạch tích hợp, vi mạch phần cảm biến, xử lý và tính toán tín hiệu đã tạo ra những con cảm biến có kích thƣớc nhỏ, đa chức năng, giá thành thấp, công suất tiêu thụ thấp, làm tăng khả năng ứng dụng rộng rãi của mạng cảm biến không dây. Một mạng cảm nhận không dây là một mạng bao gồm nhiều nút cảm biến nhỏ có giá thành thấp, và tiêu thụ năng lƣợng ít, giao tiếp thông qua các kết nối không dây, có nhiệm vụ cảm nhận, đo đạc, tính toán nhằm mục đích thu thập, tập trung dữ liệu để đƣa ra các quyết định toàn cục về môi trƣờng tự nhiên . Những nút cảm biến nhỏ bé này bao gồm các thành phần : Các bộ vi xử lý rất nhỏ, bộ nhớ giới hạn,bộ phận cảm biến, bộ thu phát không dây, nguồn nuôi. Kích thƣớc của các con cảm biến này thay đổi từ to nhƣ hộp giấy cho đến nhỏ nhƣ hạt bụi, tùy thuộc vào từng ứng dụng. Khi nghiên cứu về mạng cảm nhận không dây, một trong những đặc điểm quan trọng và then chốt đó là thời gian sống của các con cảm biến hay chính là sự giới hạn về năng lƣợng của chúng. Các nút cảm biến này yêu cầu tiêu thụ công suất thấp. Các nút cảm biến hoạt động có giới hạn và nói chung là không thể thay thế đƣợc nguồn cung cấp. Do đó, trong khi mạng truyền thông tập trung vào đạt đƣợc các dịch vụ chất lƣợng cao, thì các giao thức mạng cảm nhận phải tập trung đầu tiên vào bảo toàn công suất. Mạng cảm biến có một số đặc điểm sau: + Có khả năng tự tổ chức. + Yêu cầu ít hoăc không có sự can thiệp của con ngƣời. + Truyền thông vô tuyến và truyền đa bƣớc. + Triển khai số lƣợng lớn trên phạm vi rộng. + Năng lƣợng, bộ nhớ, khả năng xử lý có hạn. + Cấu hình thƣờng xuyên thay đổi do môi trƣơng hoặc nút mạng. + Quảng bá trong phạm vi hẹp và định tuyến multihop Các giới hạn về mặt năng lƣợng, công suất phát, bộ nhớ và công suất tính toán Chính những đặc tính này đã đƣa ra những chiến lƣợc mới và những yêu cầu thay đổi trong thiết kế mạng cảm biến. 1.2 Khái niệm , ứng dụng mạng WSN 3
4. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN Đn1:Mạng cảm nhận không dây là một mạng không dây mà các nút mạng là các vi điều khiển sau khi đã đƣợc cài đặt phần mềm nhúng kết hợp với các bộ phát song vô tuyến cùng với các cảm biến và nó co khả năng thu nhận,xử lý dữ liệu từ các nút mạng và môi trƣờng xung quanh nút mạng. Đn2:Mạng cảm nhận không dây(WSN) là mạng sử dụng phƣơng thức truyền nhận bằng sóng Radio mà các nút mạng đƣợc tích hợp bộ vi điều khiển và bộ cảm biến. Tóm lại khái niệm mạng cảm nhận không dây dựa trên công thức đơn giản sau: Cảm nhận + CPU + Radio = WSN Từ công thức đơn giản trên rất nhiều ứng dụng đã xuất hiện ví dụ nhƣ: * Quân sự: Dựa trên ƣu điểm có thể triển khai nhanh chóng ( Dải từ máy bay), với khả năng tự cấu hình lại khi có nút bị hỏng đƣa mạng cảm nhận không dây trở thành một ứng dụng hữu ích trên chiến trƣờng. Chủ yếu là: theo dõi lực lƣợng, trang bị, hƣớng di chuyển, phát hiện giám sát mục tiêu, các dấu hiệu vũ khí nguyên tử, sinh học. * Môi trƣờng: đây là ứng dụng phổ biến nhất của mạng cảm nhận không dây bao gồm: theo dõi sự xuất hiện và di chuyển của động vật, theo dõi nhiệt độ, mức nƣớc, áp suất khí quyển v.v Trong đó ứng dụng dễ nhận thấy nhất là cảnh báo cháy rừng, cảnh báo lũ. Hình 1.2: Ứng dụng theo dõi sự di chuyển của động vật * Ứng dụng trong chăm sóc sức khỏe :một vài ứng dụng về sức khỏe đối với mạng cảm biến là giám sát bệnh nhân, các triệu chứng, quản lý thuốc trong bệnh viện, giám sát sự chuyển động và xử lý bên trong của côn trùng hoặc các động vật nhỏ khác, theo dõi và kiểm tra bác sĩ và bệnh nhân trong bệnh viện. Theo dõi bác sĩ và bệnh nhân trong bệnh viện: mỗi bệnh nhân đƣợc gắn một nút cảm biến nhỏ và nhẹ, mỗi một nút cảm biến này có nhiệm vụ riêng, ví dụ có nút cảm 4
5. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN biến xác định nhịp tim trong khi con cảm biến khác phát hiện áp suất máu, bác sĩ cũng có thể mang nút cảm biến để cho các bác sĩ khác xác định đƣợc vị trí của họ trong bệnh viện. Hình 1.3: Ứng dụng trong y tế Mạng cảm nhận không dây có rất nhiều ứng dụng nhƣng hầu hết các ƣng dụng đều thuộc ba dạng: thu thập dữ liệu môi trƣờng, giám sát an ninh, và theo dõi đối tƣợng. 1.3 Cấu tạo một nút mạng 1.3.1 Phần cứng Tùy từng yêu cầu ứng dụng cụ thể mà phần cứng trong nút mạng yêu cầu có thể khác nhau, ở đây chúng ta sẽ tìm hiểu những thành phần cơ bản của một nút mạng: + Vi điều khiển: xử lý dữ liệu và thi hành chƣơng trình tại nút. + Bộ nhớ: Lƣu trữ chƣơng trình và dữ liêu, bộ nhớ chƣơng trình và bộ nhớ dữ liệu thƣờng tách biệt nhau tuân theo kiến trúc havard. + Cảm biến: tƣơng tác với môi trƣờng vật lý để theo dõi và điều khiển các thống số của môi trƣờng. + Thiết bị giao tiếp: Thiết bị cung cấp khả năng truyền – nhận dữ liệu giữa các nút qua kênh vô tuyến + Nguồn: Thƣờng xử dụng pin với năng lƣợng có hạn, trong một số ứng dụng thì năng lƣợng có thể đƣợc bổ xung bởi môi trƣờng nếu có thể ( sử dụng pin mặt trời) 5
6. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN Hình 1.4: Các thành phần cơ bản của một nút mạng thông thƣờng Một số loại nút mạng: Hình 1.5 Nút mạng thuộc họ Mica Mote Họ nút mạng này nằm trong dự án nghiên cứu của trƣờng đại học california từ cuối năm 1990, sử dụng vi xử lý của Atmel, sử dụng hệ điều hành TinyOS. Hình 1.6 Nút mạng EYES Nút mạng này phát triển bởi một tổ chức của châu âu trong dự án sử dụng năng lƣợng hiệu quả của mạng cảm nhận - Energy efficient sensor network (EYES). Nút mạng sử dụng vi điều khiển MSP 430 của Texas, có khả năng kết nối thêm cảm biến. Nút mạng này sử dụng vi điều khiển CC1010 của chipcon, tích hợp thiết bị truyền dẫn vô tuyến và cảm biến nhiệt độ 1.3.1.1 Vi xử lý 6
7. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN Vi xử lý là thiết bị quan trọng nhất trong nút mạng cảm nhận không dây, thực hiện thu thập dữ liệu từ các nút, sau đó xử lý trƣớc khi gửi đi, và nhận dữ liệu từ các nút khác. Nguyên nhân nó đƣợc lựa chọn trong các hệ thống nhúng là mềm dẻo trong kết nối với các thiết bị khác nhƣ thiết bị cảm biến, tiêu thụ năng lƣợng thấp nhờ khả năng chuyển sang chế độ ngủ khi đó chỉ có một phần của vi điều khiển hoạt động, hơn nữa thƣờng có bộ nhớ tích hợp ngay trên bộ vi xử lý. Một đặc điểm rất đƣợc ngƣời lập trình yêu thích là khả năng lập trình bằng ngôn ngữ bậc cao (C, C++). Bởi vậy khi xây dựng nút mạng việc xem xét hiệu suất của vi xử lý, hiệu quả năng lƣợng và giá thành là rất quan trọng. 1.3.1.2 Bộ nhớ Đƣợc sử dụng để lƣu trữ dữ liệu thu từ các nút cảm biến, hoặc gói dữ liệu từ các nút khác, có 2 loại kiến trúc bộ nhớ là: kiến trúc havard và kiến trúc von newman, điểm khác nhau của 2 kiến trúc này là trong kiến trúc havard thì bộ nhớ dữ liệu và chƣơng trình tách biệt nhau khi đó dữ liệu thƣờng đƣợc chứa trong RAM còn chƣơng trình đƣợc chứa trong ROM hoặc bộ nhớ FLASH, còn trong kiến trúc von newman thì dữ liệu và chƣơng trình đƣợc lƣu cùng với nhau, thƣờng là trên RAM, nhƣợc điểm của nó là dữ liệu sẽ bị mất khi tắt nguồn, bởi vậy chƣơng trình hoặc hệ điều hành thƣờng đƣợc lƣu trữ trên ROM, EEPROM, hoặc bộ nhớ flash ( gần tƣơng tự nhƣ EEPROM). Yêu cầu kích thƣớc bộ nhớ và năng lƣợng tiêu thụ tƣơng ứng với yêu cầu về dữ liệu của ứng dụng của nút mạng. 1.3.1.3 Thiết bị giao tiếp Là thiết bị đƣợc sử dụng để trao đổi dữ liệu giữa các nút đơn với nhau, trong đó môi trƣờng không dây là đƣợc ƣa dùng hơn cả, đó có thể là sóng vô tuyến, truyền thông quang, sóng siêu âm, từ trƣờng cũng đƣợc sử dụng trong một vài ứng dụng đặc biệt. Trong đó sóng vô tuyến cung cấp dải thông lớn với tốc độ dữ liệu cao là phù hợp nhất cho hầu hết các ứng dụng của mạng không dây. Trong đó các nút yêu cầu cả chức năng nhận và truyền dữ liệu (điều chế, giải điều chế, khuếch đại, lọc, trộn ) sau đó chuyển luồng bit, byte hoặc khung thành sóng vô tuyến, thông thƣờng 2 thiết bị này thƣờng đƣợc kết hợp thành một thiết bị duy nhất, bởi vậy thƣờng thì tại một thời điểm không thể thực hiện đồng thời vừa truyền vừa nhận dữ liệu, mà truyền và nhận sẽ đƣợc luân phiên nhau đƣợc điều khiển bởi hệ điều hành nhúng. Khi lựa chọn thiết bị truyền nhận cần lƣu ý vài đặc điểm sau: -Khả năng phục vụ cho lớp trên (MAC), cho phép lớp này điều khiển gói dữ liệu -Tiết kiệm năng lƣợng và sử dụng năng lƣợng hiệu quả do năng lƣợng tiêu thụ nhiều nhất trong nút mạng là do việc truyền nhận vô tuyến. -Tần số sóng mang và đa kênh truyền trong truyền nhận phải phù hợp với yêu cầu của ứng dụng. -Tốc độ dữ liệu tƣơng ứng với tần số sóng mang và băng tần cùng với việc điều chế và mã hóa dữ liệu, tốc dộ này có thể thay đổi bằng điều chế hoặc thay đổi tốc độ của ký tự. -Điều chế và mã hóa 1.3.1.4 Cảm biến 7
8. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN Có rất nhiều loại cảm biến, tùy vào loại ứng dụng trong mạng cảm nhận mà ta có các cảm biến tƣơng ứng, thƣờng là dựa vào kiểu hoạt động của cảm biến, tích cực- thụ động, phạm vi giám sát năng lƣợng tiêu thụ, giá thành và kích thƣớc. Thƣờng thì việc lựa chọn cảm biến không phức tạp nhƣ bộ nhớ và vi xử lý. 1.3.1.5 Nguồn nuôi Là thành phần cốt yếu của mạng cảm nhận, trong đó 2 vấn đề cần quan tâm là khả năng lƣu trữ và cung cấp năng lƣợng, và khả năng thay thế nguồn.Thƣờng thì nguồn ở đây thƣờng là pin, và khả năng thay thế trong nút mạng là không thế do địa hình triển khai và số nút mạng lớn, do vậy phải chọn nguồn ổn định có khả năng hoạt động phù hợp với yêu cầu của ứng dụng và môi trƣờng hoạt động. 1.3.2 Phần mềm Hệ điều hành nhúng, điều khiển và bảo vệ truy cập tài nguyên và quản lý cho phép phép ngƣời dùng cũng nhƣ hỗ trợ thi hành xử lý và giao tiếp giữa các quá trình. Tuy nhiên chức năng chủ yếu là thi hành lệnh, bởi vậy hệ thống không yêu cầu quá nhiều tài nguyên để hỗ trợ nhƣ một hệ điều hành hoàn thiện. Hơn nữa hệ điều hành cho mạng cảm nhận không dây còn có thể hỗ trợ những tùy chọn cho hê thống, điển hình là quản lý sử dụng năng lƣợng hiệu quả, quản lý và điều khiển các thành phần ngoại vi: cảm biến, thiết bị vô tuyến, định thời. Bởi vậy yêu cầu cho hệ điều hành cho mạng nhúng là cấu trúc đơn giản và hỗ trợ quản lý năng lƣợng mà không tốn nhiều tài nguyên hệ thống nhƣ bộ nhớ và thời gian xử lý. 1.4 Quản lý năng lƣợng của các thiết bị 1.4.1 Chế độ hoạt động và năng lƣợng tiêu thụ Nhƣ các phần trên đã trình bày thì năng lƣợng trong mạng cảm nhận không dây là vấn đề đặc biệt quan trọng bởi vậy điều khiển tiết kiệm năng lƣợng là vấn đề rất đƣợc quan tâm, năng lƣợng tiêu thụ chủ yếu trong hoạt động vi điều khiển, thiết bị vô tuyến, và một phần trong bộ nhớ và phụ thuộc vào kiểu của cảm biến. Chế độ hoạt động của các thành phần của nút mạng trong chế độ tiết kiệm năng lƣợng là rất đƣợc quan tâm trong xây dựng nút mạng, ví dụ với vi điều khiển là chế độ “rỗi” hay “ngủ”, với thiết bị vô tuyến truyền nhận là bật hay tắt chế độ truyền, cảm biến hay bộ nhớ có thể bật hay tắt. 1.4.2 Tiết kiệm năng lƣợng trong vi điều khiển Phụ thuộc chủ yếu vào công nghệ chế tạo của nhà sản xuất và chƣơng trình ứng dụng chạy trên vi điều khiển, bao gồm điều khiển chế độ hoạt động và tốc độ xử lý của vi điều khiển tƣơng ứng với yêu cầu dữ liệu cần xử lý, thuật toán xử lý của ứng dụng cũng giảm đƣợc đáng kể số phép toán cần thực hiện. 1.4.3 Tiết kiệm năng lƣợng trong bộ nhớ Bộ nhớ phổ biến trong mạng cảm nhận thƣờng là Flash hoặc RAM, trên thực tế năng lƣợng tiêu thụ trên bộ nhớ tƣơng ứng với năng lƣợng tiêu thụ trên vi điểu khiển. thời gian đọc dữ liệu và năng lƣợng tiêu thụ tƣơng ứng với loại bộ nhớ, thời gian ghi 8
9. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN và năng lƣợng tiêu thụ lúc ghi thì phức tạp hơn một chút vì nó còn phụ thuộc vào loại dữ liệu. 1.4.4 Tiết kiệm năng lƣợng trong truyền nhận vô tuyến. Đây là hoạt động tiêu tốn nhiều năng lƣợng nhất trong mạng cảm nhận, tƣơng tự nhƣ vi điều khiển truyền nhận vô tuyến cũng có thể hoạt động ở những chế độ khác nhau (bật – tắt) chế độ tắt có thể chiếm đa số thời gian, chỉ hoạt động khi đƣợc kích hoạt do vậy tiết kiệm đáng kể năng lƣợng. Trong chế độ truyền một phần năng lƣợng đƣợc sử dụng để phát sóng vô tuyến, nó phụ thuộc chủ yếu vào loại điều chế, khoảng cách truyền, kĩ thuật lọc, đồng bộ tần số. Tƣơng tự nhƣ chế độ truyền, chế độ nhận cũng có thể chuyển giữa 2 trạng thái tắt - bật, thƣờng thì chế độ truyền và nhận đƣợc sử dụng đan xen nhau, ví dụ trong thí nghiệm của khóa luận này truyền và nhận đƣợc luân phiên nhau, với trạm cơ sở thì chế độ chủ yếu là nhận, còn chế độ truyền chỉ hoạt động khi yêu cầu thủ tục xây dựng lại tuyến hoặc trong thủ tục yêu cầu nhận dữ liệu từ nút cơ sở. 1.4.5 Tiết kiệm năng lƣợng của cảm biến. Đây là vấn đề quan trọng cần đƣợc quan tâm trong tiết kiệm năng lƣợng của mạng không dây bởi sự đa dạng của thiết bị này, việc lựa chọn cảm biến, giao diện kết nối. 1.4.6 Mối liên hệ giữa việc tiền xử lý và truyền – nhận dữ liệu. Sau khi đã có cái nhìn khái quát về năng lƣợng tiêu thụ trên vi xử lý và truyền nhận dữ liệu thì câu hỏi đặt ra là: kết hợp giữa việc xử lý dữ liệu và truyền dữ liệu nhƣ thế nào để tiết kiệm năng lƣợng nhất ? Ví dụ: dữ liệu mà ta nhận đƣợc tại mỗi nút mạng thƣờng ở dạng thô, nếu ta gửi dữ liệu này về trạm gốc mà không xử lý trƣớc thì kích thƣớc dữ liệu này rất lớn, nhƣ vậy sẽ kéo theo một loạt các nút khác cũng phải truyền – nhận một lƣợng dữ liệu lớn dẫn tới tiêu tốn rất nhiều nút này. Kết quả là năng lƣợng tiêu thụ khi truyền dữ liệu chƣa xử lý sẽ lớn hơn rất nhiều năng lƣợng mà nút sử dụng để xử lý dữ liệu thô trƣớc khi truyền đi. Việc lựa chọn có xử lý dữ liệu thô trƣớc khi truyền đi hay không thƣờng dựa trên loại ứng dụng (loại dữ liệu), và kích thƣớc mạng, phƣơng pháp tiền xử lý thƣờng đƣợc sử dụng trong các mạng có kích thƣớc lớn. 1.5 Chế độ hoạt động và tiếp kiệm năng lƣợng Việc đƣa các thành phần vào trạng thái ngủ hay giảm hiệu suất của nút mạng bằng cách lựa chọn phƣơng pháp điều chế và mã hóa để tăng hiệu quả sử dụng năng lƣợng. Quá trình này đƣợc điều khiển bởi hệ điều hành sử dụng ngăn xếp khi chuyển từ trạng thái này sang trạng thái khác, đây đƣợc gọi là bài toán quản lý năng lƣợng động, sự phức tạp trong phƣơng pháp này là phải xem xét năng lƣợng và thời gian để thiết bị chuyển đổi giữa các trạng thái, cải tiến thuật toán dựa trên xác xuất sự kiện xảy ra trong tƣơng lai 1.6 Kiến trúc mạng 9
10. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN 1.6.1 Mô hình mạng 1.6.1.1 Nút cơ sở và nút nguồn Trong phần trƣớc ta có tìm hiểu qua một vài kiểu đối tƣợng giám sát của mạng cảm nhận (theo kiểu phát hiện sự kiện, hoặc theo chu kỳ), chức năng của chúng là phát hiện và gửi dữ liệu tại khu vực mà nó giám sát về nút cơ sở, nơi tập trung và xử lý toàn bộ dữ liệu của các nút khác gửi về, thƣờng có 3 loại nút cơ sở: có thể là một nút trong mạng tƣơng tự nhƣ các nút con khác với loại nút cơ sở này thƣờng nó chỉ dùng để nhận dữ liệu sau đó chuyển tới PC để xử lý, loại nút cơ sở thứ 2 có thể là một thiết bị cầm tay hoặc PDA đƣợc sử dụng để tƣơng tác với mạng cảm nhận, loại thứ 3 là nút cảm nhận có thể đƣợc nối qua gateway để tới một mạng lớn hơn là internet. Hình 1.10: loại nút cơ sở trong mạng WSN Hình 1.11: Kết nối 2 mạng cảm nhận qua kênh truyền trên internet 1.6.1.2 Mạng đơn bƣớc và mạng đa bƣớc. Mạng đơn bƣớc đơn giản là từ nút con ta có thể gửi dữ liệu trực tiếp về nút cơ sở, mạng loại này thƣờng là mạng nhỏ, thông thƣờng trƣờng hợp mạng đơn bƣớc đƣợc coi là một trƣờng hợp đặc biệt của mạng đa bƣớc khi xem xét trên một phạm vi nhỏ. Trong trƣờng hợp trên phạm vi lớn dữ liệu không thể gửi trực tiếp từ nút con về nút cơ sở thì dữ liệu sẽ đƣợc gửi qua các nút trung gian trƣớc khi tới nút cơ sở, ta gọi đây là truyền đa bƣớc. Đôi khi không phải vì không thể truyền trực tiếp từ nút con tới nút cơ sở mà ngƣời ta mới dùng nút trung gian, do dùng nút trung gian để giảm công suất và chia đều tiêu tán năng lƣợng giữa các nút. 10
11. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN Hình 1.12: Mạng đơn bƣớc Hình 1.13: Mạng đa bƣớc Nhƣ vậy các nút con ngoài nhiệm vụ thu nhận dữ liệu còn phải chuyển tiếp dữ liệu về trạm cơ sở. Tuy truyền đa bƣớc có thể giải quyết bài toán về khoảng cách nhƣng lại gặp phải vấn đề là sử dụng năng lƣợng hiệu quả, và xung đột khi có quá nhiều nút có yêu cầu gửi dữ liệu tới một trạm để chuyển tiếp, ví dụ trong một topo mạng phổ biến dạng cây, dạng lƣới thì những nút càng gần trạm gốc thì càng phải chuyển tiếp nhiều gói tin. Để nâng cao hiệu suất trong truyền đa bƣớc thƣờng ngƣời ta can thiệp bằng thuật toán định tuyến, hoặc dựa trên việc nút truyển tiếp lƣu và xử lý nhiều gói tin thành một khung dữ liệu mới trƣớc khi chuyển tiếp đi. 1.6.2 Hai cấu trúc cơ bản của mạng cảm nhận không dây 1.6.2.1 Cấu trúc phẳng Trong cấu trúc phẳng (flat architecture) , 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 sink qua multihop 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 sink 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ố 1.6.2.2 Cấu trúc tầng Trong cấu trúc tầng (tiered architecture) , các cụm đƣợc tạo ra giúp các tài nguyên trong cùng một cụm gửi dữ liệu single hop hay multihop ( tùy thuộc vào kích cỡ của cụm) đến một nút định sẵn, thƣờng gọi là nút chủ (cluster head). 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 tầng 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 . Cấp 0: Cảm nhận ;Cấp 1 : Tính toán ;Cấp 2: Phân phối Mạng cảm biến xây dựng theo cấu trúc tầng hoạt động hiệu quả hơn cấu trúc phẳng, do các lý do sau: 11
12. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN + Cấu trúc tầng có thể giảm chi phí cho 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 tầng sẽ có tuổi thọ cao hơn cấu trúc 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 tầng 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. + Vềđộ tin cậy: mỗi mạng cảm biến phải phù hợp với với số lƣợng các nút yêu cầu thỏa mãn điều kiện về băng thông và thời gian sống. Với mạng cấu trúc phẳng kích cỡ mạng tăng thì thông lƣơng của mỗi nút giảm + Việc nghiên cứu các mạng cấu trúc tầng đem lại nhiều triển vọng để khắc phục vấn đề kích cỡ mạng tăng thì thông lƣơng của mỗi nút giảm. Một cách tiếp cận là dùng một kênh đơn lẻ trong cấu trúc phân cấp, trong đó các nút ở cấp thấp hơn tạo thành một cụm xung quanh trạm gốc. Mỗi một trạm gốc đóng vai trò là cầu nối với cấp cao hơn, cấp này đảm bảo việc giao tiếp trong cụm thông qua các bộ phận hữu tuyến. Trong trƣờng hợp này, dung lƣợng của mạng tăng tuyến tính với số lƣợng các cụm, với điều kiện là số lƣợng các cụm tăng ít nhất phải nhanh bằng n . Các nghiên cứu khác đã thử cách dùng các kênh khác nhau ở các mức khác nhau của cấu trúc phân cấp. Trong trƣờng hợp này, dung lƣợng của mỗi lớp trong cấu trúc tầng và dung lƣợng của mỗi cụm trong mỗi lớp xác định là độc lập với nhau. Tóm lại, việc tƣơng thích giữa các chức năng trong mạng có thể đạt đƣợc khi dùng cấu trúc tầng. Đặc biệt ngƣời ta đang tập trung nghiên cứu về các tiện ích về tìm địa chỉ. Những chức năng nhƣ vậy có thể phân phối đến mọi nút, một phần phân bố đến tập con của các nút. Giả thiết rằng các nút đều không cốđịnh và phải thay đổi địa chỉ một cách định kì, sự cân bằng giữa những lựa chọn này phụ thuộc vào tân số thích hợp của chức năng cập nhật và tìm kiếm. Hiện nay cũng đang có rất nhiều mô hình tìm kiếm địa chỉ trong mạng cấu trúc tầng. 1.6.3 Mục tiêu thiết kế mạng cảm nhận và tiêu chí đánh giá 1.6.3.1 Chất lƣợng dịch vụ Mạng cảm nhận không dây về cơ bản khác với những mạng khác về tiêu chí đánh giá chất lƣợng dịch vụ của mạng, thông thƣờng với các mạng khác thì tiêu chí đánh giá hoạt động của mạng thƣờng là độ trễ, tỉ lệ mất gói, Nhƣng với mạng cảm nhận không dây thì để đánh giá chất lƣợng của dịch vụ còn phải quan tâm tới đặc điểm ứng dụng mà nó đƣợc triển khai, một vài đặc điểm cần quan tâm khi đánh giá là: xác suất báo cáo theo tỉ lệ thông tin đƣợc quan tâm, phát hiện sự kiện chậm, báo cáo sai 1.6.3.2 Hiệu quả năng lƣợng 12
13. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN Ở những phần trên ta đã nhắc lại rất nhiều lần vấn đề năng lƣợng trong hoạt động của mạng cảm nhận không dây, điều đó cho thấy năng lƣợng là vấn đề sống còn của mạng này năng lƣợng tiêu thụ tại mỗi nút còn ảnh hƣởng tới thời gian sống, và cấu hình ổn định của mạng, bởi vậy năng lƣợng là mục tiêu quan trọng để thiết kế trong mạng cảm nhận. Trong một vài giao thức định tuyến thì năng lƣợng đƣợc xem nhƣ là một thông số quan trọng việc lựa chọn giao thức định tuyến phù hợp, trong một vài giao thức năng lƣợng còn đƣợc sử dụng nhƣ một thông số quyết định tới định tuyến. Thông thƣờng việc định nghĩa hiệu quả năng lƣợng trong mạng cảm nhận có rất nhiều cách khác nhau: năng lƣợng trên từng bít nhận đƣợc, năng lƣợng trên mỗi báo cáo, thời gian sống của mạng hoặc số gói tin mà nút có thể gửi đi. 1.6.3.3 Khả năng bảo trì và thay thế Khả năng bảo trì và thay thế nút trong mạng cảm nhận tỉ lệ nghịch với kích thƣớc của mạng đó. Thông thƣờng thì số nút mạng có thể lên tới hàng nghìn nút, tuy nhiên do yêu cầu của ứng dụng đôi khi việc thay thế là hết sức cần thiết, lúc đó cần phải dựa vào thông tin nhận đƣợc và bảng định tuyến để xác định nút mạng bị hỏng, thƣờng mạng loại này các nút đƣợc triển khai thủ công và địa chỉ hóa. 1.6.3.4 Tiềm lực của hệ thống Là thông số liên quan giữa chất lƣợng dịch vụ và khả năng tự cấu hình lại khi topo mạng thay đổi đã đề cập ở những phần trƣớc, mạng cảm nhận không dây tỏ ra khá hiệu quả, mạng vẫn hoạt động tốt nếu chỉ có vài nút mạng hết năng lƣợng, môi trƣờng thay đổi, hoặc đƣờng liên kết vô tuyến đã bị chiếm thƣờng có thể vƣợt qua ,nó có thể tìm tuyến khác, việc này dựa trên giao thức định tuyến đƣợc xây dựng. trong mạng 1.6.3.5 Xử lý trong mạng Khi tổ chức mạng theo mô hình phát tán, một nút trong mạng chuyển tiếp nút hoặc thi hành các chƣơng trình. Đây là một dạng xử lý đặc biệt trong mạng, một vài kĩ thuật cho xử lý trong mạng, trong đó một kĩ thuật thƣờng đƣợc sử dụng là kĩ thuật kết hợp , kĩ thuật này khai thác đặc điểm của mạng không dây là nút cơ sở nhận dữ liệu theo chu kỳ từ các nút cảm biến, nhƣng chỉ quan tâm tới những nút có thông số thay đổi, trong trƣờng hợp nhƣ vậy không cần thiết phải chuyển tất cả dữ liệu từ nút về trạm cơ sở. Một kĩ thuật khác mà ta đã từng đề cập trong một phần trƣớc đây là kĩ thuật tiền xử lý bằng biến đổi fourier nhanh, nhằm giảm kích thƣớc dữ liệu trong mạng lớn. 1.6.3.6 Kĩ thuật khai thác thông tin vị trí Một kĩ thuật hữu ích khác là sử dụng thông tin vị trí trong giao thức truyền thông khi biểu diễn thông tin, khi đó vị trí của sự kiện xảy ra là thông tin quan trọng trong rất nhiều ứng dụng. 1.6.3.7 Kĩ thuật lấy mẫu tích cực Kĩ thuật lấy mẫu tích cực trong mạng cảm nhận dựa trên một đặc điểm của mạng này là tốc độ dữ liệu trung bình trong một khoảng thời gian lớn là rất nhỏ do có thể có rất ít sự kiện cần phải báo cáo, khi có một sự kiện xảy ra nó có thể đƣợc phát hiện bởi nhiều cảm biến quanh đó, gây ra tình trạng lƣu lƣợng mạng tại đó tăng đột biến, bởi 13
14. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN vậy nguyên lý của kĩ thuật này là điều khiển luồng lƣu lƣợng bằng việc chuyển đổi giữa chế độ không hoạt động và chế độ tích cực. 1.6.3.8 Kĩ thuật khai thác tính hỗn độn Liên quan tới kĩ thuật lấy mẫu tích cực là kĩ thuật khai thác tính hỗn độn trong mạng cảm nhận, kĩ thuật này dựa trên thực tế là khi khởi đầu thì trạng thái năng lƣợng của các nút gần nhƣ đồng đều, tuy nhiên sẽ có những nút hoạt động nhiều hơn các nút khác ( ví dụ nhƣ các nút tổng hợp dữ liệu trƣớc khi gửi tới trạm cơ sở), những nút đặc biệt này (thƣờng có bộ nhớ dữ liệu hoặc bộ xử lý mạnh hơn các nút thông thƣờng) có thể bổ xung năng lƣợng cho nó từ môi trƣờng hoặc một giải pháp khác là phân công nhiệm vụ lần lƣợt cho từng nút để cân bằng năng lƣợng tiêu thụ giữa các nút 1.7 Mô hình phân lớp trong mạng WSN Mô hình phân lớp của mạng cảm nhận không dây bao gồm các lớp: Lớp ứng dụng, lớp vận chuyển, lớp mạng, lớp liên kết dữ liệu và lớp vật lý. Trong đó lớp vận chuyển đảm bảo luồng dữ liệu khi lớp ứng dụng yêu cầu, lớp mạng hỗ trợ định tuyến cho lớp vận chuyển trong truyền dữ liệu đa bƣớc, thủ tục thâm nhập môi trƣờng của lớp liên kết dữ liệu nhằm hạn chế xung đột với các nút hàng xóm, cuối cùng lớp vật lý đảm nhận truyền nhận gói tin một cách hiệu quả. Trong nội dung của khóa luận này chỉ tìm hiểu về 3 lớp dƣới cùng trong mô hình phân lớp của mạng WSN, đó là lớp vật lý, lớp liên kết dữ liệu với thủ tục thâm nhập môi trƣờng nhằm phục vụ cho việc tìm hiểu giao thức định tuyến trong lớp mạng sẽ đƣợc trình bày ở chƣơng 2. Hình 1.14: Mô hình phân lớp trong mạng WSN 1.7.1 Lớp vật lý Phần này trình bày về lớp vật lý trong mạng WSN, đảm nhận chức năng môi trƣờng truyền tin, các kết nối vật lý, cơ khí, điện, điều chế giải điều chế, mã hóa, chế độ truyền dữ liệu, loại tín hiệu truyền tin. Và những khái niệm cơ bản trong truyền thông số qua kênh vô tuyến để có cái nhìn rõ hơn về lớp vật lý và kênh truyền. 1.7.1.1 Giới thiệu chung Trong mạng cảm nhận thách thức chủ yếu là xây dựng đƣợc mô hình kiến trúc truyền nhận đơn giản, giá thành rẻ, nhƣng vẫn phải đủ hiệu quả để đáp ứng đƣợc yêu cầu dịch vụ của ứng dụng đƣợc triển khai. 14
15. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN 1.7.1.2 Nền tảng của truyền thông và kênh truyền Trong kênh truyền vô tuyến sóng điện từ lan truyên tự do giữa trạm thu và phát, bởi vậy kênh vô tuyến là môi trƣờng truyền chung không chỉ cho mạng cảm nhận mà cho nhiều ứng dụng khác, nhƣ di động, phát thanh truyền hình a. Phân chia tần số Việc lựa chọn tần số sử dụng là rất quan trọng trong thiết kế hệ thống. Ngoại trừ công nghệ băng rộng hầu hết các hệ thống vô tuyến hoạt động với tần số dƣới 6GHz, Dải truyền thông vô tuyến dải tần sử dụng thƣờng từ VLF tới EHF. Việc lựa chọn hệ tần số nhằm tránh nhiễu giữa ngƣời dùng và các hệ thống khác nhau, một vài dải tần đƣợc dành riêng cho một vài hệ thống đặc biệt, ở châu âu GSM có thể hoạt động ở dải tần GSM 900 (880 – 915 MHz) và GSM 1800 (1710 – 1785) MHz. Bên cạnh đó ITU còn quy định dải tần miễn phí dành cho công nghiệp, nghiên cứu khoa học và Y học gọi tắt là ISM nghĩa là với dải tần này đƣợc tùy ý sử dụng mà không cần sự cho phép của chính phủ, bởi vậy nó rất phổ biến không chỉ cho mạng cảm nhận mà trong cả các công nghệ không dây khác, ví dụ dải tần 2.4 GHz ISM đƣợc sử dụng trong IEEE 802.11, Bluetooth và IEEE 802.15.4 VLF = Tần số cực thấp LF = Tần số thấp MF = Tần số trung bình HF = Tần số cao VHF = Tần số rất cao UHF = Tần số cực cao SHF = Tần số siêu cao EHF = Tần số cực kỳ cao b. Điều chế và giải điều chế Trong tính toán truyền thông số nó thao tác trên dữ liệu số do linh hoạt trong xử lý tín hiệu số và tỉ số giữa tín hiệu trên tạp cao. Về cơ bản tín hiệu số là một chuỗi kí tự thƣờng là bit, nhóm kí tự này đƣợc ánh xạ tƣơng ứng với một số dạng sóng có chiều dài giới hạn, độ dài này gọi là thời gian ký tự. Khi đề cập tới tốc độ dữ liệu trong truyền nhận hoặc điều chế ta cần phân biệt những thông số sau: + Tốc độ ký tự đƣợc định nghĩa bằng nghịch đảo của thời gian ký tự, trong điều chế bit nó còn gọi là tốc độ bit + Tốc độ dữ liệu là số bít đƣợc truyền đi trong một giây. Quá trình điều chế thực hiện tại bên truyền, bên nhận muốn khôi phục lại ký tự từ dạng sóng nhận đƣợc cần phải ánh xạ dạng sóng nhận đƣợc tới ký tự tƣơng ứng, bƣớc này đƣợc gọi là giải điều chế. Do tín hiệu có thể bị sai lệch đi trong quá trình truyền nên ta có khái niệm tốc độ lỗi ký tự và tốc độ lỗi bít. Thông thƣờng trƣớc khi dữ liệu đƣợc đƣa vào bộ điều chế số nó đƣợc mã hóa để dễ dàng cho việc khôi phục tín hiệu nhịp tại đầu thu. Trong phần thử nghiệm sử dụng nút mạng CC1010EB của Chipcon hỗ trợ mã hóa dữ liệu NRZ và Manchester. Một số kĩ thuật điều chế số: 15
16. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN Hình 1.15: Khóa dịch biên độ ASK Hình 1.16: Khóa dịch pha PSK Hình 1.17: Khóa dịch tần số FSK c. Hiệu quả của truyền sóng và ồn Khi truyền từ trạm phát tới trạm thu tín hiệu có thể bị méo do tác động của môi trƣờng truyền hoặc do lỗi của bộ thu trong quá trình giải mã và điều chế. Những thông số cơ bản cần quan tâm khi đánh giá hiệu quả của kênh truyền vô tuyến là sự phản xạ, giao thoa, suy yếu trên đƣờng truyền, ồn và lỗi tƣơng quan d. Truyền gói và đồng bộ Lớp liên kết dữ liệu sử dụng cấu trúc gói hoặc khung nhƣ là đơn vị truyền nhận cơ bản, trạm phát thực hiện xử lý điều chế và giải điều chế. Trạm thu cần phải biết chắc chắn thuộc tính của dạng sóng tới để có thể phát hiện ra khung tới bao gồm tần số, 16
17. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN pha, bit hoặc ký tự bắt đầu hoặc kết thúc khung. Do đó nó phải đồng bộ giữa sóng mang và đồng hồ hệ thống. e. Chất lƣợng của kênh vô tuyến Khác với kênh có dây, kênh truyền vô tuyến thƣờng có chất lƣợng kém, tốc độ lỗi bit/ký tự cao. Trên thực tế chất lƣợng của kênh truyền phụ thuộc vào rất nhiều thông số bao gồm: tần số, khoảng cách truyền, tốc độ truyền, môi trƣờng, công nghệ sử dụng 1.7.1.3 Lớp vật lý và thiết kế truyền thông Một vài đặc điểm quan trọng của lớp vật lý trong mạng cảm nhận là: + Tiêu thụ năng lƣợng thấp + Truyền công suất thấp tƣơng ứng với khoảng cách truyền ngắn. + Phần cứng có thể hoạt động trong chế độ tiết kiệm năng lƣợng. + Tốc độ dữ liệu thấp từ vài chục tới vài trăm kilobits trên giây + Cấu tạo đơn giản và giá thành rẻ + Có khả năng chịu đựng sự thay đổi của môi trƣờng cao 1.7.2 Lớp liên kết dữ liệu và thủ tục thâm nhập môi trƣờng Đây là phần khá quan trọng liên quan nhiều tới phần sau của khóa luận này nên ta sẽ tìm hiểu chi tiết hơn các phần khác, do nó có liên quan tới giao thức định tuyến sẽ tìm hiểu ở chƣơng sau. Thủ tục thâm nhập môi trƣờng thực hiện nhiệm vụ điều khiển nút khi thâm nhập môi trƣờng truyền vô tuyến, phần này tìm hiểu nền tảng của thủ tục thâm nhập môi trƣờng, những yêu cầu và các vấn đề cơ bản mà thủ tục thâm nhập môi trƣờng gặp phải trong mạng cảm nhận không dây. 1.7.2.1 Nền tảng của thủ tục thâm nhập môi trƣờng a. Yêu cầu và tiêu chí thiết kế thủ tục thâm nhập môi trƣờng Mục đích của thủ tục thâm nhập môi trƣờng là truyền gói tin một cách hiệu quả, ổn định. Xung đột có thể xảy ra nếu nhƣ giao thức thâm nhập môi trƣờng cho phép 2 hay nhiều nút gửi dữ liệu tại cùng một thời điểm, xung đột có thể là nguyên nhân làm cho trạm thu không thể nhận dữ liệu chính xác. Hoạt động và hiệu suất của thủ tục thâm nhập môi trƣờng phụ thuộc khá nhiều vào lớp vật lý, hơn nữa mạng WSN cũng gặp phải những vấn đề mà mạng không dây đó là: tốc độ lỗi, mất tuyến, sự suy giảm trên đƣờng truyền, cách thức điều chế, tần số sử dụng và khoảng cách giữa trạm thu, phát. Trong phƣơng pháp tránh xung đột CSMA (đa truy cập cảm nhận sóng mang), mỗi nút nghe ngóng môi trƣờng truyền trƣớc khi truyền dữ liệu đi. Nếu nhƣ môi trƣờng đang bận nó sẽ hoãn việc gửi gói tin lại để tránh xung đột và yêu cầu truyền lại. 17
18. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN Hình 1.18 Mô hình vùng xung đột giữa các nút mạng Ví dụ giả sử nút A bắt đầu truyền dữ liệu cho nút B, một lát sau nút C cũng quyết định truyền dữ liệu cho nút B, bởi vì C không nhận thấy nút A đang hoạt động khi C bắt đầu truyền, dữ liệu xung đột tại B và cả 2 gói dữ liệu đều không sử dụng đƣợc, bởi vậy sử dụng phƣơng pháp CSMA trong trƣờng hợp này vẫn không tránh đƣợc xung đột, đây gọi là hiện tƣợng ẩn nút trong mạng cảm nhận, hiện tƣợng này chỉ đƣợc khắc phục bởi giao thức định tuyến phân cấp của lớp mạng sẽ đƣợc trình bày ở phần sau. Một ví dụ khác thể hiện nhƣợc điểm của phƣơng pháp này là: giả sử B truyền dữ liệu cho A, một lát sau C muốn truyền dữ liệu cho D, tuy nhiên C nhận thấy B đang hoạt động nên sẽ chờ, mặc dù C vẫn có thể gửi dữ liệu cho D mà không ảnh hƣởng gì tới dữ liệu nhận đƣợc tại A. Trong môi trƣờng có dây ví dụ nhƣ mạng ethernet khi trạm gửi tín hiệu, nếu phát hiện xung đột tại đầu thu nó lập tức dừng việc gửi tín hiệu lại, đặc điểm này gọi là phát hiện xung đột (CD – collision detection) nhờ vào phát hiện sự thay đổi điện thế trên đƣờng truyền, tuy nhiên phƣơng pháp này không thƣờng đƣợc sử dụng trong môi trƣờng không dây do việc truyền nhận trong môi trƣờng vô tuyến trong mạng cảm nhận thƣờng là bán song công, nghĩa là chỉ sử dụng một kênh truyền tại một thời điểm nó chỉ gửi hoặc nhận tín hiệu, do đó khi có xung đột rồi thì vẫn không tránh đƣợc. Một đặc điểm khác khi thiết kế thủ tục thâm nhập môi trƣờng là lƣu lƣợng luồng dữ liệu trong mạng, ví dụ với loại đối tƣợng giám sát theo chu kỳ thì lƣu lƣợng mạng thấp, nút chủ yếu ở chế độ nghỉ, tuy nhiên với loại đối tƣợng giám sát sự kiện, ví dụ nhiệt độ trong rừng thì bài toán trở nên khá phức tạp, vì bình thƣờng lƣu lƣợng mạng rất ít, nhƣng taị khu vực xảy ra cháy, lƣu lƣợng mạng tăng đột biến. b. Một số thủ tục thâm nhập môi trƣờng điển hình Thủ tục thâm nhập môi trƣờng về cơ bản nó đƣợc chia ra 3 loại: thủ tục phân chia cố định, thủ tục phân chia theo yêu cầu, và thủ tục truy cập ngẫu nhiên. + Thủ tục phân chia cố định: tài nguyên đƣợc phân chia cho từng nút mà không sợ xung đột. khi đó kênh truyền sẽ đƣợc phân chia theo thời gian (TDMA), theo tần số (FDMA), theo mã CDMA. + Thủ tục phân chia theo yêu cầu, cho phép các nút sử dụng tài nguyên khi có yêu cầu sử dụng, thủ tục này có thể chia thành thủ tục tập trung và thủ tục phân tán, trong thủ tục điều khiển tập trung nút sẽ gửi yêu cầu tới nút trung tâm và chờ trả lời, trong trƣờng hợp đƣợc phép nó sẽ gửi một bản tin xác nhận đƣợc phép tới nút đã gửi yêu cầu cùng với thông tin tài nguyên nó đƣợc phép sử dụng, ví dụ nhƣ số lƣợng và vị trí của các khe thời gian trong hệ thống TDMA. Trong trƣờng hợp này nút trung tâm thƣờng tốn nhiều năng lƣợng, bởi vậy trong giao thức này thƣờng thì năng lƣợng của những nút trung tâm đƣợc cung cấp nhiều hơn các nút thông thƣờng. Trong giao thức 18
19. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN phân tán gần tƣơng tự nhƣ thẻ bài trong token bus. Khung token sẽ lần lƣợt lƣu hành trong một vòng kín là một nhóm các nút mạng, một chƣơng trình quản lý vòng đặc biệt dùng để phát hiện lỗi và tái tạo thẻ bài khi xảy ra sự cố, nhƣợc điểm của nó là các nút phải ở trong tình trạng nhận dữ liệu, thêm vào đó việc bào trì và duy trì tuyến khi hình dáng mạng thay đổi là khá phức tạp. + Thủ tục truy cập ngẫu nhiên các nút hoạt động phân tán hoàn toàn, phƣơng pháp đầu tiên và tới giờ vẫn đƣợc sử dụng là ALOHA, trong thủ tục ALOHA một nút khi truyền dữ liệu nó gửi đi ngay lập tức, không hề có sự liên hệ với các nút khác bởi vậy khả năng xảy ra xung đột là rất cao, khi phát hiện xung đột phía nhận sẽ gửi một xác nhận cho thuộc tính của gói tin nhận, phía gửi sẽ chờ một thời gian ngẫu nhiên và bắt đầu truyền lại. c. Thủ tục thâm nhập môi trƣờng trong mạng cảm nhận Trong mạng cảm nhận không dây yêu cầu đầu tiên và quan trọng nhất là cân bằng năng lƣợng giữa các nút mạng, sử dụng năng lƣợng hiệu quả trong thiết kế, lựa chọn thủ tục thâm nhập môi trƣờng và khả năng thiết lập lại tuyến khi topo mạng thay đổi. - Nhƣ đã tìm hiểu ở những phần trƣớc năng lƣợng của nút tiêu thụ chủ yếu do truyền hoặc nhận dữ liệu. thông thƣờng quá trình truyền thông gồm 4 trạng thái: truyền, nhận, rỗi và chế độ ngủ. trong đó chế độ truyền và nhận là tốn nhiều năng lƣợng nhất, dựa vào hoạt động của giao thức thâm nhập môi trƣờng ta có thể nhận thấy một số vấn đề và mục tiêu thiết kế của giao thức MAC: + Xung đột: khi xảy ra xung đột thì vừa tốn năng lƣợng tại cả nơi nhận và nơi thu và năng lƣợng dùng để phát lại gói tin đó, bởi vậy cần phải loại bỏ xung đột, tuy nhiên nếu có thể đảm bảo lƣu lƣợng của mạng cảm nhận đủ thấp thì xung đột gần nhƣ đƣợc bỏ qua. + Nghe ngóng: mặc dù khung Unicast gửi từ một nguồn tới mục đích, tuy nhiên vì kênh vô tuyến là môi trƣờng chúng cho tất cả các nút hàng xóm của nó bởi vậy chúng đều nhận đƣợc các nút đó và bỏ qua nếu nó không phải là đích tới, việc này cũng tốn khá nhiều năng lƣợng. Tuy nhiên đôi khi việc này là hết sức cần thiết khi thu thập thông tin về háng xóm để xác định lƣu lƣợng hiện tại hỗ trợ cho mục đích quản lý. + Nghe ngóng ở chế độ rỗi: khi một nút ở trạng thái rỗi nó sẵn sàng nhận dữ liệu, tuy nhiên trong những mạng lƣu lƣợng ít thì thời gian chờ nhận dữ liệu tốn khá nhiều năng lƣợng. + Một thông số quan trọng nữa ngoài năng lƣợng ra là yêu cầu chƣơng trình không phức tạp, xử dụng ít tài nguyên nhƣ bộ nhớ, vi xử lý Thủ tục thâm nhập môi trƣờng của mạng cảm nhận thƣờng đƣợc chia vào 2 nhóm thủ tục chính là: thủ tục cạnh tranh, và thủ tục lập lịch. 1.7.2.2 Thủ tục cạnh tranh Trong thủ tục cạnh tranh, cơ hội truyền dữ liệu chia đều cho tất cả các nút hàng xóm. Nếu chỉ có một nút hàng xóm cần truyền dữ liệu thì không vấn đề gì, tuy nhiên nếu có 2 hoặc nhiều nút muốn truyền khi đó chúng phải cạnh tranh với nhau để giành quyền truyền dữ liệu, 2 giao thức quan trọng của nhóm giao thức này là ALOHA và CSMA mà ta đã có dịp đề cập ở phần trƣớc. * Thủ tục CSMA: Trong thủ tục đa truy cập cảm nhận sóng mang tránh xung đột CSMA – CA(Carrier Sense Multiple Access with Collision Avoidance) Một vấn đề 19
20. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN gặp phải với đối tƣợng giám sát theo sự kiện, bình thƣờng thì nút mạng ở trạng thái rỗi trong một thời gian dài, nó chỉ bắt đầu hoạt động khi có sự kiện bên ngoài tác động, khi sự kiện đó xảy ra gần nhƣ tất cả các nút đều muốn truyền dữ liệu một cách đồng thời, do vậy sẽ tạo ra nhiều xung đột, nếu nút cố gắng gửi dữ liệu theo chu kỳ thì khả năng lặp lại xung đột là rất cao nếu không có quá trình thăm dò xảy ra. Sau đây ta sẽ tìm hiểu nguyên lý làm việc cơ bản của giao thức đa truy cập cảm nhận sóng mang này. Ban đầu khi một nút nhận gói dữ liệu mới để truyền đi, nó chờ một thời gian trễ ngẫu nhiên, mục đích của việc làm này nhằm làm giảm tính đồng bộ của các nút khi phát hiện sự kiện sảy ra (vì nếu khi 2 nút xảy ra xung đột mà trong lần thử tiếp theo nếu có cùng thời gian chờ thì vẫn không tránh khỏi xung đột), trong thời gian chờ ngẫu nhiên đó nút có thể đặt ở trạng thái ngủ, trong thời gian nghe ngóng nút sẽ thực hiện cảm nhận sóng mang. Nếu nhƣ môi trƣờng truyền đang bận, sau một số lần thử mà vẫn không thành công nó sẽ dừng lại và chờ một thời gian ngẫu nhiên, phụ thuộc vào số lần thử và thời gian ngủ của nút, sau đó nó lại tiếp tục nghe ngóng môi trƣờng, cứ nhƣ vậy khi tới một giới hạn nào đó mà vẫn không thành công thì gói sẽ bị bỏ qua. Trong trƣờng hợp môi trƣờng rỗi, nút sẽ gửi bản tin RTS và chuyển sang trạng thái chờ, trong trƣờng hợp không nhận đƣợc bản tin CTS, hoặc chỉ có bản tin CTS cho nút khác thì nó sẽ quay lại quá trình chờ một thời gian ngẫu nhiên và thử lại. Còn nếu nhận đƣợc bản tin CTS, nó sẽ gửi dữ liệu đi và chờ bản tin ACK. Tùy từng trƣờng hợp mà CSMA có thể thay đổi thời gian chờ, thời gian nghe ngóng là ngẫu nhiên hay cố định. Một điều cần lƣu ý là cần phân biệt thủ tục CSMA – CA trong mạng không dây và thủ tục CSMA – trong mạng có dây, về cơ bản thì 2 thì tục này giống nhau là đều dựa vào việc cảm nhận sóng mang, tuy nhiên thủ tục truy cập CSMA – CA chỉ đƣợc gọi là tránh xung đột, do nó không thể phát hiện khi có xung đột xảy ra, do chế độ truyền là bán song công, nút mạng tại một thời điểm chỉ có thể thu hoặc phát dữ liệu. Do vậy trong lập trình định tuyến sử dụng thủ tục thâm nhập môi trƣờng này thƣờng sử dụng một thời gian trễ ngẫu nhiên để giảm tính đồng bộ giữa các nút, nhằm tăng hiệu quả tránh xung đột. Thiết bị duy trì ba thông số NB, CW và BE, trong đó NB đếm số thời điểm rút lui, CW chỉ ra kích thƣớc của cửa sổ xung đột hiện tại, BE là số mũ của thời điểm rút lui hiện tại. Khi có một gói dữ liệu để truyền đi, các thông số này đƣợc khởi tạo tƣơng ứng với: NB=0, CW=2 và BE=macMinBE (trong đó macMinBE là thông số của giao thức). Thiết bị sẽ chờ ngẫu nhiên trong r thời điểm rút lui tiếp theo trong khoảng [0, 2be – 1] , khi đó nó thực hiện cảm nhận sóng mang, nếu môi trƣờng rỗi nó sẽ giảm CW, và chờ tới thời điểm rút lui tiếp theo và xem xét lại môi trƣờng truyền một lần nữa, nếu môi trƣờng vẫn rỗi thì thiết bị sẽ bắt đầu truyền dữ liệu của nó. Trong trƣờng hợp phát hiện ra môi trƣờng đang bận thì số thời điểm rỗi NB và số mũ BE tăng lên và CW đƣợc đặt lại CW=2, nếu NB vƣợt quá ngƣỡng thì khung dữ liệu đƣợc bỏ qua, quá trình truyền thất bại. Cứ nhƣ vậy các bƣớc đƣợc lặp lại. 1.7.2.3 Thủ tục xếp lịch Ƣu điểm của thủ tục này là xắp xếp quá trình truyền tại các nút hàng xóm để không xảy ra xung đột tại đầu thu. Tuy nhiên nó cũng có một vài nhƣợc điểm đó là phức tạp trong thiết đặt và bảo trì việc sắp xếp, lập lịch. (kĩ thuật đa truy cập phân chia theo thời gian TDMA thƣờng đƣợc sử dụng với loại thủ tục thâm nhập môi trƣờng này) 20
21. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN a. Thủ tục LEACH Hình 1.19: Thủ tục LEACH Thủ tục này thƣờng đƣợc sử dụng trong mạng mà các nút có năng lƣợng tiêu thụ nhƣ nhau. Nó phân vùng các nút thành các liên cung, mỗi liên cung đó sẽ chọn ra một nút gọi là nút chính sẽ thực hiện việc xắp xếp và bảo trì thông tin của các nút trong liên cung, các nút còn lại trong liên cung đó gọi là các nút thành viên đƣợc gán vào khe thời gian tƣơng ứng để trao đổi dữ liệu với nút chính. Nút chính sẽ tập hợp dữ liệu trong cluster lại gửi trực tiếp hoặc qua nút trung gian để truyền dữ liệu về trạm cơ sở. Nhƣ vậy năng lƣợng tiêu thụ trong mạng này là bất đối xứng, nút chính sẽ tiêu tốn nhiều năng lƣợng hơn các nút thành viên, do ngoài việc gửi dữ liệu về trạm cớ sở nó còn thực hiện chức năng liên lạc và điều khiển hoạt động của các nút thành viên. Trong khi năng lƣợng tiêu thụ tại các nút thành viên sẽ đƣợc tiết kiệm rất nhiều do khoảng cách với nút chính gần hơn rất nhiều so với trạm cơ sở. để khắc phục tình trạng tiêu thụ năng lƣợng bất cân đối nhƣ vậy có thể cứ sau một khoảng thời gian thì các nút này tự đánh giá năng lƣợng và thay đổi nút chính luân phiên. b. Thủ tục SMACS Thủ tục tự tổ chức điều khiển truy cập môi trƣờng SMACS về bản chất là sự kết hợp giữa việc khám phá các nút lân cận và phân chia TDMA cho các nút đó, giao thức này đƣợc xây dựng dựa trên một số giả thiết: + Dải tần sử dụng đƣợc chia thành nhiều kênh nhỏ và nút có thể sử dụng để trao đổi với bất kỳ nút khác. + Tất cả các nút trong mạng cảm nhận là cố định. + Các nút chia các khung dữ liệu có độ dài cố định, không cần thiết là tất cả các nút đều giống nhau. Mục đích của SMACS là phát hiện ra các nút hàng xóm và thiết lập liên kết hoặc kênh truyền tới nút đó, trong đó dữ liệu chạy theo một chiều, nếu 2 nút đều muốn truyền dữ liệu cho nhau thì phải sử dụng 2 kênh liên kết. việc này sẽ đảm bảo tránh đƣợc xung đột. Giả sử nút x muốn thiết đặt một liên kết để trao đổi dữ liệu với nút y, nó sẽ nghe ngóng dải tần cố định trong một khoảng thời gian ngẫu nhiên, nếu không nhận đƣợc gì trong thời gian đó, nó sẽ gửi một bản tin mời gửi dữ liệu rồi thông báo tới các nút hàng xóm. Khi nút hàng xóm z nhận đƣợc bản tin mời của x nó sẽ chờ một thời gian ngẫu nhiên và trả lời chứa địa chỉ của nó, địa chỉ của nút mời và số hàng xóm n, khi x nhận đƣợc bản tin trả lời của nút y, nó sẽ mời y thiết lập liên kết. y sẽ trả lời bằng bản tin chứa thông tin về khe thời gian và tần số sử dụng. Giao thức này cho phép thiết đặt liên kết cố định giữa các nút cố định, do đó việc khám phá thông tin về các nút hàng xóm đƣợc thực hiện liên tục để tƣơng thích khi cấu hình mạng thay đổi. Hạn chế của thủ tục này là phức tạp trong xử lý giữa các nút, 21
22. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN do vậy khi lựa chọn thủ tục này cần cân nhắc giữa tổng năng lƣợng cần khi thực hiện thủ tục và truyền nhận dữ liệu so với các phƣơng pháp khác, ƣu điểm của phƣơng pháp này nhƣ các thủ tục xếp lịch khác là tránh xung đột tốt. c. thủ tục tƣơng thích lƣu lƣợng truy cập môi trƣờng Thủ tục TRAMA thực hiện việc phân công cho phép các nút truy cập kênh truyền để tránh xung đột, giao thức này giả sử tất cả các nút đều đồng bộ thời gian và chia thời gian thời gian đƣợc chia thành thời điểm truy cập ngẫu nhiên. Một nút sẽ quảng bá thông tin của nó tới các nút hàng xóm, bao gồm cả thông tin về lập lịch của nó. Dựa và các thông tin này các nút sẽ sử dụng thuật toán phân tán để xác định khe thời gian và kế hoạch thâm nhập để truyền - nhận dữ liệu và kế hoạch chuyển sang trạng thái ngủ của nó. Nhƣợc điểm của thủ tục này khá nặng về tính toán và bộ nhớ bởi vậy yêu cầu mạng có tài nguyên đủ lớn. Hình 1.20: Thủ tục TRAMA 1.7.2.4 Chuẩn thủ tục thâm nhập môi trƣờng IEEE 802.15.4 Phạm vi ứng dụng của thủ tục IEEE 802.15.4 đƣợc triển khai cho mạng cảm nhận không dây, mạng trong nhà, kết nối thiết bị với PC và bảo mật hầu hết những ứng dụng này yêu cầu tốc độ thấp, không đòi hỏi quá cao về độ trễ, đặc biệt năng lƣợng tiêu thụ thấp. a. Kiến trúc mạng vai trò và kiểu nút mạng Trên lớp mạng có 2 kiểu nút: Nút đa năng, nghĩa là nó có thể hoạt động đảm nhiệm vai trò của nhiều chức năng khác nhau, kiểu nút thứ 2 là nút có chức năng giới hạn nó chỉ có thể hoạt động nhƣ một thiết bị. Một thiết bị phải liên kết với nút điều khiển, trong mạng hình sao thiết bị điều khiển có thể hoạt động dựa trên liên kết 1-1, hoặc đa liên kết nhƣ trong mạng cá nhân. Một thiết bị điều hành thƣờng thực hiện nhứng nhiệm vụ sau: + Nó quản lý những thiết bị liên kết với nó. + Cấp địa chỉ cho những thiết bị đó, tất cả các nút IEEE 802.15.4 có 64 bit địa chỉ, địa chỉ này cũng có thể ngắn hơn tùy theo yêu cầu của ứng dụng + Trong chế độ báo hiệu IEEE 802.15.4 nó phát một khung bao hiệu thông báo cho các nút, và thiết bị điều hành có thể xử lý những yêu cầu của các nút trong các khe thời gian đƣợc chỉ ra trong tín hiệu thông báo. + Nó trao đổi dữ liệu với các thiết bị ngang hàng với nó b. Cấu trúc siêu khung 22
23. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN Hình 1.21 Cấu trúc siêu khung Trạm điều hành trong mạng hình sao khi hoạt động ở chế độ thông báo nó tổ chức kênh truy cập và truyền dữ liệu. Mọi siêu khung đều có độ dài nhƣ nhau, trạm điều hành bắt đầu mỗi siêu khung bằng cách gửi một khung dữ liệu cảnh báo, khung cảnh báo này sẽ chứa dữ liệu mô tả thông tin độ dài và những thông tin liên quan khác ở những siêu khung tiếp theo. + Một siêu khung đƣợc chia thành 2 khoảng: hoạt động và không hoạt động. Trong thời gian không hoạt động, tất cả các nút bao gồm cả nút điều khiển sẽ ở trạng thái ngủ, khi thời gian không hoạt động kết thúc nó lập tức bị đánh thức để nhận thông tin thông báo từ nút điều hành, thời gian không hoạt động này cũng có thể đƣợc bỏ qua. + Thời gian hoạt động đƣợc chia thành 16 khe, khe đầu tiên là khung cảnh báo, những khung còn lại đƣợc chia thành 2 vùng, thời điểm cạnh tranh truy cập sau đó là các khe thời gian “đảm bảo”. Độ dài của thời gian hoạt động và không hoạt động cũng nhƣ độ dài của mỗi khe và số khe thời gian có thể điều chỉnh đƣợc bằng chƣơng trình. Nút điều hành hoạt động trong toàn bộ thời gian hoạt động, nó liên lạc với các thiết bị hoạt động trong khe thời gian đảm bảo khi đƣợc phép. Trong hầu hết khe thời gian đảm bảo nó có thể chuyển sang chế độ ngủ. Trong khoảng thời gian cạnh tranh truy cập, thiết bị có thể tắt chế độ truyền nhận nếu không có dữ liệu để truyền. c. Quản lý thời gian đảm bảo Nút điều hành sẽ phân khe thời gian đảm bảo cho thiết bị khi có yêu cầu trong khoảng thời gian cạnh tranh, một cờ đƣợc sử dụng để chỉ ra khe thời gian yêu cầu là khe nhận hay truyền dữ liệu. Trong khe truyền dữ liệu thiết bị sẽ truyền gói tới nút điều hành và ngƣợc lại trong trƣờng hợp là khe nhận. Khi nhận đƣợc gói tin yêu cầu ngay lập tức nó sẽ gửi gói tin ACK thông báo rằng nó đã nhận đƣợc yêu cầu, khi nút điều hành đủ tài nguyên nó sẽ phân khoảng thời gian bảo hành cho nút, nó sẽ chèn thông tin mô tả về khoảng thời gian bảo hành trong khung thông báo tiếp theo, phần thông tin mô tả về thời gian bảo hành nó sẽ chỉ ra địa chỉ của nút gửi yêu cầu, số lƣợng và vị trí của khe thời gian trong khe thời gian bảo hành trong siêu khung. Và thiết bị có thể sử dụng khe thời gian đƣợc phân đó. Nếu không đủ tài nguyên nó sẽ gửi một thông báo là khe thời gian đã hết, khi đó thiết bị sẽ chờ gửi lại yêu cầu vào lần sau. d. Thủ tục truyền dữ liệu 23
24. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN Giả sử thiết bị có dữ liệu muốn gửi tới nút điều hành, nếu nhƣ thiết bị đã đƣợc phân khe thời gian đảm bảo, nó sẽ hoạt động trƣớc khi khe thời gian bắt đầu và ngay lập tức truyền dữ liệu mà không hề có thao tác thăm dò tránh xung đột. Trong trƣờng hợp thiết bị chƣa đƣợc phân khe thời gian nó sẽ gửi gói dữ liệu tại thời điểm cạnh tranh truy cập sử dụng giao thức đa truy cập cảm nhận sóng mang, sau đó nút điều hành gửi ACK. Trong trƣờng hợp dữ liệu truyền từ nút điều hành tới thiết bị, nếu thiết bị đã đƣợc phân trong khe thời gian đảm bảo thì dữ liệu sẽ đƣợc truyền ngay lập tức mà không cần yêu cầu xác nhận. Trong trƣờng hợp phổ biến nhất khi nút điều hành không thể sử dụng để nhận trong khoảng thời gian đảm bảo, thì một thủ tục bắt tay đƣợc thực hiện giữa thiết bị và trạm điều hành, trạm điều hành sẽ gửi một thông báo vùng đệm dữ liệu cho thiết bị bao gồm cả địa chỉ của thiết bị trong trƣờng địa chỉ của khung thông báo. Trong thực tế khi thiết bị tìm thấy địa chỉ của nó trong trƣờng địa chỉ nó sẽ gửi một gói dữ liệu yêu cầu đặc biệt trong khoảng thời gian cạnh tranh. Trạm điều hành sẽ trả lời bằng bản tin ACK và sắn sàng nhận dữ liệu tới. Trong trƣờng hợp không gửi thành công thiết bị sẽ gửi lại yêu cầu trong những siêu khung tiếp theo. e. Khe thời gian trong giao thức đa truy cập cảm nhận sóng mang Khi một nút gửi dữ liệu hoặc thông tin quản lý, điều khiển đi trong khoảng thời gian cạnh tranh truy cập nó sử dụng giao thức đa truy cập cảm nhận sóng mang, để giảm xác suất xung đột giao thức đa truy cập cảm nhận sóng mang tránh xung đột (CSMA –CA) sử dụng một thời gian trễ ngẫu nhiên. Khe thời gian trong gian đoạn cạnh tranh truy cập đƣợc chia thành các khe thời gian nhỏ hơn, gọi là thời điểm rút lui, tƣơng ứng với độ dài của khoảng 20 kênh và khe thời gian trong giao thức CSMA – CA tƣơng ứng với thời điểm rút lui. f. Chế độ không cảnh báo Bên canh chế độ cảnh báo trong IEEE 802.15.4 còn đề suất giao thức chế độ không cảnh báo, một vài điểm khác nhau cơ bản giữa 2 chế độ này là: + Trong chế độ không cảnh báo trạm điều hành không gửi khung cảnh báo, sự vắng mặt của gói tin cảnh báo đƣợc thiết bị tận dụng trong khoảng thời gian này để đồng bộ với trạm điều hành. + Mọi gói gửi từ thiết bị không sử dụng khe CSMA – CA. do không có đồng bộ trong thời điểm rút lui, thêm vào đó thiết bị chỉ thi hành duy nhất một lần thăm dò môi trƣờng, nếu kênh rỗi thì quá trình thâm nhập thành công. + Trạm điều hành phải hoạt động theo chu kỳ nhƣng thiết bị thì có thể hoạt động theo lập lịch của riêng nó, nó chỉ hoạt động khi, có gói dữ liệu hoặc gói điều khiển cần gửi đi hoặc có dữ liệu đƣợc gửi tới chính nó từ trạm điều khiển. 24
25. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN CHƢƠNG II: Phân tuyến trong mạng WSN 2.1. Giới thiệu Mặc dù mạng cảm biến có khá nhiều điểm tƣơng đồng so với các mạng ad hoc có dây và không dây nhƣng chúng cũng biểu lộ một số các đặc tính duy nhất mà tạo cho chúng tồn tại thành mạng riêng. Chính những đặc tính này làm cho tập trung mũi nhọn vào yêu cầu thiết kế các giao thức phân tuyến mới mà khác xa so với các giao thức phân tuyến trong các mạng ad hoc có dây và không dây. Việc nhằm vào đặc tính này đã đƣa ra một tập các thách thức lớn và riêng đối với WSN.Chƣơng này sẽ trình bày ba loại giao thức định tuyến chính hay đƣợc dùng trong mạng cảm biến, đó là : + Phân tuyến trung tâm dữ liệu (data - centric protocol). + Phân tuyến phân cấp (hierarchical protocol). + Phân tuyến dựa vào vị trí (location - based protocol). 2.2. Thách thức trong vấn đề phân tuyến Chính vì những đặc điểm riêng biệt của mạng cảm biến mà việc phân tuyến trong mạng cảm biến phải đối mặt với rất nhiều thách thức sau: + Mạng cảm biến có một số lƣợng lớn các nút, cho nên ta không thể xây dựng đƣợc sơ đồ địa chỉ toàn cầu cho việc triển khai số lƣợng lớn các nút đó vì lƣợng mào đầu để duy trì ID quá cao. + Dữ liệu trong mạng cảm biến yêu cầu cảm nhận từ nhiều nguồn khác nhau và truyền đến sink. + Các nút cảm biến bị rang buộc khá chặt chẽ về mặt năng lƣợng, tốc độ xử lý, lƣu trữ. + Hầu hết trong các ứng dụng mạng cảm biến các nút nói chung là tĩnh sau khi đƣợc triển khai ngoại trừ một vài nút có thể di động. + Mạng cảm biến là những ứng dụng riêng biệt + Việc nhận biết vị trí là vấn đề rất quan trọng vì việc tập hợp dữ liệu thông thƣờng dựa trên vị trí. + Khả năng dƣ thừa dữ liệu rất cao vì các nút cảm biến thu lƣợm dữ liệu dựa trên hiện tƣợng chung. 2.3. Các vấn đề về thiết kế giao thức phân tuyến Mục đích chính của mạng cảm biến là truyền thông dữ liệu trong mạng trong khi cố gắng kéo dài thời gian sống của mạng và ngăn chặn việc giảm các kết nối bằng cách đƣa ra những kỹ thuật quản lý năng lƣợng linh hoạt. Trong khi thiết kế các giao thức phân tuyến, chúng ta thƣờng gặp phải các vấn đề sau. 2.3.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 hang trăm, thậm chí hang ngàn nút 25
26. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN đƣợc triển khai tùy ý và thông thƣờng không bị giám sát bao phủ một vùng rộng lớn. Trong mạng này, đặc tính của các con cảm biến là có tính thích nghi động và cao, nhƣ là nhu 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.3.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 mutilhop chính là nguồn tiêu thụ năng lƣợng chính trong mạng. Để giảm việc tiêu thụ năng lƣợng có thể đạt đƣợc bằng cách điều khiển tự động chu kỳ công suất 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.3.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 sink. Mô hình này phụ thuộc nhiều vào bản chất của ứng dụng trong đó cái cách dữ liệu đƣợc yêu cầu và sử dụng. 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 đa dạng các ứng dụng. Một loại các ứng dụng của mạng cảm biến yêu cầu mô hình thu thập dữ liệu mà 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 chụp 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 sink. 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à sink. Nhu cầu hỗ trợ đa dạng các mô hình dữ liệu làm tăng tính phức tạp của vấn đề thiết kế giao thức phân tuyến. 2.3.4. Cách truyền dữ liệu Cái cách mà các truy vấn và dữ liệu đƣợc truyền giữa các trạm cơ sở 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 cơ sở. Tuy nhiên phƣơng pháp dựa trên bƣớc nhảy đơn (singlehop) có chi phí rất đắt và các nút mà xa trạm cơ sở 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 cơ sở có thể đƣợc thực hiện bằng việc sử dụng truyền gói đa bƣớc nhảy (mutilhop) 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. Dữ liệu đƣợc truyền giữa các nút cảm biến và các sink Để đáp ứng các truy vấn từ các sink 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 cơ sở thông qua nhiều đƣờng dẫn mutilhop. Trong định tuyến mutilhop 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 26
27. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN 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 phân 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 phân 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.4. Phân loại và so sánh các giao thức phân tuyến Vấn đề phân tuyến trong mạng cảm biến là một thách thức khó khăn đòi hỏi phải cân bằng giữa sự đáp ứng nhanh của mạng và hiệu quả. Sự cân bằng này yêu cầu sự cần thiết thích hợp khả năng tính toán và truyền dẫn của các nút cảm biến ngƣợc với mào đầu yêu cầu thích ứng với điều kiện này. Trong mạng cảm biến không dây, mào đầu đƣợc đo chính là lƣợng băng thông đƣợc sử dụng, tiêu thụ công suất và yêu cầu xử lý của các nút di động. Việc tìm ra chiến lƣợc cân bằng giữa sự cạnh tranh này cần thiết tạo ra một nền tảng chiến lƣợc phân tuyến . Việc thiết kế các giao thức phân tuyến trong mạng cảm biến không dây phải xem xét giới hạn về : + Công suất và tài nguyên của mỗi nút mạng. + Chất lƣợng thay đổi theo thời gian của các kênh vô tuyến. + Khả năng mất gói và trễ. Nhằm vào các yêu cầu thiết kế này một số các chiến lƣợc phân tuyến trong mạng cảm biến đƣợc đƣa ra. Bảng (2.1) đƣa ra sự phân loại một số giao thức dựa trên nhiều tiêu chí khác nhau, nói chung việc phân tuyến trong WSN có thể đƣợc chia thành : + Loại thứ nhất giao thức phân tuyến thông qua kiến trúc phẳng ( hay còn gọi là giao thức phân tuyến ngang hàng ) trong đó các nút có vai trò nhƣ nhau. Kiến trúc phẳng có một vài lợi ích bao gồm số lƣợng mào đầu tối thiểu để duy trì cơ sở hạ tầng, và có khả năng khám phá ra nhiều đƣờng giữa các nút truyền dẫn để chống lại lỗi và tất cả các nút thƣờng có vai trò hoặc chức năng nhƣ nhau. + Loại thứ 2 là phân cấp theo cụm, lợi dụng cấu trúc của mạng để đạt đƣợc hiệu quả về năng lƣợng, sự ổn định, sự mở rộng. Trong loại giao thức này các nút mạng tự tổ chức thành các cụm trong đó một nút có mức năng lƣợng cao hơn các nút khác và đóng vai trò là nút chủ. Nút chủ thực hiện phối hợp hoạt động trong cụm và chuyển tiếp thông tin giữa các cụm với nhau. Việc tạo thành các cụm có khả năng làm giảm tiêu thụ năng lƣợng và kéo dài thời gian sống của mạng. + Loại giao thức phân tuyến thứ 3 là giao thức phân tuyến dựa theo vị trí tùy thuộc vào cấu trúc mạng. Trong đó vị trí của các nút cảm biến đƣợc sử dụng để phân tuyến số liệu Một giao thức phân tuyến đƣợc coi là thích ứng nếu các tham số của hệ thống có thể điều khiển đƣợc để thích ứng với các trạng thái mạng hiện tại và các mức năng lƣợng khả dụng. Những giao thức này cũng có thể đƣợc chia thành các giao thức phân tuyến đa đƣờng, yêu cầu, hỏi/đáp, liên kết hoặc dựa vào QoS tuỳ theo cơ chế hoạt động của giao thức. Ngoài ra, các giao thức phân tuyến có thể đƣợc chia thành ba loại 27
28. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN là chủ động, tƣơng tác hoặc lai ghép tuỳ thuộc vào cách thức mà nguồn tìm đƣờng tới đích. Trong các giao thức chủ động, tất cả các đƣờng đƣợc tính toán trƣớc khi có yêu cầu, trong khi đối với các giao thức tƣơng tác thì các đƣờng đƣợc tính toán theo yêu cầu. Các giao thức lai ghép kết hợp cả hai quy tắc ở trên. Khi các nút cảm biến cố định, nó thích hợp với các giao thức phân tuyến theo bảng hơn là với các giao thức tƣơng tác. Một lƣợng công suất đáng kể đƣợc sử dụng để tìm đƣờng và thiết lập các giao thức tƣơng tác. Một số giao thức khác dựa vào định thời và thông tin vị trí. Để khái quát, có thể sử dụng phân loại theo cấu trúc mạng và cơ chế hoạt động của giao thức (tiêu chuẩn phân tuyến) . Việc phân loại và so sánh các giao thức phân tuyến trong WSN đƣợc chỉ ra trong hình 2.1 và bảng 1. Hình 2.1 Phân loại giao thức phân tuyến trong WSN 28
29. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN Bảng1: Phân loại và so sánh các giao thức phân tuyến trong mạng WSN 2.4.1 Giao thức phân tuyến ngang hàng Các loại giao thức phân tuyến đầu tiên là giao thức phân tuyến ngang hàng. Trong giao thức phân tuyến ngang hàng các nút có vai trò nhƣ nhau và các nút cảm biến cộng tác với nhau để thực hiện nhiệm vụ cảm biến. Do số lƣợng các nút lớn lên, nó không khả thi để chỉ định một định dạng toàn cầu cho mỗi nút. Điều này xem xét đã dẫn đến trung tâm dƣc liệu phân tuyến nơi mà những BS(các nút cơ sở) gửi truy vấn đến một số vùng và chờ đợi dữ liệu từ vị trí cảm biến trong vùng đƣợc lựa chọn. Từ các dữ liệu đƣợc yêu cầu truy vấn thông qua, dựa trên thuộc tính đặt tên là cần thiết để xác định thành phần dữ liệu. 2.4.1.1 Flooding và Gossiping Flooding là kỹ thuật chung thƣờng đƣợc sử dụng để tìm ra đƣờng và truyền thông tin trong mạng adhoc vô tuyến và hữu tuyến. Chiến lƣợc phân tuyến này rất đơn giản và không phụ thuộc vào cấu hình mạng và các giải thuật phân tuyến phức tạp. Flood sử dụng phƣơng pháp reactive nhờ đó mỗi nút nhận dữ liệu hoặc điều khiển dữ liệu để gửi các gói tới các nút lân cận. Sau khi truyền, một gói sẽ đƣợc truyền trên tất cả các đƣờng có thể. Trừ khi mạng bị ngắt không thì các gói sẽ truyền đến đích (hình 3.2) Hình 2.2 Truyền gói trong Flooding Hơn nữa khi cấu hình mạng thay đổi các gói sẽ truyền theo những tuyến mới giải thuật này sẽ tạo ra vô hạn các bản sao của mỗi gói khi đi qua các nút. Giải thuật này có 3 nhựơc điểm lớn nhƣ sau: + Thứ nhất là hiện tƣợng bản tin kép, tức là các gói dữ liệu giống nhau đƣợc gửi đến cùng nút. + Thứ hai là hiện tƣợng chồng chéo, tức là các nút cùng cảm nhận một vùng không gian và do đó tạo ra các gói tƣơng tự nhau gửi dữ liệu đến các nút lân cận. + Thứ ba đó là thuật toán này không hề quan tâm đến vấn đề năng lƣợng của các nút, các nút sẽ nhanh chóng tiêu hao năng lƣợng và làm giảm thời gian sống của mạng. Một sự cải tiến của giao thức này là Gossiping, thuật toán này cải tiến ở chỗ mỗi nút sẽ ngẫu nhiên gửi gói mà nó nhận đƣợc đến một trong các nút lân cận của nó. Thuật toán này làm giảm số lƣợng các gói lan truyền trong mạng, tránh hiện tƣợng 29
30. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN bản tin kép tuy nhiên có nhƣợc điểm là có thể gói sẽ không bao giờ đến đƣợc đích. 2.4.1.2 Giao thức tự thƣơng lƣợng SPIN SPIN ( Sensor Protocol for Information via Negotiation)là giao thức phân tuyến thông tin dựa trên sự dàn xếp dữ liệu. Mục tiêu chính của giao thức này đó là tập trung việc quan sát môi trƣờng có hiệu quả bằng một số các nút cảm biến riêng biệt trong toàn bộ mạng. Nguyên lý của giao thức này đó là sự thích ứng về tài nguyên và sắp xếp dữ liệu. Ý nghĩa của việc dàn xếp dữ liệu (data negotiation) này là các nút trong SPIN sẽ biết về nội dung của dữ liệu trƣớc khi bất kỳ dữ liệu nào đƣợc truyền trong mạng . SPIN khai thác tên dữ liệu nhờ đó mà các nút sẽ kết hợp miêu tả dữ liệu (metadata) với dữ liệu mà chúng tạo ra và sử dụng sự miêu tả này để thực hiện việc giàn xếp dữ liệu trƣớc khi truyền dữ liệu thực tế. Nơi nhận dữ liệu có thể bày tỏ mối quan tâm đến nội dung dữ liệu bằng cách gửi yêu cầu để lấy đƣợc dữ liệu quảng bá. Điều này tạo ra sự sắp xếp dữ liệu để đảm bảo rằng dữ liệu chỉ đƣợc truyền đến nút quan tâm đến loại dữ liệu này. Do đó mà loại trừ khả năng bản tin kép và giảm thiểu đáng kể việc truyền dữ liệu dƣ thừa qua mạng. Hơn nữa việc sử dụng bộ miêu tả dữ liệu cũng loại trừ khả năng chồng lấn vì các nút có thể chỉ giới hạn về tên lọai dữ liệu mà chúng quan tâm đến. Việc thích ứng tài nguyên cho phép các nút cảm biến chạy SPIN có thể thích ứng với trạng thái hiện tại của tài nguyên năng lƣợng. Mỗi nút có thể dò tìm tới bộ quản lý để theo dõi mức tiêu thụ năng lƣợng của mình trƣớc khi truyền hoặc xử lý dữ liệu. Khi mức năng lƣợng còn lại thấp các nút này có thể giảm hoặc loại bỏ một số hoạt động nhƣ là truyền miêu tả dữ liệu hoặc các gói. Chính việc thích nghi với tài nguyên làm tăng thời gian sống của mạng. Để thực hiện truyền và sắp xếp dữ liệu các nút sử dụng giao thức này sử dụng ba loại bản tin (hình 2.3). Hoạt động của SPIN gồm 6 bƣớc nhƣ hình sau: Hình 2.3 Hoạt động của SPIN + Bƣớc 1: ADV để thông báo dữ liệu mới tới các nút. + Bƣớc 2: REQ để yêu cầu dữ liệu cần quan tâm. Sau khi nhận đƣợc ADV các nút quan tâm đến dữ liệu này sẽ gửi REQ để yêu cầu lấy dữ liệu. 30
31. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN + Bƣớc 3: bản tin DATA bản tin này thực sự chứa dữ liệu đƣợc cảm biến và kèm theo mào đầu miêu tả dữ liệu. + Bƣớc 4, sau khi nút này nh ận dữ liệu nó sẽ chia sẻ dữ liệu của nó cho các nút còn lại trong mạng bằng việc phát bản tin ADV chứa miêu tả dữ liệu (metadata). + Bƣớc 5: sau đó các nút xung quanh lại gửi bản tin REQ yêu cầu dữ liệu. + Bƣớc 6 là DATA lại đƣợc truyền đến các nút mà yêu cầu dữ liệu này. Tuy nhiên giao thức SPIN cũng có hạn chế khi mà nút trung gian không quan tâm đến dữ liệu nào đó, khi đó dữ liệu không thể đến đƣợc đích. Giao thức SPIN đƣợc chia thành các loại : * SPIN – PP : Giao thức này đƣợc thiết kế cho truyền thông điểm điểm, giả sử nhƣ 2 nút có thể giao tiếp với nhau mà không ảnh hƣởng tới truyền thông của các nút khác. Khi nút có dữ liệu để gửi nó sẽ gửi ADV tới nút hàng xóm, nếu nút nào muốn nhận thông tin đó nó sẽ trả lời bằng bản tin REG. Khi đó nút vừa gửi bản tin ADV sẽ gửi gói dữ liệu tới nút vừa gửi bản tin REG. Và quá trình cứ tiếp diễn nhƣ vậy. * SPIN – EC : Giao thức này là sự bổ xung thêm thủ tục xác định năng lƣợng so với giao thức trƣớc. Một nút chỉ tham gia quá trình nếu nhƣ nó có thể thực hiện các giai đoạn của giao thức mà năng lƣợng không xuống dƣới ngƣỡng cho phép. * SPIN BC : Giao thức này dùng cho kênh quảng bá, ƣu điểm của giao thức này là mọi nút hàng xóm đều nhận đƣợc bản tin quảng bá còn nhƣợc điểm của nó là các nút sẽ ngừng truyền nếu nhƣ kênh đó đã đƣợc sử dụng. Một điểm khác của giao thức này với các giao thức trƣớc đó là các nút sẽ không lập tức gửi bản tin trả lời REQ ngay sau khi nhận đƣợc gói tin ADV, mỗi nút sẽ sử dụng mội thời gian trễ ngẫu nhiên rồi mới gửi gói tin REQ đi. 2.4.1.3 Giao thức gán tuyến liên tiếp SAR (Sequential Assignment Routing) Giao thức gán tuyến liên tiếp xem xét năng lƣợng và chất lƣợng dịch vụ trên mỗi tuyến và mức độ ƣu tiên của gói tin để quyết định. Mỗi nút sẽ duy trì nhiều tuyến tới trạm cơ sơ cùng một lúc để tránh tình trạng quá tải hoặc một tuyến liên kết bị lỗi. Số tuyến này đƣợc xây dựng bằng cách xây dựng cây mạng tại các nút kề trạm cơ sở, cây đƣợc mở rộng bằng cách thêm vào các nút lá hoặc nút nhánh kế tiếp và bỏ qua những nút có chất lƣợng dịch vụ hoặc năng lƣợng thấp. Nhƣ vậy mỗi nút sẽ kết hợp 2 thông số, chất lƣợng dịch vụ và năng lƣợng trong mỗi tuyến, trong đó năng lƣợng đƣợc xác định bằng số gói tối đa có thể định tuyến mà không cần thay thế năng lƣợng nếu nhƣ vẫn sử dụng tuyến đó. Giao thức SAR tính toán thông số chất lƣợng dịch vụ, năng lƣợng tiêu thụ và mức ƣu tiên của gói tin, Một thủ tục xây dựng lại tuyến đƣợc khởi phát bởi nút cở sở để kịp thích ứng khi topo mạng thay đổi, việc phục hồi lại lỗi đƣợc thực hiện bằng thủ tục bắt tay giữa các nút hàng xóm với nhau. 2.4.1.4 Giao thức khuếch tán trực tiếp (Dirrected Diffusion) Dirrected Diffusion trong mô hình tập trung dữ liệu data centric (DC), nó sẽ tập trung tổng hợp dữ liệu để sử dụng năng lƣợng một cách hiệu quả, nghĩa là nó sẽ kết hợp dữ liệu từ những nút khác nhau để loại bỏ thông tin dƣ thừa nhằm tối ƣu hóa số gói tin phải gửi, bởi vậy sẽ tiết kiệm đƣợc năng lƣợng cho toàn mạng. Trong mô hình phân tuyến tập trung địa chỉ address centric (AC) chỉ chỉ cần tìm đƣờng đi ngắn nhất tới nút cơ sở. Trong mô hình tập trung dữ liệu, dữ liệu đƣợc tập trung ở một nút trƣớc khi gửi về nút cơ sở, còn trong mô hình tập trung địa chỉ thì các nút gửi dữ liệu độc lập theo tuyến ngắn nhất về nút gốc. 31
32. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN 2.4.1.5 Giao thức chuyển tiếp giá tối thiểu (MCFA) MCFA là thuật toán đƣợc lựa chọn trong phần thực nghiệm truyền nhận nhiệt, do vậy phần này sẽ tìm hiểu chi tiết hơn các thuật toán khác. Đây là thuật toán đầu tiên đƣợc tìm ra trong nhóm giao thức phân tuyến công bằng trong mạng tích cực, Thuật toán này dựa trên thực tế chiều của luồng dữ liệu trong mạng là đơn hƣớng luôn hƣớng về trạm cơ sở, do vậy nó không đòi hỏi các nút phải xây dựng và duy trì bảng định tuyến để truyền tiếp dữ liệu. Thay vào đó mỗi nút sẽ xác định giá tối thiểu từ nó tới trạm cơ sở. 2.4.2 Nhóm giao thức phân cấp Lợi dụng cấu trúc của mạng để đạt đƣợc hiệu quả về năng lƣợng, sự ổn định, sự mở rộng. Trong loại giao thức này các nút mạng tự tổ chức thành các cụm trong đó một nút có mức năng lƣợng cao hơn các nút khác và đóng vai trò là nút chủ. Nút chủ thực hiện phối hợp hoạt động trong cụm và chuyển tiếp thông tin giữa các cụm với nhau. Việc tạo thành các cụm có khả năng làm giảm tiêu thụ năng lƣợng và kéo dài thời gian sống của mạng. 2.4.2.1 Giao thức phân tuyến phân cấp tƣơng thích nang lƣợng thấp LEACH(Low Energy Adaptive Clustering Hierachy) là một giao thức sử dụng năng lƣợng rất hiệu quả trong mạng cảm nhận. tác giả của phƣơng pháp này khẳng định nó nâng thời gian sống của mạng lên tới 8 lần so với một số phƣơng pháp phân tuyến khác. Để đạt đƣợc mục tiêu này LEACH đã thông qua mô hình phân cấp để tổ chức mạng thành các cụm, mỗi cụm đƣợc quản lý bởi nút chủ. Nút chủ gánh lấy trọng trách thực hiện nhiều tác vụ. Đầu tiên là thu lƣợm dữ liệu theo chu kỳ từ các nút thành viên, trong quá trình tập trung dữ liệu nút chủ sẽ cố gắng tập hợp dữ liệu để giảm dƣ thừa về những dữ liệu tƣơng quan nhau. Nhiệm vụ thứ hai đó là nút chủ sẽ trƣợc tiếp truyền dữ liệu đã đƣợc tập hợp lại đến các trạm cơ sở. Việc truyền này có thể thực hiện theo kiểu single hop. Nhiệm vụ thứ ba là LEACH sẽ tạo ra một mô hình ghép kênh theo thời gian TDMA, mỗi nút trong cụm sẽ đƣợc gán một khe thời gian mà có thể sử dụng để truyền tin. Một thuật toán đƣợc sử dụng để chọn ra nút chính, ban đầu mỗi nút tự xác định xem nó có thể làm nút chính hay không (dựa vào đánh giá năng lƣợng của chính nó), nếu nó quyết định trở thành nút chính nó sẽ thông báo cho các nút hàng xóm của nó, các nút không trở thành nút chính sẽ tham gia vào một nhóm dựa trên thông báo mà nó nhận đƣợc. LEACH là giao thức đƣợc dùng trong mạng cảm nhận mà các nút là cố định có vai trò bình đẳng, dựa trên giả thiết các nút luôn có dữ liệu để gửi, các nút thu thập dữ liệu môi trƣờng liên tiếp do đó tốc độ dữ liệu là cố định. Do các nút chính đƣợc thay đổi liên tục nên nhìn chung năng lƣợng tiêu thụ trên các nút là khá cân bằng. 32
33. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN Hình 2.7: Mô hình Leach Các nút chủ sẽ quảng bá mô hình TDMA cho các nút thành viên trong cụm của nó. Để giảm thiểu khả năng xung đột giữa các nút cảm biến trong và ngoài cụm, LEACH sử dụng mô hình truy cập đa phân chia theo mã CDMA. 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. Pha thiết lập bao gồm hai bƣớc là lựa chọn nút chủ và thông tin về cụm. Pha ổn định trạng thái gồm thu lƣợm dữ liệu, tập trung dữ liệu và truyền dữ liệu đến các trạm cơ sở. Thời gian của bƣớc ổn định kéo dài hơn so với thời gian của bƣớc thiết lập để giảm thiểu mào đầu. Giao thức LEACH sử dụng bƣớc phân nhóm trƣớc khi truyền dữ liệu. Một nút cảm biến đƣợc chọn làm nút chủ nhóm và sẽ truyền tất cả số liệu của các nút cảm biến thuộc nhóm đó tới nút gốc. Đây là điểm khác biệt so với các phƣơng pháp thông thƣờng mà mỗi nút cảm biến sẽ truyền trực tiếp tới nút gốc. 2.4.2.2 Giao thức Giao thức ngƣỡng năng lƣợng hiệu quả TEEN (Threshold Sensitive Energy Efficient Sensor Network) dựa trên việc phân loại mạng cảm nhận thành 2 nhóm: dạng tích cực và dạng thụ động, trong mạng tích cực thì thông số môi trƣờng đƣợc theo dõi một cách liên tục do đó tốc độ dữ liệu là cố định. Trong trƣờng hợp nút thụ động nghĩa là chỉ có dữ liệu truyền khi có sự quan tâm sảy ra, do vậy lƣợng dữ liệu truyền là không cân bằng, giao thức TEEN đƣợc thiết kế cho loại nút mạng này. Giao thức TEEN sử dụng 2 thông số do ngƣời thiết kế mạng quyết định, đó là ngƣỡng cứng và ngƣỡng mềm. Khi giá trị giám sát vƣợt quá ngƣỡng cứng lần đầu tiên nó lƣu lại và gửi dữ liệu đi, việc lựa chọn ngƣỡng cứng liên quan tới giá trị dữ liệu mạng quan tâm. sau đó nếu giá trị theo dõi vƣợt qua ngƣỡng mà giá trị ngƣỡng cứng cộng với ngƣỡng mềm thì dữ liệu mới đƣợc truyền đi, việc này nhằm tránh gửi lại những gói tin mà giá trị không có sự thay đổi lớn so với đối tƣợng dữ liệu cần theo dõi. Hạn chế của giao thức này là trong trƣờng hợp không vƣợt ngƣỡng nút không bao giờ gửi dữ liệu về mạng. 2.4.2.3 PEGASIS (Power-Efficient Gathering in Sensor Information Systems) PEGASIS phân cấp là một họ các giao thức phân tuyến và tập trung thông tin trong mạng cảm biến. 33
34. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN Giao thức này đầu tiên hỗ trợ việc kéo dài thời gian sống của mạng nhờ đạt đƣợc việc tiêu thụ năng lƣợng đồng nhất và hiệu suất năng lƣợng cao qua tất cả các nút trong mạng, thứ hai làm giảm trễ truyền dữ liệu đến sink. Giao thức này xem xét mô hình mạng bao gồm tập hợp các nút đồng nhất đƣợc triển khai qua một vùng địa lý. Các nút này có sự hiểu biết về vị trí các nút khác trong toàn mạng và chúng còn có khả năng điều khiển công suất và bao phủ một vùng tùy ý.Các nút này cũng đƣợc trang bị bộ thu phát sóng hỗ trợ CDMA. Trách nhiệm của các nút này là thu lƣợm và truyền dữ liệu đến các sink, thông thƣờng là các trạm cơ sở. Mục đích để phát triển một cấu trúc phân tuyến và một sơ đồ tập trung dữ liệu để giảm thiểu sự tiêu thụ công suất và truyền dữ liệu đƣợc tập trung đến trạm cơ sở với trễ truyền dẫn nhỏ nhất trong khi vẫn cân bằng sự tiêu thụ công suất giữa các nút trong mạng. Giải thuật này sử dụng mô hình cấu trúc dạng chuỗi. Dựa trên mô hình này các nút sẽ giao tiếp với nút hàng xóm gần nó nhất. Cấu trúc chuỗi bắt đầu với nút xa sink nhất, các nút mạng đƣợc thêm dần vào chuỗi làm chuỗi lớn dần lên, bắt đầu từ nút hàng xóm gần nút cuối nhất. Các nút sẽ đƣợc gán vào chuỗi theo cách greedy từ nút lân cận gần nhất cho tới các nút còn lại trong mạng. Để xác định đƣợc nút lân cận gần nhất mỗi nút sẽ sử dụng cƣờng độ tín hiệu để đo khoảng cách tới các nút lân cận của nó. Sử dụng dữ kiện này các nút sẽ điều chỉnh cƣờng độ tín hiệu sao cho chỉ có nút lân cận gần nhất nghe đƣợc. Một nút trong chuỗi sẽ đƣợc trọn làm nút chủ, trách nhiệm của nút chủ là truyền dữ liệu tập hợp đƣợc tới trạm cơ sở. Vai trò nút chủ sẽ bị dịch chuyển vị trí trong chuỗi sau mỗi vòng chu kỳ. Chu kỳ này đƣợc quản lý bởi sink và việc chuyển trạng thái từ vòng này đến vòng tiếp theo có thể đƣợc khởi tạo bởi việc đƣa ra dấu hiệu công suất cao bởi sink. Việc quay vòng nút chủ trong chuỗi nhằm đảm bảo công bằng trong tiêu thụ năng lƣợng giữa các nút trong mạng. Tuy nhiên cũng cần chú ý rằng việc thay đổi có khi dẫn đến nút chủ rời xa trạm cơ sở, sink, khi đó nút này lại cần yêu cầu công suất cao để truyền đến trạm cơ sở. Việc tập trung dữ liệu trong mạng dọc theo chuỗi. Đầu tiên chain leader sẽ gửi một thẻ bài tới nút cuối cùng bên phải cuối chuỗi. Trong khi nhận đƣợc tín hiệu này nút cuối sẽ gởi dữ liệu nó thu lƣợm đƣợc đến nút lân cận theo chiều xuôi trong chuỗi, sau đó nút này tập trung dữ liệu và lại tiếp tục gửi đến nút lân cận gần nó nhất, cứ nhƣ vậy cho đến khi gửi đến nút chủ. Sau đó nút chủ sẽ lại tập trung dữ liệu và gửi đến sink. Mặc dù đơn giản nhƣng mô hình tập trung dạng chuỗi dễ gây ra trễ trƣớc khi dữ liệu tập trung đƣợc truyền đến sink. Một phƣơng pháp để giảm độ trễ này là tập trung dữ liệu song song dọc theo chuỗi, và sẽ càng giảm nhiều hơn nếu các nút đƣợc trang bị bộ thu phát sử dụng CDMA. 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. Hơn nữa ở nút chính có thể xảy ra hiện tƣợng thắt cổ chai. 2.4.3 Giao thức dựa trên vị trí Mục tiêu chính của giải thuật phân tuyến này là dựa vào các thông tin về vị trí của các nút cảm biến để tìm một đƣờng đi hiệu quả đến đích. Loại phân tuyến này rất phù 34
35. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN hợp với mạng cảm biến nơi mà việc tập trung dữ liệu là kỹ thuật hữu ích để giảm thiểu việc truyền bản tin đến trạm cơ sở bằng cách loại bỏ sự dƣ thừa giữa các gói đến từ các nguồn khác nhau. Loại phân tuyến này còn yêu cầu sự tính toán và lƣợng mào đầu truyền dẫn thấp. Ta sẽ xem xét một số giao thức phân tuyến dựa trên vị trí nhƣ sau: 2.4.3.1 Giải thuật chính xác theo địa lý (GAF : Geographic Adaptive Fidelity) Giải thuật chính xác theo địa lý (GAF) 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. GAF khai thác việc dƣ thừa dữ liệu trong mạng bằng cách coi một tập hợp các nút con trong mạng là tƣơng đƣơng nhau khi nhìn từ giao thức lớp trên. GAF chia vùng quan sát thành các hình vuông đủ nhỏ, bất kỳ các nút nào trong hình vuông cũng đều có thể giao tiếp vô tuyến với bất kỳ nút nào nằm trong hình vuông bên cạnh.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 phân tuyến. Nó tạo ra một lƣới ảo cho vùng bao phủ. Mỗi nút dùng 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 phân 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.8). Hình (2.8) : Ví dụ về lƣới ảo trong GAF 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ỉ. Các nút chuyển trạng thái từ nghỉ sang hoạt động lần lƣợt để cho các tải đƣợc cân bằng. Có ba trạng thái đƣợc định nghĩa trong GAF, đó là : + Phát hiện (discovery), để xác định các nút lân cận trong lƣới. + Hoạt động (active), thể hiện sự tham gia vào quá trình định tuyến. + Nghỉ (sleep) khi sóng đƣợc tắt đi.Nút nào nghỉ trong bao lâu liên quan đến các thông số đƣợc điều chỉnh trong quá trình phân tuyến. Để điều khiển độ di động, mỗi nút trong lƣới ƣớc đoán thời gian rời khỏi lƣới của nó và gửi thông tin này đến nút lân cận. Các nút đang không hoạt động điều chỉnh thời gian nghỉ của chúng phù hợp các thông tin nhận đƣợc từ các nút lân cận đó để giữ cho việc phân tuyến đƣợc chính xác. 35
36. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN Trƣớc khi thời gian rời khỏi lƣới của các nút đang hoạt động quá hạn, các nút đang nghỉ thoát khỏi trạng thái đó và một trong số các nút đó trở nên hoạt động. GAF đƣợc triển khai cho cả những mạng bao gồm các nút không di động (GAF cơ bản) và mạng bao gồm các nút di động (GAF thích ứng di động). GAF cố gắng giữ mạng hoạt động bằng cách giữ cho các nút đại diện luôn ở chế độ hoạt động trong mỗi vùng ở lƣới ảo của nó. Các kết quả mô phỏng đã chỉ ra rằng GAF thực hiện tối thiểu sẽ đƣợc nhƣ giao thức phân tuyến trong mạng ad hoc thông cho vi trí, thƣờng khi nói đến tổn thất gói và làm tăng thời gian sống của mạng bằng cách tiết kiệm năng lƣợng. Mặc dù GAF là một giao thức dựa trên vị trí, nó cũng có thể đƣợc coi là nhƣ một giao thức phân cấp khi mà các cụm dựa trên vị trí địa lý. Đối với mỗi vùng lƣới xác định, mỗi nút đại điện hoạt động nhƣ một nút chủ để truyền dữ liệu đến các nút khác. Tuy nhiên nút chủ này không thực hiện bất cứ một nhiệm vụ hợp nhất hay tập trung dữ liệu nào nhƣ trong các giao thức phân cấp thông thƣờng. 2.4.3.2 GEAR (Geographic and Energy-Aware Routing) Yue et đã đƣa ra việc sử dụng thông tin về địa lý trong khi phổ biến các yêu cầu đến các vùng thích hợp vì các yêu cầu dữ liệu thƣờng bao gồm các thuộc tính địa lý. Giao thức GEAR dùng sự nhận biết về năng lƣợng và các phƣơng pháp thông báo thông tin về địa lý tới các nút lân cận. Việc phân 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 này 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. 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. Trong giao thức GEAR, mỗi một nút giữ một estimated cost và một learned cost trong quá trình đến đích qua các nút lân cận. Estimated cost là sự kết hợp của năng lƣợng còn dƣ và khoảng cách đến đích. Learned cost là sự cải tiến của estimated cost giải thích cho việc phân tuyến xung quanh các hốc trong mạng. Hốc xảy ra khi mà một nút không có bất kì một nút lân cận nào gần hơn so với vùng đích hơn là chính nó. Trong trƣờng hợp không có một hốc nào thì estimated cost bằng với learned cost. Learned cost đƣợc truyền ngƣợc lại 1 hop mỗi lần một gói đến đích làm cho việc thiết lập đƣờng cho gói tiếp theo đƣợc điều chỉnh. Có 2 pha trong giải thuật này: + Chuyển tiếp gói đến vùng đích: GEAR dùng cách tự chọn nút lân cận dựa trên sự nhận biết về năng lƣợng và vị trí địa lý để phân tuyến gói đến vùng đích. Có 2 trƣờng hợp cần quan tâm: - Khi tồn tại nhiều hơn một nút lân cận gần hơn so với đích: GEAR sẽ chọn hop tiếp theo trong số tất cả các nút lân cận gần đích hơn. - Khi mà tất cả các nút đều xa hơn: trong trƣờng hợp này sẽ có một lỗ hổng. GEAR chọn hop tiếp theo mà làm tối thiểu giá chi phí của nút lân cận này. Trong trƣờng hợp này, một trong số các nút lân cận đƣợc chọn để chuyển tiếp gói dựa trên learned cost. Lựa chọn này có thểđƣợc cập nhật sau theo sự hội tụ của learned cost trong suốt quá trình truyền gói. + Chuyển tiếp gói trong vùng : Nếu gói đƣợc chuyển đến vùng, nó có thể truyền dữ liệu trong vùng đó có thể bằng cách chuyển tiếp địa lý đệ quy hoặc flooding có giới hạn. Flooding có giới hạn áp dụng tốt trong trƣờng hợp các sensor triển khai 36
37. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN không dày đặc. Ở những mạng có mật độ sensor cao, flooding địa lý đệ quy lại hiệu quả về mặt năng lƣợng hơn là flooding có giới hạn. Trong trƣờng hợp đó, ngƣời ta chia vùng thành 4 vùng nhỏ và tạo ra 4 bản copy của gói đó. Việc chia nhỏ này và quá trình chuyển tiếp tiếp tục cho đến khi trong vùng chỉ còn 1 nút, ví dụ nhƣ hình (2.8). Hình 2.8 Chuyển tiếp địa lý đệ quy trong GEAR Để thỏa mãn các điều kiện chúng ta dùng giải thuật chuyển tiếp địa lý đệ qui để truyền gói trong vùng này. Tuy nhiên, với những vùng mật độ thấp, chuyển tiếp địa lý đệ quy đôi khi không hoàn thành, định tuyến vô tác dụng trong một vùng đích rỗng trƣớc khi số hop gói đi qua vƣợt quá giới hạn. Trong trƣờng hợp này chúng ta dùng flooding có giới hạn. 2.5 Kết luận Chƣơng này đã tổng kết và đƣa ra khá nhiều các giao thức phân tuyến. Mỗi giao thức đều có những ƣu và nhƣợc điểm riêng. Hiện nay, đã có rất nhiều các cải tiến của các loại giao thức này đƣợc đƣa ra, và cho kết quả rất khả quan. Việc lựa chọn loại giao thức nào hoàn toàn phụ thuộc vào ứng dụng mà chúng ta triển khai. Mặc dù sự hoạt động của các giải thuật phân tuyến này đầy hứa hẹn trong vấn đề sử dụng hiệu quả năng lƣợng, các nghiên cứu sau này cần phải xác định rõ các vấn đề nhƣ chất lƣợng dịch vụ của các ứng dụng của các cảm biến hình ảnh và các ứng dụng thời gian thực. 37
38. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN CHƢƠNG III : Các cấu trúc giao thức phân tuyến LEACH 3.1 Giới thiệu Ngày nay nhờ có những tiến bộ nhanh chóng trong khoa học và công nghệ sự phát triển của những mạng bao gồm các cảm biến giá thành rẻ, tiêu thụ ít năng lƣợng và đa chức năng đã nhận đƣợc những sự chú ý đáng kể. Hiện nay ngƣời ta đang tập trung triển khai các mạng cảm biến để áp dụng vào trong cuộc sống hàng ngày. Đó là các lĩnh vực về y tế, quân sự, môi trƣờng, giao thông Trong một tƣơng lai không xa, các ứng dụng của mạng cảm biến sẽ trở thành một phần không thể thiếu trong cuộc sống con ngƣời nếu chúng ta phát huy đƣợc hết các điểm mạnh mà không phải mạng nào cũng có đƣợc nhƣ mạng cảm biến. Tuy nhiên mạng cảm ứng đang 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 đó là nguồn năng lƣợng bị giới hạn và không thể nạp lại. WSN sẽ kích hoạt tính năng đáng tin cậy của mạng lƣới giám sát các vùng sâu, vùng xa. Công việc chủ yếu của các mạng lƣới là thu thập dữ liệu, thu thập dữ liệu có tính tổng quan cao và ngƣời dùng cuối yêu cầu phải có mô tả cấp cao của môi trƣờng đang có những nút cảm ứng. Ngoài ra, mạng lƣới triển khai dễ dàng, hệ thống lâu đời, và dữ liệu truyền nhận trễ thấp. Những hạn chế về pin của các nút và số lƣợng lớn dữ liệu mà mỗi nút thu thập với nhƣ cầu cần thiết cho ứng dụng với hiệu quả ở mức chi phí tối thiểu về năng lƣợng và độ trễ. Để đáp ứng các yêu cầu của các mạng WSN chúng tôi phát triển Leach. Leach là một cụm dựa trên giao thức bao gồm các tính năng sau đây: + Ngẫu nhiên, thích nghi, tự cấu hình thành cụm. + Kiểm soát dữ liệu truyền nhận. + Phƣơng tiện truyền thông năng lƣợng thấp. +Ứng dụng cụ thể xử lý dữ liệu, nhƣ là tập hợp dữ liệu. Các ứng dụng điển hình của mạng cảm biến là hỗ trợ các mạng lƣới giám sát môi trƣờng từ xa. Dữ liệu của các nút riêng lẻ tƣơng quan trong một bộ cảm biến mạng, ngƣời dùng cuối cùng không đòi hỏi tất cả các dữ liệu(dƣ thừa), ngƣời dùng cuối cùng cần thu thập dữ liệu mô tả những sự kiện xảy ra trong môi trƣờng. 38
39. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN Hình 3.1: Các giao thức Leach cho các mạng lƣới Vì sự tƣơng quan dữ liệu giữa các tín hiệu từ các nút nằm gần nhau, chúng tôi đóng cụm để sử dụng cơ sở hạ tầng nhƣ là cơ sở cho Leach. Điều này cho phép tất cả các dữ liệu từ các nút trong nhóm để đƣợc xử lý tại nút cluster-head, giảm bớt những dữ liệu cần thiết để đƣợc chuyển đến ngƣời dùng cuối. Vì vậy, các nút sẽ tiết kiệm năng lƣợng của nó. Trong Leach, các nút tự tổ chức mình thành một cụm, với một nút hành động nhƣ là cluster-head. Tất cả các nut non-cluster-head phải truyền tải dữ liệu của họ vào nút clusted-head, trong khi nút cluster-head phải nhận đƣợc dữ liệu từ tất cả các thành viên trong nhóm, thực hiện chức năng xử lý tín hiệu trên các dữ liệu (ví dụ nhƣ: tập hợp các dữ liệu), và truyền tải dữ liệu đến trạm cơ sở ở xa . Vì vậy, nút cluster-head tốn nhiều năng lƣợng hơn nút non-cluster-head. Trong kịch bản, nơi tất cả các nút có năng lƣợng giới hạn, nếu cluster-head đã lựa chọn theo cách suy diễn và cố định trên toàn hệ thống trong đời, nhƣ trong một thuật toán nhóm tĩnh, các nút cluster-head xin cảm biến một cách nhanh chóng lập các giới hạn sử dụng năng lƣợng. Một khi các cluster-head hết năng lƣợng, nó không còn hoạt động. Hình 3.2: Thời gian hiển thị hoạt động cua Leach Vì vậy, khi một nút cluster-head chết, tất cả các nút nằm trong nhóm bị mất khả năng giao tiếp. Vì vậy, Leach xoay vòng lựa chọn các nút cluster-head nhƣ vậy nó xoay vòng giữa các nút cảm biến để tránh hiện tƣợng hết pin của bất kỳ nút cảm biến trên mạng lƣới nhằm kéo dài tuổi thọ của các nút. Bằng cách này, việc nạp năng lƣợng đƣợc liên kết với một cluster-head là đều chia ra cho các nút. Phƣơng tiện truyền thông truy cập trong Leach đã đƣợc chọn để làm giảm năng lƣợng tiêu hao trong không các nút cluster-head. Kể từ khi nút cluster-head biết tất cả các thành viên trong nhóm. Nó có thể tạo ra một lịch trình TDMA rằng mỗi nút cho biết chính xác khi nào sẽ truyền tải dữ liệu của nó. Điều này cho phép các nút để ở chế độ ngủ càng lâu càng tốt. Ngoài ra, bằng cách sử dụng một lịch trình TDMA chuyển giao cho các dữ liệu ngăn chặn các xung đột trong các cụm. Các hoạt động của các Leach đƣợc chia thành vòng. Mỗi vòng bắt đầu với một 39
40. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN giai đoạn thiết lập khi các cụm đƣợc tổ chức, theo sau một giai đoạn ổn định, nơi một số khung của dữ liệu đƣợc chuyển giao từ các nút vào cluster-head và để trên trạm cơ sở. Giai đoạn ổn định dài so với giai đoạn thiết lập. 3.2. Tự cấu hình cụm LEACH cluster sử dụng một thuật toán phân phối, nơi các nút thực hiện tự quyết định mà không có bất kỳ trung tâm kiểm soát. Những lợi ích của phƣơng pháp tiếp cận này là không có thông tin liên lạc đƣờng dài với các trạm cơ sở đƣợc yêu cầu và phân phối hình thành cụm có thể đƣợc thực hiện mà không cần biết chính xác vị trí của bất kỳ các nút trong mạng. Trong phần bổ sung thêm, không có thông tin liên lạc toàn cục cần thiết để thành lập cụm. Mục đích là để đạt đƣợc các kết quả của toàn cục, hình thành tốt cụm ra khỏi nút, hoàn toàn thông qua vị trí thực hiện các quyết định của mỗi nút tự quyết. 3.2.1. Xác định nút cluster-head Ban đầu, khi nhóm đang đƣợc tạo ra, mỗi nút quyết định có hay không trở thành một cluster-head . Quyết định này đƣợc tính dựa trên tỷ lệ phần trăm đề xuất của nhóm trƣởng cho các mạng ( trƣớc khi xác định) và số lần các nút có đƣợc một cluster-head. Quyết định này đƣợc thực hiện bởi n nút lựa chọn ngẫu nhiên một số từ 0 đến 1. Nếu con số sẽ thấp hơn một ngƣỡng T (n), các nút sẽ trở thành một cluster- head. Ngƣỡng đƣợc thiết lập nhƣ: P T(n) = if n G 1 1 P *(r mod ) P T (n) = 0 khác Ở đâu P = tỷ lệ phần trăm mong muốn của ngƣời đứng đầu nhóm, r = chu kỳ hiện thời, và G là tập hợp các nút không đƣợc lựa chọn là cluster-head trong 1/P chu kỳ . Bằng cách sử dụng theshold, mỗi nút sẽ đƣợc làm cluster-head tại một số điểm trong vòng1/P chu kỳ. Sau 1/P - 1 chu kỳ, T = 1 cho bất kỳ nút nào chƣa đƣợc làm cluster- head, và sau 1/P chu kỳ, tất cả các nút lại một lần nữa hội đủ điều kiện để trở thành cluster-head 3.2.2. Giai đoạn thiết lập Một khi các nút bầu cử tự nhận là cluster-head bằng cách sử dụng những xác xuất trong chƣơng trình ở trên, các nút cluster-head phải thông báo cho tất cả các nút khác trong mạng lƣới biết rằng họ đã chọn cho vai trò này trong chu kỳ hiện tại. Để làm đƣợc điều này, mỗi nút cluster-head phát một tin nhắn quảng cáo (Adv) bằng cách sử dụng CSMA. Thông báo này là một thông điệp có chứa ID của nút và một tiêu đề mà phân biệt thông báo này nhƣ một thông điệp thông báo. Tuy nhiên, thông báo này phải đƣợc phát sóng để tiếp cận với tất cả các nút trong mạng. Có hai cách cho việc này. Trƣớc tiên, đảm bảo rằng tất cả các nút nghe thông báo chủ yếu loại bỏ xung đột khi CSMA đƣợc sử dụng. Thứ hai, một khi không có gì đảm bảo rằng các nút tự bầu chọn cluster-head là spead đều trên toàn mạng, bằng cách sử dụng nguồn điện đủ để tiếp cận với tất cả các nút đảm bảo rằng tất cả các nút có thể trở thành một phần của một nhóm. Nếu nguồn điện của các thông điệp thông báo đã đƣợc giảm, một số nút trên cạnh của các mạng có thể không nhận đƣợc bất kỳ thông báo và do đó có thể không thể tham gia vào vòng này của các giao thức. Hơn nữa, từ những thông điệp 40
41. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN thông báo nhỏ, việc gia tăng nguồn điện để tiếp cận với tất cả các nút trong mạng lƣới không phải là một gánh nặng. Vì vậy, việc truyền tải điện năng đƣợc thiết lập đủ cao mà tất cả các nút trong mạng có thể nghe các thông điệp thông báo. Mỗi nút non-cluster-head xác định nó thuộc nhóm nào bằng cách chọn các cluster- head đòi hỏi năng lƣợng truyền thông tối thiểu, dựa trên việc nhận tín hiệu cƣờng độ thông báo từ mỗi cluster-head. Sau khi đã quyết định nút thuộc nhóm nào, nó phải thông báo cho nút cluster-head rằng nó sẽ là một thành viên của nhóm. Mỗi nút truyền một thông báo yêu cầu tham gia(Join-Req) quay trở lại chọn cluster-head bằng cách sử dụng CSMA. Thông báo này lại là một thông báo ngắn, bao gồm các ID của nút, các ID của các cluster-head, và một tiêu đề. Kể từ khi nút có một quan niệm về năng lƣợng cần thiết để tiếp cận với các cluster-head (dựa trên nhận đƣợc thông điệp thông báo về mức năng lƣợng của), nó có thể điều chỉnh nó để truyền tải điện năng cấp độ này. Các cluste-head trong LEACH hoạt động nhƣ các trung tâm kiểm soát vị trí để phối hợp các dữ liệu đƣợc truyền đi trong nhóm của họ. Các nút cluster-head thiết lập một lịch trình và TDMA truyền vào lịch trình các nút trong cụm. Điều này đảm bảo rằng không có xung đột dữ liệu và cũng cho phép các thành phần phát của mỗi nút non-cluster-head đƣợc tắt ở tất cả các lần, trừ khi thời gian của họ truyền tải, do đó giảm thiểu năng lƣợng tiêu thụ của các cảm nhận riêng lẻ. Sau khi TDMA gọi lịch trình của tất cả các nút trên các cụm, các thiết lập giai đoạn hoàn tất và giai đoạn ổn định có thể bắt đầu hoạt động. Hình 3,3: Lƣu đồ quá trình thiết lập 41
42. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN Hình 3,4: năng động trong quá trình hình thành hai nhóm khác nhau trong vòng LEACH 3.2.3. Giai đoạn ổn định Các hoạt động giai đoạn ổn định là đứt quãng trong khung, nơi các nút gửi dữ liệu vào các cluster-head tại hầu hết các khung cho mỗi lần trong thời gian của khe truyền . Mỗi khe trong đó một nút truyền dữ liệu là cố định, do đó, thời gian cho một khung của dữ liệu chuyển tùy thuộc vào số lƣợng các nút trong cụm. Trong khi các thuật toán phân phối để xác định nút cluster-head đảm bảo cho việc tạo ra số lƣợng mỗi chu kỳ tạo cụm là k, nó không đảm bảo rằng có k cụm ở mỗi chu kỳ. Trong phần bổ xung thêm, các thiết lập giao thức không đảm bảo rằng các nút đều đƣợc chia ra cho các nút cluster-head. Để giảm năng lƣợng tiêu hao, mỗi nút non-cluster-head sử dụng quyền lực để thiết lập kiểm soát số lƣợng truyền tải điện năng, dựa vào các nhận đƣợc năng lƣợng của các thông báo cluster-head. Ngoài ra, các trạm phát của mỗi nút non-cluster-head bị tắt cho đến khi phân bổ lại thời gian truyền. Vì tất cả các nút có để gửi cho các cluster- head bằng cách sử dụng một lịch trình TDMA. Các cluster-head phải thu nhận tất cả các dữ liệu từ các nút trong cụm. Một khi cluster-head nhận đƣợc tất cả các dữ liệu, nó có thể hoạt động trên các dữ liệu (ví dụ nhƣ: thực hiện việc tập hợp dữ liệu) và sau đó các dữ liệu đƣợc gửi từ các cluster-head đến tram cơ sở . . 42
43. Đồ án tốt nghiệp K9 Phân tuyến trong mạng WSN Hình 3.5: lƣu đồ giai đoạn ổn định MAC và các giao thức phân tuyến đƣợc thiết kế để bảo đảm năng lƣợng tiêu hao trong các nút thấp và không có xung đột dữ liệu trong nhóm. Tuy nhiên, đài phát vốn là một phƣơng tiện quảng bá. Nhƣ vậy, truyền trong một nhóm sẽ ảnh hƣởng đến giao tiếp trong một nhóm gần đó. Hình 3.6: Tƣơng tác giữa nhiều cụm. Hình 3,6 hiển thị các thông tin liên lạc cho một đài phát , nơi nút A truyền, trong khi dành cho nút B, xung đột làm hỏng dữ liệu truyền cho nút C. Để giảm sự can thiêp của cụm, mỗi cụm trong Leach giao tiếp sử dụng cách lan truyền các chuỗi (DS-SS). Mỗi nhóm sử dụng một mã số duy nhất để lan truyền, tất cả các nút trong cụm truyền tải dữ liệu vào các cluster-head này lan truyền bằng cách sử dụng mã số và các cluster-head nhận đƣợc tất cả các bộ lọc năng lƣợng bằng cách sử dụng mã số này lan truyền. Điều này khác với phƣơng pháp tiếp cận CDMA nơi mỗi nút sẽ có một mã số duy nhất. DS-SS kết hợp với ý tƣởng làm giảm TDMA , nhóm can thiệp, trong khi loại trừ can thiệp trong nhóm và yêu cầu chỉ có một bộ lọc phù hợp cho viecj nhận đƣợc dữ liệu. Dữ liệu từ nút cluster-head đến trạm cơ sở sẽ đƣợc gửi bằng cách sử dụng một mã số lan truyền cố định và một phƣơng pháp tiếp cận CSMA. Khi một cluster-head có dữ liệu để gửi, nó phải cảm nhận các kênh để xem bất kỳ một nút nào khác có đƣợc truyền bằng cách sử dụng tram cơ sở lan truyền mã . Nếu vậy, các cluster-head chờ đợi để truyền dữ liệu. Nếu không, các cluster-head gửi dữ liệu bằng cách sử dụng trạm 43