Chương 1: Giới thiệu về mạng cảm biến không dây và ứng dụng, những vấn đề gặp phải trong mạng cảm biến không dây, định tuyến dựa trên thông tin vị trí, các kỹ thuật khôi phục - Chương 2: Trình bày các kỹ thuật xây dựng đồ thị phẳng. - Chương 3: Đánh giá hiệu năng của định tuyến khôi phục trên các đồ thị phẳng. 2 TIEU LUAN MOI download : skknchat@gmail.com CHƢƠNG 1: TỔNG QUAN VỀ ĐỊNH TUYẾN DỰA TRÊN THÔNG TIN VỊ TRÍ CHO MẠNG CẢM BIẾN KHÔNG DÂY 1.Mạng cảm biến không dây Mạng cảm biến không dây (WSN: Wireless Sensor Networks) bao gồm nhiều nút cảm biến. Mỗi nút bao gồm có các thành phần sau: - Vi điều khiển bao gồm: CPU, ROM, RAM, ADC, DAC.
- Sensor: cảm nhận thế giới bên ngoài, sau đó chuyển dữ liệu qua bộ phận chuyển đổi để xử lý. -Bộ phát radio - Nguồn năng lƣợng (pin) và có thể có cả bộ phận định vị. Node cảm biến là thành phần quan trọng nhất trong WSN. Do vậy, việc thiết kế các node cảm biến sao cho có thể tiết kiệm đƣợc tối đa nguồn năng lƣợng là vấn đề quan trọng hàng đầu Nút cảm biến có nhiệm vụ thu nhận các tín hiệu vật lý từ môi trƣờng xung quanh.
Tín hiệu vật lý thu nhận đƣợc đƣợc lƣợng hóa bằng bộ chuyển đổi tƣơng tự - số (ADC) rồi đƣợc chuyển vào bộ vi xử lý. Thông thƣờng, mỗi thiết bị cảm biến chỉ đo đƣợc một tín hiệu vật lý nhƣ nhiệt độ, độ ẩm, áp suất, độ sáng, độ rung chuyển hay nồng độ khí CO2, v. Để đo nhiều tín hiệu vật lý đồng thời, ngƣời ta tích hợp nhiều thiết bị cảm biến thành một bảng các thiết bị cảm biến. Bộ phận thu/phát tín hiệu không dây có nhiệm vụ điều chế và phát tín hiệu dƣới dạng sóng không dây, đồng thời thu và giải điều chế tín hiệu.
Các chuẩn công nghệ đƣợc sử dụng phổ biến cho WSN bao gồm IEEE 802. Bộ phận định vị, ví dụ thiết bị GPS, cho biết vị trí (tọa độ) của nút cảm biến. Bộ vi xử lý có năng lực tính toán hạn chế. Tƣơng tự, bộ nhớ có dung lƣợng cũng hạn chế.
Pin có nhiệm vụ cung cấp điện cho nút hoạt động, có kích thƣớc nhỏ và thƣờng không nạp điện bổ sung. Tất cả các thành phần kể trên cấu thành một máy tính siêu nhỏ với khả năng tính toán và 3 TIEU LUAN MOI download : skknchat@gmail.com truyền dữ liệu. Nhiều nút cảm biến đƣợc triển khai trên một khu vực tạo thành một mạng tự hợp của các nút cảm biến. Do vậy, một mạng cảm biến cho phép truy nhập thông tin mọi lúc mọi nơi bằng cách thu thập, xử lý, phân tích và phát tán dữ liệu.
Dẫn tới cảm biến tham gia một cách tích cực trong việc tạo ra một môi trƣờng thông minh. Mạng cảm biến hứa hẹn sẽ là một cuộc cách mạng trong một loạt các ứng dụng. Điều này là có thể bởi tính linh hoạt, chính xác, hiệu quả về giá thành và dễ dàng về triển khai của mạng, theo Tilaketal. Những bộ cảm biến thông minh cho phép giám sát, thăm dò và thu thập dữ liệu liên quan đến bất kỳ hỏng hóc nào của máy móc, động đất, lũ lụt, thậm chí là một vụ tấn công khủng bố.Những vấn đề gặp phải trong định tuyến cho mạng cảm biến không dây Mạng cảm biến không dây có những đặc tính riêng sau dẫn đến những thách thức cho việc thiết kế các thuật toán định tuyến cho mạng cảm biến không dây: - Tài nguyên (năng lực tính toán, bộ nhớ, pin) của mỗi nút hết sức hạn chế: Đây là thách thức lớn khi thiết kế các thuật toán định tuyến cho mạng cảm biến không dây.
Những thuật toán áp dụng đƣợc cho mạng cảm biến không dây phải yêu cầu tính toán cũng nhƣ lƣu trữ rất ít tại mỗi nút. Đồng thời, những thuật toán này phải giải quyết tốt vấn đề cân bằng tải để ít nút phải hoạt động nhiều hơn và sớm ngừng hoạt động do pin hết điện. - Số lƣợng nút đƣợc triển khai có thể rất lớn: Có thể hàng nghìn nút đƣợc triển khai trên vùng rộng lớn. Đặc điểm này càng làm tăng yêu cầu tính toán cũng nhƣ lƣu trữ rất ít tại mỗi nút.
- Nút thay đổi chế độ thức và ngủ: Để tiết kiệm điện của pin và kéo dài tuổi thọ các nút, một số nhà sản xuất cung cấp các nút có khả năng đi vào chế độ ngủ khi rỗi hay theo chu kỳ. Đây là một thách thức cho các thuật toán định tuyến vì các liên kết giữa các nút hay bị thay đổi. 4 TIEU LUAN MOI download : skknchat@gmail.com - Nút ngừng hoạt động: Do các nút cảm biến có thể đƣợc đặt ở một số nơi có điều bên ngoài khắc nghiệt, hoặc các node có nguồn nuôi bị hết pin. Nên các nút cảm biên có thể bị ngừng hoạt động - Nút đƣợc bổ sung: Các nút mới có thể đƣợc bổ sung để lấp các vùng trống do các nút đã ngừng hoạt động để lại hoặc để mở rộng khu vực triển khai.
Trên đây là các thách thức gặp phải trong quá trình nghiên cứu mạng cảm biến không dây. Để mạng cảm biến đƣợc triển khai trên thực tế cẩn có những nghiên cứu để giải quyết đƣợc các thách thức trên. Định tuyến dựa trên thông tin vị trí Trƣớc đây, trong định tuyến trên mạng hay sử dụng phƣơng pháp định tuyến dựa trên thông tin về topo mạng Các phƣơng pháp định tuyến dựa trên thông tin topo nhƣ DSDV [10] , WRP [11], STAR [12], sử dụng tác tử di động [14], AIR [15], OLSR [16] và TBRPF [17], DSR [10], AODV [18], LBAR [19], preemptive routing [20], DLAR [21], và NCP-based [22] yêu cầu các nút phải lƣu trữ nhiều thông tin về các đƣờng định tuyến. Yêu cầu này vƣợt ngoài khả năng đáp ứng của các nút cảm biến.
Ngoài ra, định tuyến topo sử dụng nhiều gói tin điều khiển để tìm và duy trì các đƣờng đƣờng định tuyến. Ngoài tác động làm giảm băng thông sẵn có cho dữ liệu, nhiều gói tin điều khiển tiêu hao điện năng của các nút và hệ quả là làm giảm tuổi thọ của các nút. Với đặc điểm nhƣ vậy, định tuyến dựa trên topo hầu nhƣ không áp dụng đƣợc cho mạng cảm biến. Và điều này đòi hỏi cần có một phƣơng pháp mới phù hợp cho mạng cảm biến Những năm gần đây, phƣơng pháp định tuyến dựa trên thông tin vị trí đã ra đời [1] [2] và đã trở thành phƣơng pháp định tuyến đƣợc sử dụng rộng rãi trong mạng cảm biến không dây.
Định tuyến dựa trên thông tin vị trí giả thiết rằng: mỗi nút biết về vị trí của nó bằng việc sử dụng hệ thống định vị nhƣ GPS hoặc bằng kỹ thuật định vị nào đó. Ngoài ra, định tuyến cần sử dụng một thuật toán khác, đƣợc gọi là dịch vụ thông tin vị trí (location service) [1] 5 TIEU LUAN MOI download : skknchat@gmail.com [2], để xác định vị trí của nút đích. Trƣớc khi thực hiện thuật toán định tuyến, nút nguồn xác định vị trí của nút đích thông qua triệu gọi dịch vụ thông tin vị trí, chẳng hạn sử dụng hệ thống định vị toàn cầu GPS. Thông tin về vị trí nút đích, sau đó, đƣợc gắn vào tiêu đề mỗi gói tin cần chuyển đi và đƣợc sử dụng làm thông tin dẫn đƣờng.
Các nút không phải duy trì các đƣờng đi cũng nhƣ các trạng thái định tuyến. Định tuyến dựa trên thông tin vị trí sử dụng kết hợp chuyển tiếp dựa trên thông tin vị trí (geographic forwarding - GF) và định tuyến khôi phục (recovery routing - RR) để định tuyến gói tin. Chuyển tiếp dựa trên thông tin vị trí là kỹ thuật chuyển gói tin từ nút này đến nút khác gần đích hơn. Độ gần đích của một nút có thể đo bằng khoảng cách từ nút đó đến nút đích.
Nút không có láng giềng gần đích hơn đƣợc gọi là cực tiểu địa phƣơng (local minimum). Cực tiểu địa phƣơng xuất hiện ở biên của những vùng trống (hole), hay vùng không có nút cảm biến, và biên của mạng. Để mỗi nút nhận đƣợc gói tin biết nên sử dụng chuyển tiếp dựa trên thông tin vị trí hay định tuyến khôi phục cho gói tin nhận đƣợc, một thông tin chỉ dẫn đƣợc gọi là chế độ (mode) định tuyến đƣợc ghi trong tiêu đề của gói tin. Chế độ định tuyến có thể là tham lam (greedy) hoặc khôi phục (recovery).
Nút nguồn thiết lập chế độ tham lam, hay chế độ sử dụng chuyển tiếp dựa trên thông tin vị trí, cho gói tin. Khi nhận đƣợc gói tin ở chế độ tham lam, cực tiểu địa phƣơng sẽ thay đổi gói tin sang chế độ khôi phục, hay chế độ sử dụng định tuyến khôi phục, đồng thời ghi thông tin về vị trí của nó vào tiêu đề gói tin ở trƣờng cực tiểu địa phƣơng gặp cuối cùng. Khi nhận đƣợc gói tin ở chế độ khôi phục, nút gần đích hơn cực tiểu địa phƣơng gặp cuối cùng khôi phục gói tin về chế độ tham lam. Ở những tình huống còn lại, nút nhận đƣợc gói tin không thay đổi chế độ định tuyến của gói tin mà chỉ chuyển tiếp gói tin bằng việc áp dụng chuyển tiếp dựa trên thông tin vị trí hay định tuyến khôi phục tùy theo chế độ định tuyến hiện tại của gói tin.
6 TIEU LUAN MOI download : skknchat@gmail.com CHƢƠNG 2: CÁC KỸ THUẬT XÂY DỰNG ĐỒ THỊ PHẲNG 2. Các kỹ thuật khôi phục 2.Tổng quan Khi chuyển tiếp tham lam gặp thất bại, thì quá trình chuyển tiếp gói tin từ nguồn đến đích sẽ chuyển sang định tuyến khôi phục. Có hai kỹ thuật chinh đƣợc sử dụng trong kỹ thuật khôi phục: - Định tuyến gói tin đi theo biên của vùng trống - Định tuyến gói trên đồ thị phẳng. Định tuyến gói tin theo biên của vùng trống Ta sẽ tìm hiểu một số thuật toán định tuyến chính đi theo biên của vùng trống.
Đó là các thuật toán: -Thuật toán BOUNDHOLE -Thuật toán GAR -Thuật toán Curved Stick 1).Thuật toán BOUNDHOLE 1.Ý tƣởng BoundHole [2] [6] [7] là một kỹ thuật khôi phục đi theo biên hiệu quả. Trong đó, BoundHole sử dụng kỹ thuật quay (sweeping) để chuyển tiếp gói tin theo biên vùng trống.Mô tả Trong [2] nhóm tác giả định nghĩa các nút bị kẹt mà ở đó gói tin bị kẹt khi chuyển tiếp tham lam và phát triển một quy tắc cục bộ, gọi là quy tắc TENT cho mỗi nút trong mạng để kiểm tra một gói tin có bị kẹt hay không. Để đƣa gói tin ra khỏi các nút bị kẹt, họ đã đƣa ra thuật toán BOUNDHOLE, để xây dựng các đƣờng đi xung quanh các vùng trống. Có hai loại nút bị kẹt: nút bị kẹt yếu và nút bị kẹt mạnh.
7 TIEU LUAN MOI download : skknchat@gmail.