TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG
DOANH NGHIỆP

Dưới đây là bài báo khoa học “Định Tuyến Theo Giá Tối Thiểu Trên Mạng Cảm Nhận Không Dây” của ThS.Nguyễn Trọng Thể - Khoa Công nghệ thông tin, Đại học Dân lập Hải Phòng.

Abstract

Routing techniques for WNS is to forward sensing data of a node to base station. This paper, we present a new routing scheme based on the minimum of distance according to the intensity of the signal energy of node. Experimental results, the proposed scheme has better performance compared with the previous algorithm in the tree structured routing, in terms of network deployment is not complicated, and node’s memory is not required too large.

1. Định tuyến trong mạng cảm nhận không dây

Có nhiều loại giao thức định tuyến cho mạng cảm nhận không dây (WSN –Wireless Sensor Network) [2-4], phổ biến nhất là nhóm giao thức bình đẳng và nhóm giao thức phân cấp. Trong nhóm giao thức bình đẳng các nút mạng bình đẳng và hoạt động động lập với nhau, ngược lại trong nhóm giao thức phân cấp, một nút mạng sẽ giữ vai trò điều khiển hoạt động của các nút trong bán kính phủ sóng của nó. Mặc dù WSN được triển khai nghiên cứu gần ba thập kỷ, đã có nhiều công trình về định tuyến được đề xuất, nhưng đến nay nó vẫn là chủ đề được gới nghiên cứu quan tâm [1]. Từ thực tế của WSN, luồng dữ liệu thường hướng về trạm cơ sở, các nút mạng không cần có định danh riêng và bảng định tuyến, mỗi nút chỉ cần xác định giá nhỏ nhất được hiểu theo số liên kết tối thiểu từ nó tới trạm cơ sở. Mỗi gói tin mà nút mạng chuyển đi là gói tin quảng bá tới các nút láng giềng của nó. Khi một nút nhận được gói tin, nó kiểm tra giá trên gói tin để biết mình có nằm trên tuyến tối ưu hay không, nếu đúng nó sẽ quảng bá tiếp gói tin này tới các nút láng giềng. Quá trình được lặp lại ở các nút khác cho tới khi gói tin đến trạm cơ sở.

2. Các công việc liên quan

Vi mạch tích hợp CC1010[5] là nút mạng để truyền, nhận thông tin cảm nhận được, ví dụ nhiệt độ môi trường. Dữ liệu cảm nhận được tại nút đó, chuyển tiếp về nút cơ sở.  Nút trạm cơ sở được nối với máy tính qua để  lưu trữ, xử lý và hiển thị dữ liệu. Theo [2] định dạng gói tin gồm 5 trường: ID, Cost, Data, HS và Tracert. Trong đo: trường ID là định danh của nút mạng, dùng cho mục đích hiển thị hoạt động của từng nút mạng và theo vết của gói tin. Trường Cost là giá của gói tin, dùng cho mục đích quảng bá giá và xử lý chuyển tiếp gói tin về nút cơ sở. Trường Data là giá trị dữ liệu ví dụ nhiệt độ tại nút mạng nguồn. Trường HS là hiệu suất, dùng đánh giá một phần hiệu suất gửi tin của nút cơ sở và nút mạng. Trường này chứa số thứ tự của gói tin mà nó đã gửi. Trường Tracert là theo vết, chứa thông tin về những nút mạng mà gói tin đã đi qua. Trong thực tế 2 trường HS, Tracert có thể bỏ qua, nhưng để đánh giá hoạt động của giao thức, chúng tôi thêm 2 trường này giúp tường minh trong quá trình dữ liệu di chuyển trên mạng, qua đó đánh giá giao thức.

3. Định tuyến theo giá tối thiểu

Thoạt đầu mỗi nút phải xác định giá tối thiểu từ nó tới nút trạm cơ sở. Muốn vậy nút cơ sở khởi phát Bản tin quảng bá giá với giá bằng 0, trong khi các nút mạng khác có giá mặc định ban đầu là vô cùng. Mỗi nút mạng khi nhận được gói tin quảng bá từ trạm cơ sở, sẽ so sánh giá của nó với tổng giá, bao gồm giá của bản tin quảng bá cộng với giá của tuyến liên kết mà nó vừa nhận. Nếu tổng giá nhỏ hơn thì giá của nút được cập nhật bằng tổng giá và bản tin tiếp tục được quảng bá. Nếu tổng giá lớn hơn, gói tin bị bỏ qua. Để các nút trên mạng không nhận các gói tin quảng bá giá trùng lặp, đặc biệt các nút ở xa, một thủ tục được thêm vào để một nút không gửi bản tin quảng bá nếu thông số  A*Lcost­­­ lớn hơn một ngưỡng đặt trước, trong đó L­­­cost là giá của liên kết tại nút đó, còn A là thông số được xác định bằng thực nghiệm.

a.Thuật toán hoạt động của nút cơ sở:

Hoạt động của nút cơ sở được chia làm 2 pha: pha nhận dữ liệu và pha quảng bá giá. Số lần quảng bá giá của nút cơ sở tỉ lệ với xác suất thay đổi cấu hình của mạng, được xác định bởi người thiết kế, dựa trên đặc điểm của từng ứng dụng. Gói tin quảng bá có dạng như sau:

Hình 1: Thuật toán tại nút cơ sở 

Hình 2: Thuật toán tại nút mạng

Trong hình 1. trên Nr là một hằng số cho trước mô tả số lần nhận gói tin và số lần quảng bá giá, ở đây Nr chọn bằng 500.

ID = 1 chỉ ra gói tin này là gói tin quảng bá do nút cơ sở khởi phát. COST = 0, giá khởi phát ban đầu là 0. TRACERT = 1, cho biết gói tin đi qua nút 1.

Trong pha nhận dữ liệu, nút cơ sở nhận, xử lý và hiển thị: gói dữ liệu có khung ID nút, giá trị dữ liệu, số thứ tự của gói tin và những nút trung gian nào gói tin đã đi qua. Ví dụ một gói tin mà nút cơ sở nhận được có các thông tin sau:

Ý nghĩa gói tin này mang là: Gói tin này xuất phát từ ID = 4 Dữ liệu nhiệt độ tại ID 4 lúc đó là 9^oC, đây là gói tin thứ 87 mà ID 4 gửi đi, Gói tin này đi từ: ID 4 -> ID 2 -> ID 1

b.Thuật toán hoạt động tại nút mạng bất kỳ

Các ký hiệu trong hình 2 này có nghĩa như sau: Ccost = giá hiện tại, Ncost = giá của gói quảng bá giá, Icost = giá của gói tin nhiệt độ tới. Hoạt động của một nút mạng được chia làm 2 pha là gửi dữ liệu tại chính nó về nút cơ sở và chuyển tiếp các gói tin từ các nút khác. Thí dụ, pha gửi dữ liệu từ nút 4, định dạng của gói tin là:

Trong pha chuyển tiếp dữ liệu, có 2 khả năng xảy ra: gói tin tới là gói tin quảng bá giá hoặc gói tin chuyển tiếp về nút cơ sở.

Trong trường hợp là gói tin quảng bá giá thì ID = 1, nút kiểm tra giá trên gói tin và so sánh với giá hiện tại của nó, nếu giá tới tối ưu hơn giá hiện tại (nhỏ hơn) nó sẽ thay thế và chuyển tiếp gói tin này đi. Trong trường hợp ngược lại giá mới không tối ưu, gói tin quảng bá giá bị bỏ qua.

Trong trường hợp là gói tin chuyển tiếp (ID ≠ 1), nút kiểm tra giá trên gói tin và so sánh với giá của nó, nếu nằm trên tuyến tối ưu thì nó sẽ giảm giá của gói tin tới đi 1, thêm nó vào trường TRACERT và tiếp tục chuyển tiếp gói tin này. Khi mạng quy mô lớn, nút mạng có thể gặp những gói tin quảng bá trùng lặp, đặc biệt các nút xa nút cơ sở. Cần thêm một thông số hạn chế tình huống này, đó là thông số A*Lcost, tương tự thông số TTL trong gói tin IP. Với Lcost là giá của nút, A là hằng số xác định bằng thực nghiệm, được đặt bởi người quản trị, khi tích này vượt một ngưỡng nào đó thì gói tin quảng bá giá sẽ không được chuyển tiếp.

4. Các kết quả thử nghiệm

a.Truyền đơn bước

Với 2 nút mạng, thuật toán hoạt động hoàn hảo: một nút nạp chương trình nút cơ sở với ID=1, nút còn lại nạp chương trình nút cảm nhận với ID = 2. Thoạt đầu để nút 2 ở sát nút 1 và cho hai nút cùng hoạt động, cứ sau một khoảng thời gian 2 phút, lại di chuyển nút 2 ra xa nút cơ sở 10m. Kết quả thu được như sau: khi nút mạng đặt gần nút cơ sở hiệu suất nhận gói tin của nút cơ sở là 100% và giảm dần khi di chuyển nút mạng ra xa, nút cơ sở không nhận được gói tin từ ID 2 khi nó ra ngoài bán kính phủ sóng của nút cơ sở (ước chừng 150m). Như vậy, hiệu suất nhận gói tin của nút cơ sở tỉ lệ nghịch với khoảng cách từ nó tới nút mạng.

b.  Truyền đa bước

Mạng được bố trí như hình 3. Nút ID4 nằm ngoài vùng phủ sóng của nút cơ sở. Như vậy ID 4 gửi dữ liệu về nút cơ sở phải qua nút trung gian ID 2, hoặc ID 3.

Hình 3: Truyền đa bước (trước khi quảng bá giá)

Kết quả: dữ liệu tại nút cơ sở là gói tin từ ID 3, trường TRACERT của gói tin có 2 chỉ thị khác nhau: 31 và 321. Điều này có nghĩa là gói tin từ ID 3 đi trực tiếp tới nút cơ sở và gói tin từ ID 3 được gửi qua nút trung gian ID 2    ( Trường TRACERT là 321). Nút cơ sở cũng nhận được gói tin từ ID 4, trường TRACERT của gói dữ liệu chỉ thị các số 431 và 4321. Như vậy, từ ID 4 dữ liệu chuyển qua ID 3 tới ID 1 hoặc chuyển qua hai nút trung gian ID 3 và ID 2. Số gói tin do ID 3 gửi nhận được tại nút cơ sở nhiều hơn số gói tin do ID 4 gửi tới.

Kết quả thu được trong thử nghiệm này cho thấy việc quảng bá giá thành công, giá của các nút tỉ lệ tương ứng với khoảng cách của nó tới nút cơ sở. Từ kết quả thu được cho phép vẽ mô hình mạng với các giá được cập nhật sau khi quảng bá giá:

5. Kết luận

Định tuyến với giá tối thiểu hoạt động đơn giản, không quá phức tạp trong khâu xử lý và không đòi hỏi dung lượng bộ nhớ lớn. Việc định tuyến của các nút dựa trên giá từ nó về nút cơ sở, không đòi hỏi cập nhật thông tin thường xuyên và không cần duy trì bảng định tuyến phức tạp. Với định tuyến giá tối thiểu đã hạn chế được một lượng lớn gói tin không cần thiết hướng ra ngoài mạng. Với các phương pháp định tuyến khác, dù nút mạng không nằm trên tuyến tối ưu thì gói tin vẫn yêu cầu được chuyển tiếp.

Tuy nhiên phương pháp này cũng có những nhược điểm như khả năng xung đột cao, đặc biệt với đối tượng theo dõi theo kiểu sự kiện. Khó dàn đều việc tiêu thụ năng lượng giữa các nút, điều đó ảnh hưởng tới thời gian sống của toàn mạng. Hiệu suất chuyển tiếp các gói tin thấp đối với các nút ở xa nút cơ sở.

Để phát triển thuật toán định tuyến tốt phải nhìn nhận rằng có những hạn chế trong nhóm giao thức định tuyến bình đẳng như xung đột dữ liệu, kiểm soát năng lương chưa đủ mạnh, xác suất gửi thành công gói tin không kiểm soát được. Giải pháp là kết hợp giao thức định tuyến giá tối thiểu với định tuyến phân cấp. Kết hợp sự đơn giản của định tuyến theo giá và sự hiệu quả của định tuyến phân cấp về tiêu thụ năng lượng và tránh xung đột. Đó là hướng nghiên cứu định tuyến cho mạng WSN trong tương lai.

Tài liệu tham khảo

1.Al-Karaki, J.N.; Kamal, A.E.; , "Routing techniques in wireless sensor networks: a survey," Wireless Communications, IEEE , vol.11, no.6, pp. 6- 28, Dec. 2004

2. Uddin, M.Y.S.; Akbar, M.M.; , "Addressing Techniques in Wireless Sensor Networks: A Short Survey," Electrical and Computer Engineering, 2006. ICECE '06. International Conference on , vol., no., pp.581-584, 19-21 Dec. 2006

3.Guofang Nan; Minqiang Li; , "Evolutionary Based Approaches in Wireless Sensor Networks: A Survey," Natural Computation, 2008. ICNC '08. Fourth International Conference on , vol.5, no., pp.217-222, 18-20 Oct. 2008

4.Lambrou, T.P.; Panayiotou, C.G.; , "A Survey on Routing Techniques Supporting Mobility in Sensor Networks," Mobile Ad-hoc and Sensor Networks, 2009. MSN '09. 5th International Conference on , vol., no., pp.78-85, 14-16 Dec. 2009

5.Chatzimilioudis, G.; Cuzzocrea, A.; Gunopulos, D.; , "Optimizing Query Routing Trees in Wireless Sensor Networks," Tools with Artificial Intelligence (ICTAI), 2010 22nd IEEE International Conference on , vol.2, no., pp.315-322, 27-29 Oct. 2010

6. Vương Đạo Vy, Nguyễn Thế Sơn, “To Buid Up And Test The Data Transceiving From Wireless Sensor Nodes Base On The Tree-Base Routing Algorithm With the Master-Slave”, Configuration, 2006.

7. CC1010 Datasheet, Texas instruments, 2003-2004, Chipcon AS, URL: http://www.chipcon.com

Nội dung đính kèm: download