Phần II: CHẤT LƯỢNG DỊCH VỤ CHO WSN
Chương 5: Đa kênh và truyền thông thời gian thực
5.3 Giao thức đa kênh luồng cơ sở
5.3.2 Hiệu quả năng lượng định tuyến thời gian thực
5.3.2.2 Quản lí lân cận
Kiến trúc định tuyến tin cậy được chấp nhận để đối phó với việc năng động và mất mát tự nhiên trong WSN. Đầu tiên chất lượng và trạng thái của liên kết phải được đo lường tự động qua một bộ ước lượng liên kết (link estimator). Thứ hai chất lượng liên kết đo lường được phải được duy trì trong một bảng lân cận (neighborhood table) để tạo ra quyết định định tuyến tin cậy trong môi trường động. Trong giao thức của chúng ta, chúng ta đo lượng độ trễ trên từng chặng giũa nút và mỗi lân cận sử dụng các gói dữ liệu để tránh chi phí tìm kiếm gói tin (overhead of probing packets). Thông tin độ trễ của mỗi lân cận được lưu trữ trong bảng lân cận (neighbor table) và sử dụng để tạo ra các quyết định định tuyến tin cậy. Đặc biệt chúng ta duy trì bảng lân cận cho mỗi nút để ghi lại tốc độ cung cấp của mỗi nút lân cận (provided velocity of each neighbor).
Khi một nút nhận một gói tin, nó sẽ tìm kiếm trong bảng để tìm ra một lân cận mà có thể cung cấp tốc độ yêu cầu và chi phí năng lượng truyền thông thông thấp nhất. Theo cách này, chúng ta sử dụng chỉ vừa đủ năng lượng cho tốc độ mong đợi và vì thế mà có thể đạt được năng lượng hiệu quả.
Nếu không có lân cận có thể cung cấp tốc độ yêu cầu, nút sẽ lựa chọn vài lân cận để xây dựng năng lượng thích nghi. Nút lân cận được sử dụng trong việc phân phát thành công gói tin trước đó tới cùng một nút đích sẽ được xem xét đầu tiên bởi vì trạng
thái liên kết của nó là cập nhật nhất. Nếu nút lần trước sử dụng là không phù hợp thì nó sẽ được xem xét ở lần thứ hai. Chúng ta chỉ xem xét các nút lân cận mà có số lần truyền lại khác không khi khoảng cách cho năng lượng thích nghi (power adaption) làm giảm độ trễ của chúng. Nếu năng lượng truyền thông tương ứng của nút lân cận không phải là mức cao nhất, chúng ta sử dụng chiến lược Multi Increase Linear Decrease (MILD) để điều chỉnh mức năng lượng sử dụng để truyền một gói tin tới nút lân cận. Đặc biệt mức năng lượng được nhân lên 1.5 lần cho thời gian phân phát của gói tin hiện tại. Ví dụ nếu mức năng lượng hiện tại là 10, mức năng lượng sẽ được sử dụng là 15 khi được sử dụng để phân tán gói tin. Việc tăng năng lượng khi phân phát gói tin được sử dụng bởi vì tính kịp thời là quan trọng hơn hiệu quả năng lượng ở đây.
Sau khi gói tin được truyền thành công, mức năng lượng sẽ được giảm đi 1 và tiếp tục giảm với mọi gói tin gửi thành công tới nút lân cận.
Nếu một nút không thể tìm thấy nút lân cận cho năng lượng thích nghi (power adaptation), nó sẽ gửi đi một gói tin yêu cầu định tuyến (Routing Request PR) để tìm - các lân cận mới mà có khả năng cung cấp tốc độ yêu cầu. Gói tin PR chứa tốc độ yêu cầu và thông tin bảng lân cận (neighbor table infomation), và được quảng bá sử dụng mức năng lượng cao nhất. Khi các lân cận mà không nằm trong bảng lân cận hiện tại chúng sẽ kiểm tra xem liệu chúng có thể cung cấp tốc độ yêu cầu. Nếu một lân cận có thể cung cấp tốc độ yêu cầu, nó sẽ trả lời gói tin PR sau một khoảng thời gian ngẫu nhiên. Khi các lân cận khác nghe được tin nhắn phản hồi chúng sẽ dừng việc trả lời nút hiện tại để làm giảm tắc nghẽn trong mạng gây ra bởi số lượng lớn các tin phản hồi.
Trong phần này chúng ta trình bày về MCRT, một giao thức đa kênh truyền thông thời gian thực, sử dụng đa kênh và năng lượng truyền tải thích nghi để đạt được truyền thông thời gian thực trong WSN. MCRT phân bổ kênh dựa trên luồng chỉ sử dụng một số lượng nhỏ các kênh trực giao. MCRT sử dụng hiệu quả đa kênh để giảm sự mất mát gói tin và đảm bảo thời gian thực trong truyền thông điểm điểm- .
Phần III: MÔ PHỎNG VÀ ĐÁNH GIÁ KẾT QUẢ Chương 6: Phần mềm mô phỏng NS2
6.1 Giới thiệu chung
NS2 (Network Simulator) là phần mềm mô phỏng mạng điều khiển sự kiện riêng rẽ hướng đối tượng, được phát triển tại UC Berkely, viết bằng ngôn ngữ C++ và OTcl.
NS rất hữu ích cho việc mô phỏng mạng diện rộng (WAN) và mạng local (LAN). Bốn lợi ích lớn nhất của NS 2 phải kể đến đầu tiên là: -
• Khả năng kiểm tra tính ổn định của các giao thức mạng đang tồn tại
• Khả năng đánh giá các giao thức mạng mới trước khi đưa vào sử dụng
• Khả năng thực thi những mô hình mạng lớn mà gần như ta không thể thực thi được trong thực tế
• Khả năng mô phỏng nhiều loại mạng khác nhau 6.2 Kiến trúc của NS2
NS thực thi các giao thức mạng như TCP, UDP; các dịch vụ như FTP, Telnet, Web, tốc độ bit cố định (CBR) và tốc độ bit thay đổi (VBR) ; các kỹ thuật quản lý hàng đợi như vào trước ra trước (Drop Tail), dò sớm ngẫu nhiễn (RED) và CBQ; các thuật toán định tuyến như Dijkstra… NS cũng thực thi multicasting và vài giao thức lớp điều khiển truy cập đường truyền (MAC) đối với mô phỏng LAN.
Hình 6.1: Tổng quan về NS dưới góc độ người dùng
• OTcl Script Kịch bản OTcl
• Simulation Program Chương trình mô phỏng
• OTcl Bộ biên dịch Tcl mở rộng hướng đối tượng
• NS Simulation Library Thư viện ô phỏng NS m
• Event Scheduler Objects Các đối tượng bộ lập lịch sự kiện
• Network Component Objects Các đối tượng thành phần mạng
• Network Setup Helping Modules Các mô đun trợ giúp hiết lập ạng t m
• Plumbling Modules Các mô đun Plumbling
• Simulation Results Các kết quả mô phỏng
• Analysis Phân tích
• NAM Network Animator Minh họa mạng NAM
Trong hình trên, NS là bộ biên dịch Tcl mở rộng hướng đối tượng; bao gồm các đối tượng bộ lập lịch sự kiện, các đối tượng thành phần mạng và các mô đun rợ giúp hiết t t lập ạng (hay các mô đunm Plumbing). Để sử dụng NS 2, user lập trình bằng ngôn ngữ - kịch bản OTcl. User có thể thêm các mã nguồn Otcl vào NS 2 bằng cách viết các lớp - đối tượng mới trong OTcl. Những lớp này khi đó sẽ được biên dịch cùng với mã nguồn gốc. Kịch bản OTcl có thể thực hiện những việc sau:
• Khởi tạo bộ lập lịch ự kiệns
• Thiết lập mô hình mạng dùng các đối tượng hành phần mạng t
• Báo cho nguồn traffic khi nào bắt đầu truyền và ngưng truyền packet trong bộ lập lịch ự kiệns
Thành phần lớn khác của NS bên cạnh các đối tượng thành phần mạng là ộ lập lịch b sự kiện. Bộ lập lịch ự kiện trong NS 2 thực hiện những việc sau: s -
• Tổ chức bộ định thời ô phỏng m
Hủy các sự kiện trong hàng đợi sự kiện
• Triệu gọi các thành phần ạng trong mô phỏng m
Phụ thuộc vào mục đích của user đối với kịch bản mô phỏng OTcl mà kết quả mô phỏng có thể được lưu trữ như file trace. Định dạng file trace sẽ được tải vào trong các ứng dụng khác để thực hiện phân tích:
• File nam trace (file.nam) được dùng cho công cụ minh họa mạng NAM
• File Trace (file.tr) được dùng cho công cụ ần vết và iám sát ô phỏng l g m XGRAPH hay TRACEGRAPH
Hình 6.2: Luồng các sự kiện cho file Tcl chạy trong NS
NAM Visual Simulation Mô phỏng ảo NAM
Tracing and Monitoring Simulation Mô phỏng ần vết và Giám sát l 6.3 C++ và OTcl
NS sử dụng hai ngôn ngữ lập trình: Ngôn ngữ kịch bản (Tcl – Tool Command Language) và Ngôn ngữ lập trình hệ thống (C/C++).
Dùng C++ để:
• Mô phỏng giao thức chi tiết yêu cầu ngôn ngữ lập trình hệ thống
Thao tác trên byte, xử lý gói, thực thi thuật toán
Tốc độ thời gian thực là quan trọng nhất
• Thực hiện bất kỳ việc gì mà cần phải xử lý tứng packet của một luồng.
• Thay đổi hành vi của lớp C++ đang tồn tại theo những hướng đã không được lường trước.
Và dùng OTcl để:
• Mô phỏng những thông số hay cấu hình thay đổi o Tham dò nhanh một số tình huống
o Thời gian tương tác (thay đổi mô hình hay chạy lại) là quan trọng
• Cấu hình, thiết lập hay những gì chỉ làm một lần.
• Thực hiện những cái ta muốn bằng cách thao tác trên các đối tượng C++ đang tồn tại.
6.4 Các thành phần cấu hình mạng trong NS2 Lớp mô phỏng (Simulator)
Trong bộ công cụ giả lập NS 2, lớp quan trọng nhất là lớp mô phỏng. Nó cung - cấp các thủ tục, giao tiếp để tạo, quản lý topology và lưu giữ các tham số cấu hình của các thành phần trong topology. Thông thường, các kịch bản giả lập thường bắt đầu bằng việc tạo một thể nghiệm của lớp Simulator để điều khiển và thực hiện việc giả lập, sau đó gọi các phương thức để tạo các node, topo và cấu hình cho các node, các liên kết, ứng dụng.
Các Agent trong NS2
Agent hay có thể gọi là giao thức ở tầng mạng hoặc ở tầng vận tải dùng để xử lý các gói tin khi node nhận được. Lớp Agent được cài đặt một phần trong Otcl và một phần trong C++.
• UDP Agent: UDP agent được cài đặt bên node gửi dữ liệu và cũng có thể được cài đặt bên node nhận. Agent này là agent không hướng kết nối, tức là không có cơ chế để phát hiện gói tin bị mất khi truyền, và truyền lại gói tin khi bị mất. Nó
chỉ thích hợp cho những ứng dụng không đòi hỏi độ chính xác cao, và chấp nhận chịu sự mất mát dữ liệu
• TCP Agent: Trong NS-2, TCP agent được chia làm hai loại: agent một chiều và agent hai chiều.
Agent một chiều là những agent chỉ đóng một trong hai vai trò hoặc là bên gửi hoặc là bên nhận. Trong khi đó, agent hai chiều là agent đóng cả hai vai trò vừa là bên nhận, vừa là bên gửi. Hiện nay, agent này vẫn đang được phát triển.
Lớp ứng dụng (Application)
Ứng dụng trong NS-2 được xây dựng bởi lớp ứng dụng được cài đặt trong phần nhân của NS-2. Lớp ứng cung cấp một số phương thức cơ bản cho quá trình hoạt động của một ứng dụng: send(), recv(), resume(), start(), stop(), một con trỏ trỏ đến giao thức ở tầng vận tải bên dưới mà nó kết nối.
Trong NS-2 có hai loại ứng dụng cơ bản:
• Ứng dụng phát sinh lưu lượng mạng (Traffic Generator)
• Ứng dụng giả lập mạng (Simulated Applications) Mạng không dây trong NS2
Thành phần quan trọng nhất trong mô hình mạng không dây là MobileNode.
Trong C++, lớp MobileNode được kế thừa từ lớp cha là lớp Node. Do đó, MobileNode có đầy đủ các đặc điểm của đối tượng Node, thêm vào đó là các đặc tính của Wireless như khả năng di chuyển tự do trong phạm vi của topology, có khả năng truyền và nhận tín hiệu vô tuyến.
Ngôn ngữ TCL
TCL -Tool Command Language là một ngôn ngữ lệnh khá mạnh, có thể chạy được trên các hệ điều hành như Unix, Linux, DOS/Window, OS/2 và MacOS nhờ các trình thông dịch. Tuy nhiên, ngôn ngữ này chỉ có một số ít các cấu trúc nền tảng và khá ít các cú pháp.
Chương 7: Mô phỏng và đánh giá kết quả
7.1 Thuật toán Mục đích
Tắc nghẽn là một hiện tượng rất quen thuộc trên mạng, mà nguyên nhân nói chung là do tài nguyên mạng giới hạn trong khi nhu c u truyầ ền thông tin của con ng i ườ là không có giới hạn. Thông th ng, nút mườ ạng được thi t kế ế ớ v i m t bộ ộ đệ m lưu trữ có hạn. Nếu tình trạng nghẽn mạng kéo đủ dài, bộ đệm bị tràn, các gói sẽ ị ất hoặc trễ b m quá thời gian cho phép. Nếu một gói bị m t trên mạấ ng thì tại thời đ ểm ấy các tài i nguyên m ng mà gói ạ đó đã s dử ụng cũng bị ất theo. m
Trong các mạng cảm biến thông thường các nút cảm biến sẽ đị nh kì ngủ và thức giấc đ g i tin báo cáo tới sink về ữể ử d liệu nó cảm nhận đư c vì vậợ y mà vấn đề ắ t c nghẽn có th ít xể ảy ra hơn. Tuy nhiên khi một số ợ lư ng lớn các nút cảm biến được triển khai và trong m t sộ ố ứ ng dụng dùng đ ể giám sát hiện tư ng, khi hiệợ n tư ng xảợ y ra thì lưu lượng trong m ng sạ ẽ tăng đ t biếộ n, hơn nữa do giới hạn về ộ b nhớ ạ t i các nút cảm biến và giớ ại h n về băng thông mà vấn đ t c ngh n có thể ề ắ ẽ trở thành trầm trọng.
Như đã nói ở trên việc sử dụng cơ chế đa kênh trong mạng cảm biến tận dụng được ưu điểm của phần cứng được thiết kế sẵn trên các nút cảm biến hiện nay, nhiều loại radio chip có thể làm việc với nhiều tần số khác nhau. Khi tắc nghẽn xảy ra việc sử dụng cơ chế truyền thông đa kênh sẽ làm tăng lưu lượng trên toàn mạng. Hơn nữa trong các ứng dụng giám sát có thể có những gói tin mang những thông tin quan trọng vì thế những gói tin này phải được ưu tiên đến đích trước, để giải quyết vấn đề này cần thiết lập mức ưu tiên cho các gói tin và có một cơ chế để điều khiển các gói tin này theo mức ưu tiên của chúng.
Ứng dụng
Một bài toán được đặt ra là một số lượng lớn các nút cảm biến được triển khai trong một khu rừng, khi xảy ra cháy rừng nhiệt độ của vùng đang cháy rõ ràng là cao hơn nhiều so với các vùng khác, các nút cảm biến sẽ liên tục gửi dữ liệu về sink để thông báo rừng đang bị cháy, tắc nghẽn sẽ xảy ra trong trường hợp này. Rõ ràng các gói tin báo nhiệt độ là 100-200 oC sẽ có độ quan trọng cao hơn là các gói tin báo nhiệt độ là 20-30 oC. Tại vùng rừng bị cháy các nút cảm biến sẽ đặt mức ưu tiên cho các gói tin của nó cao hơn so với bình thường. Các nút chuyển tiếp gói tin sẽ căn cứ vào mức ưu tiên của các gói tin mà quyết định gói tin nào được đến sink trước.
Mô hình sử dụng cơ chế đa kênh và mức ưu tiên cho các gói tin có thể được sử dụng cho các ứng dụng giám sát hiện tượng như là cháy rừng, giám sát địa chấn, đo mực nước…và một số ứng dụng khác.
Nguyên lí
Đa kênh và cơ chế định tuyến
Để sử dụng cơ chế đa kênh cần thực hiện:
(1) Nút nguồn và nút đích cần gắn thêm tag để chuyển tiếp các gói tin theo mẫu sau:
Destination Tag
Chẳng hạn nút nguồn là nút 0 muốn chuyển tiếp gói tin tới nút đích thì nút nguồn và nút đích phải gắn thêm tag = 8.
Nút nguồn (nút 0) gắn nút đích và tag
11 8
Nút đích (nút 11) gắn nút nguồn và tag
0 8
(2) Trên đường đi tới nút đích, các nút trung gian gắn nút đích, tag, nút tiếp theo và NIC
Destination Tag Next hop NIC
Chẳng hạn nút nguồn là nút 0 và nút đích là nút 11, gói tin xuất phát từ nút 0 lần lượt đi qua các nút 5 và 10 rồi tới nút 11.
Nút 0 gắng nút đích, tag, nút kế tiếp và NIC
11 8 0 1
11 8 5 1
Nút 5 gắn đích, tag, nút kế tiếp và NIC
11 8 10 1
Nút 10 gắn đích, tag, nút kế tiếp (nút sink) và NIC
11 8 11 1
Các hàng đợi Hàng đợi PriQ
Căn cứ vào mức ưu tiên của gói tin đến, nếu nó có mức ưu tiên là 1 nó sẽ được chuyển tiếp, các gói tin có mức ưu tiên khác sẽ được đưa vào hàng đợi chờ để gửi đi khi kênh nhàn rỗi.
Priority == 1 Forward packet
Queue/Droptail Yes
No Receive packet
Hình 7.1: Hàng đợi PriQ
Hàng đợi Multiserv
Khi các gói tin đến nút cảm biến, dựa theo mức ưu tiên của các gói tin mà nó sẽ được đưa vào các hàng đợi khác nhau, các gói tin có cùng một mức ưu tiên sẽ được đưa vào cùng một hàng đợi ở bộ Schedule các gói tin sẽ đi ra lần lượt là các gói tin trong hàng đợi có mức ưu tiên cao, tiếp theo đó là các gói tin trong hàng đợi có mức ưu tiên thấp hơn.
Input Output
Input
Input
Input
Output
Output
Output Priority = 1
Priority = 2
Priority = 3
Priority = 4
Scheduler
4 3 2 1
Hình 7.2: Hàng đợi Multiserv 7.2 Mô phỏng và đánh giá kết quả
7.2.1 Kịch bản mô phỏng
Mạng bao gồm 25 nút ( từ nút 0 cho tới nút 24), đặt trên một hình vuông kích thước 100x100m. Mỗi nút cách nhau 25 m.
0 5 10 15 20
1 6 11 16 21
2 7 12 17 22
3 8 13 18 23
4 9 14 19 24
Path 4
Path 2
Path 0 Nguồn Nguồn Nguồn
Sink UDP/CBR
UDP/CBR
UDP/CBR
25 m 100 m
100 m
Hình 7.3: Sơ đồ phân bố các nút trong mạng
Trong các kịch bản mô phỏng sẽ thực hiện trên 3 đường đi:
• Path 0: Nút 0 sẽ gửi các gói tin tới nút 22, trên đường đi các gói tin sẽ đi qua lần lượt các nút 5, 10, 11, 12, 17. Các nút này đóng vai trò là router chuyển tiếp gói tin.
Nguồn Sink
Path 0 0 5 10 11 12 17 22
UDP/CBR
• Path 4: Nút 4 sẽ gửi các gói tin tới nút 22, trên đường đi các gói tin sẽ đi qua lần lượt các nút 9, 14, 13, 12, 17. Các nút này đóng vai trò là router chuyển tiếp gói tin.
Nguồn Sink
Path 4 4 9 14 13 12 17 22
UDP/CBR
• Path 2: Nút 2 sẽ gửi các gói tin tới nút 22, trên đường đi các gói tin này sẽ đi qua lần lượt các nút 7, 12, 17. Các nút này đóng vai trò là router chuyển tiếp gói tin.
Nguồn Sink
Path 2 2 7 12 17 22
UDP/CBR
Có 3 kịch bản mô phỏng được sử dụng:
• Kịch bản 1: Sử dụng hàng đợi Droptail
• Kịch bản 2: Sử dụng hàng đợi PriQ
• Kịch bản 3: Sử dụng hàng đợi Multiserv Tham số nào sẽ thay đổi
Các tham số được thay đổi bao gồm:
• Mức ưu của gói tin
• Kích thước gói tin
• Tốc độ truyền tin
• Số nút trên một đường truyền tin