THUYẾT MINH ĐỀ TÀI

KHOA HỌC VÀ CÔNG NGHỆ CẤP BỘ

1. TÊN ĐỀ TÀI

Xây dựng công cụ mô phỏng các thuật toán định tuyến mạng không dây ứng dụng nghiên cứu khắc phục hố mạng trong môi trường địa hình phức tạp

3. LĨNH VỰC NGHIÊN CỨU

Tự nhiên		Kỹ thuật	X	Môi trường
Kinh tế; XH-NV		Nông Lâm		ATLĐ
Giáo dục		Y Dược		Sở hữu trí tuệ

4. LOẠI HÌNH NGHIÊN CỨU

Cơ bản		Ứng dụng		Triển Khai
	X		X

5. THỜI GIAN THỰC HIỆN 24 tháng

                             Từ tháng   1   năm   2013      đến  tháng  12    năm 2014

6. CƠ QUAN CHỦ TRÌ ĐỀ TÀI

Tên cơ quan:  Trường Đại học Bách Khoa Hà nội

Địa chỉ:          Số 1, Đại Cồ Việt, Q. Hai Bà Trưng, tp. Hà Nội

7. CHỦ NHIỆM ĐỀ TÀI

           Họ và tên:      Nguyễn Khanh Văn    

E-mail: vannk@soict.hut.edu.vn

Học vị:  TS.

8. NHỮNG THÀNH VIÊN THAM GIA NGHIÊN CỨU ĐỀ TÀI

TT

Họ và tên

Đơn vị công tác và

lĩnh vực chuyên môn

Nội dung nghiên cứu cụ thể   được giao

Chữ ký

1

NCS. Nguyễn Phi Lê

Bộ môn Công nghệ Phần mềm – Viện Công nghệ Thông tin và Truyền thông – Đại học Bách khoa Hà Nội

- Nghiên cứu khảo sát các hệ thống mô phỏng NS2,

- Nghiên cứu thuật toán định tuyến thông minh, tiết kiệm năng lượng

- Nghiên cứu các kỹ thuật trong đảm bảo cân bằng tải

9. ĐƠN VỊ PHỐI HỢP CHÍNH

Tên đơn vị

trong và ngoài nước

Nội dung phối hợp nghiên cứu

Họ và tên người đại diện đơn vị

Khoa Công nghệ Thông tin, Đại học Công nghệ, ĐH Quốc gia Hà Nội

Trao đổi về các phương pháp thiết kế thuật toán định tuyến địa lý trong mạng cảm biến không dây, các kỹ thuật tránh tắc ngẽn và vấn đề xác định biên hố mạng hiệu quả

TS. Nguyễn Đại Thọ

10.  TỔNG QUAN TÌNH HÌNH NGHIÊN CỨU THUỘC LĨNH VỰC CỦA ĐỀ TÀI Ở TRONG VÀ NGOÀI NƯỚC

10.1. Ngoài nước (phân tích, đánh giá tình hình nghiên cứu thuộc lĩnh vực của đề tài trên thế giới, liệt kê danh mục các công trình nghiên cứu, tài liệu có liên quan đến đề tài được trích dẫn khi đánh giá tổng quan)

(i) Nghiên cứu về các công cụ mô phỏng mạng máy tính:

Trong nghiên cứu đề xuất thuật toán mới trong mạng máy tính, việc kiểm tra đánh giá bằng thực nghiệm thông qua mô phỏng là hết sức quan trọng. Vì chi phí thực nghiệm trực tiếp trong thực tế thường là rất cao, nên thực nghiệm mô phỏng là cách duy nhất để đảm bảo nghiên cứu có tính thực tiễn đáng tin cậy mà tránh được chi phí lớn. Hệ thống mô phỏng cần đảm bảo các yếu tố cơ bản sao cho sát thực nhất, tương tự như một thực tiễn với qui mô thu nhỏ. Để hỗ trợ cho mô phỏng các hệ thống mạng, trên thế giới, đã có nhiều nghiên cứu tập trung vào xây dựng công cụ mô phỏng hệ thống mạng với các hệ công cụ nổi tiếng như NS2 [1,2,3], OMNET++ [4], OpNET [5] ,… 

NS2 (Network simulator version 2) là một công cụ mô phỏng mạng phổ biến nhất với hơn 45% các nhà nghiên cứu sử dụng. NS2 được phát triển tại trường đại học UC Berkely, với phiên bản đầu tiên bắt đầu từ năm 1989. Nó sử dụng cơ chế điều khiển sự kiện rời rạc hướng đối tượng (object-oriented discrete event simulator) để thực hiện quá trình mô phỏng. NS2 được viết dựa trên hai ngôn ngữ lập trình, C++ và OTcl, trong đó, C++ được dùng để xây dựng phần lõi hệ thống, thực hiện các giao thức và mở rộng thư viện NS2. Trong khi đó, là một ngôn ngữ bậc cao (kiểu script) hướng đối tương, OTcl được dùng để tạo kịch bản và điều khiển môi trường mô phỏng (như việc quy định định dạng các thông tin đầu vào, đầu ra, …). Một trong những ưu điểm nổi bật của NS2 là được thiết kế khá mở, cho phép những người sử dụng chuyên gia có thể mở rộng, tích hợp thêm cac module chuyên dụng mới.

NS2 cung cấp một thư viện các giao thức truyền thông khá phong phú ở tất cả các tầng như: tầng MAC (Ethernet, 802.11); tầng internet (các giao thức định tuyến như AODV, DSR, Dijktra, …); tầng chuyển vận (TCP, UDP); tầng ứng dụng (FTP, Telnet, http, …). NS2 hỗ trợ khá tốt cho các mạng có dây và một số mạng không dây truyền thống do những thế hệ mạng này đã ra đời từ lâu và hoạt động theo những bộ giao thức chuẩn cố định.

Tuy nhiên, mạng cảm biến không dây là một thế hệ mạng mới với các ứng dụng rất phong phú, trong đó các giao thức được sử dụng cho các node mạng thường được thiết kế theo đặc trưng của từng ứng dụng cụ thể chứ không tuân theo một chuẩn nhất định. Hiện tại, NS2 hỗ trợ rất ít các giao thức được sử dụng trong mạng cảm biến không dây. Chẳng hạn, các lớp giao thức hiện đại hơn như định tuyến địa lý, định tuyến hướng dữ liệu đều không được hỗ trợ bởi NS2. Ngoài ra, các định dạng của gói tin, mô hình năng lượng, hay các mô hình cảm biến hiện tại trong NS2 cũng không phù hợp với mạng cảm biến không dây. Chính vì những hạn chế trên đây, các nhóm nghiên cứu khi muốn thử nghiệm một giải thuật mới đều phải tự mình phát triển các công cụ riêng (adhoc) rồi tích hợp vào nền NS2. Cho đến nay, đã có một số công trình nghiên cứu mở rộng NS2 nhằm giải quyết các vấn đề nêu trên như [7,8]. Trong các nghiên cứu này, các tác giả đã phát triển thêm một số module như năng lượng, cảm biến, ….Tuy nhiên, các nghiên cứu này vẫn còn nhiều tồn đọng chưa được giải quyết; ví dụ: khó sử dụng, không linh hoạt, số lượng giao thức hỗ trợ còn rất hạn chế.

OMNET++ là một công cụ mô phỏng phổ biến khác sử dụng các sự kiện rời rạc dựa trên các hợp phần (component-based discrete event simulator). OMNET++ sử dụng triệt để mô hình lắp ghép các module, mỗi module có thể phát triển độc lập, thực hiện một tác vụ mô phỏng cụ thể. Mỗi module có thể được định nghĩa dưới dạng module đơn giản hoặc module tổng hợp. Trong đó module đơn giản được sử dụng để định nghĩa các giao thức, thuật toán, còn module tổng hợp là một tập hợp của các module đơn giản. Các module giao tiếp với nhau thông qua các bản tin. Mô hình hỗ trợ mạng cảm biến không dây trong OMNET++ được gọi là SensorSim. SensorSim mô phỏng khá tốt phần cứng của các node mạng cảm biến, tuy nhiên lại hỗ trợ khá ít ỏi các giao thức truyền thông. Chính vì vậy, khi người dùng muốn mô phỏng mạng cảm biến không dây dựa trên OMNET++, thì phải tự viết phần lớn các giao thức. Đây chính là một trong những nguyên nhân khiến cho OMNET++ ít được chọn để mô phỏng mạng cảm biến không dây.

Trong khi NS2, OMNET++ là các công cụ mô phỏng miễn phí thì bộ công cụ OpNET lại là phần mềm thương mại. OpNet cũng là một công cụ mô phỏng hướng đối tượng dựa trên các sự kiện rời rạc. Khác với NS2, OpNET hỗ trợ việc mô phỏng các bộ phận cụ thể trong phần cứng của các node mạng cảm biến như: bộ phận thu phát (physical –link transceiver) hay ăng-ten. OpNET cũng cho phép người dùng được thay đổi định dạng của gói tin và hỗ trợ giao diện đồ họa, giúp người dùng dễ dàng trong việc thiết lập mô phỏng và xứ lý hậu mô phỏng. Tuy nhiên, cũng giống như NS2 và OMNET++, OpNET hỗ trợ rất ít các giao thức truyền thông trong mạng cảm biến không dây. Và bởi vì là một phần mềm thương mại, OpNET không được sử dụng rộng rãi như NS2 và OMNET++.

(ii) Nghiên cứu về các thuật toán định tuyến trong mạng cảm biến không dây:

Cùng với sự phổ cập của mạng không dây và sự phát triển của công nghệ vi xử lý, mạng cảm biến không dây ngày càng trở nên phổ biến và có những ứng dụng quan trọng ở khắp các lĩnh vực: từ nông nghiệp (theo dõi nhiệt độ, độ ẩm, …) đến công nghiệp (giám sát rung, đo khoảng cách, …); từ quân sự (thu thập thông tin chiến địa, …) đến dân sinh (chăm sóc sức khỏe, tòa nhà thông minh …) [9]. Nghiên cứu về mạng cảm biến không dây trở nên quan trọng và thu hút được sự quan tâm trong những năm gần đây.

Khác với các thế hệ mạng truyền thống, mạng cảm biến không dây được đặc trưng bởi sự hạn chế về năng lượng và khả năng xử lý của các node mạng cũng như sự phức tạp của topo mạng [10]. Một chủ đề quan trọng trong nghiên cứu về mạng cảm biến không dây là tìm ra các cơ chế lưu trữ thông tin hiệu quả và các giao thức định tuyến phù hợp với các đặc trưng này.

Một trở ngại lớn trong việc thiết kế các giao thức định tuyến trong mạng cảm biến không dây là sự xuất hiện của các “hố mạng”, tức là các vùng không tồn tại các node mạng cảm biến hoặc nếu có thì không còn khả năng hoạt động [11]. Các hố mạng có thể được tạo ra do những đặc điểm địa lý cố hữu của vùng triển khai tức là có vật cản thiên nhiên như sông, núi, ao, hồ, hay do sự phá hủy bởi các tác động bên ngoài, có thể do thiên tai (động đất, sóng thần, …), hoặc do chính các node mạng bị cạn kiệt năng lượng sau quá trình làm việc liên tục. Hố mạng là yếu tố thường xuyên xuất hiện trong mạng cảm biến không dây đặc biệt là đối với những mạng triển khai ở những môi trường địa hình phức tạp.

Bài toán xác định hố mạng được đề xuất đầu tiên bởi QingFang trong nghiên cứu [12]. Ở nghiên cứu này, tác giả trước hết đưa ra một phương pháp “phẳng hóa” đồ thị topo mạng (planarization) rồi xác định hình dạng hố mạng như là một đa giác với các đỉnh là các node mạng cảm biến nằm trên biên hố. Việc xác định hố mạng được thực hiện bằng cách cho một gói tin truyền theo quy tắc bàn tay phải xung quanh hố để thu thập thông tin của các node mạng trên biên hố. Một số các nghiên cứu khác cũng đề cập đến vấn đề xác định biên hố như [13, 14,15].

Để giải quyết bài toán định tuyến khi gặp hố mạng, phương pháp truyền thống là hướng dẫn các gói tin truyền men theo biên hố. Phương pháp này được gọi lại định tuyến vành đai, được đề xuất bởi B.Karp and H. T. Kung vào năm 2000 [16]. Nhiều nghiên cứu khác đã được tiếp tục phát triển theo phương pháp định tuyến vành đai [17,18,19,20]. Tuy nhiên phương pháp này có một nhược điểm lớn là làm cho giao thông tại các node trên biên hố cao hơn nhiều các vùng khác, dẫn tới tình trạng tắc nghẽn quanh biên hố. Ngoài ra, nó cũng làm cho các node trên biên hố nhanh chóng bị cạn kiệt năng lượng, trở thành các node chết. Từ đó, topo mạng sẽ bị thay đổi do sự phình to ra của các hố đã có hoặc sự phát sinh của hố mới.

Để giải quyết bài toán tắc nghẽn trên biên hố, đã có một số nghiên cứu được tiến hành như [21,22,23,24,25]. Tư tưởng phổ biến ở trong các nghiên cứu [21,22,23] là định nghĩa một vùng bao xung quanh hố thực tế; từ đó, khi gói tin được truyền tới lân cận của vùng bao này, nó sẽ được hướng dẫn tránh xa hố thay vì đi men theo biên hố. Phương pháp này tuy giải quyết được vấn đề tắc nghẽn trên biên hố ban đầu nhưng thực chất nó lại tạo nên một vùng tắc nghẽn mới xung quanh vùng bao. Ngoài ra, nó còn có xu hướng kéo dài đáng kể đường truyền của gói tin và gia tăng sự hao phí tài nguyên đối với các node mạng.

Nhóm nghiên cứu [24,25] đề xuất một cơ chế nhằm duy trì sự cân bằng tải giữa các node mạng thông qua phương pháp tự học. Ở đó, các node mạng sẽ có thông tin về mức năng lượng còn lại của các node lận cận và việc định tuyến sẽ được quyết định dựa trên cả thông tin về vị trí và thông tin về năng lượng. Cơ chế này có thể giải quyết khá tốt vấn đề cân bằng tải giữa các node mạng nói chung và vấn đề tắc nghẽn trên biên hố nói riêng, nhưng nó lại gây ra sự tiêu tốn tài nguyên, năng lượng tương đối đáng kể của node mạng cho việc trao đổi thông tin lẫn nhau phổ khắp.

Danh sách các nghiên cứu liên quan:

[1] The Network Simulator –ns-2. http://www.isi.edu/nsnam/ns/ .

[2] I. Downard, Simulating Sensor Networks in ns-2. NRL Formal Report 5522. April, 2004.

[3] V. Naoumov and T. Gross. Simulation of Large Ad Hoc Networks. ACM MSWiM, 2003.

[4] C. Mallanda, A. Suri, V. Kunchakarra, S.S. Iyengar, R. Kannan, and A. Durres.  Simulating Wireless Sensor Networks with OMNeT++.

[5] X. Chang. Network Simulations with OPNET.

[6] Y. Pan. Introduction to OPNET Simulator.

[7] S. Park, A. Savvides, and M. B. Srivastava. SensorSim: A Simulation Framework for Sensor Networks. ACM MSWiM, August, 2000.

[8] A. M. Abu-Mahfouz, G. P. Hancke. NS-2 Extension to Simulate Localization System in Wireless Sensor Networks. IEEE Africon 2011, September, 2011.

[9] C. F. Garcia-Hernandez, P. H. Ibarguengoytia-Gonzalez, J. Garcia-Hernandez, and J. A. Perez-Diaz. Wireless Sensor Networks and Applications: a Survey. IJCSNS Int 264 International Journal of Computer Science and Network Security, 7(3):264–273, 2007.

[10] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. Wireless sensor networks: a survey. Computer Networks, 38:393–422, 2002.

[11] N. Ahmed, S. S. Kanhere and S. Jha, "The Holes Problem in Wireless Sensor Networks: A Survey, ACM SIGMOBILE Mobile Computing and Communications Review, vol. 9, pp. 4 - 18, 2005.

[12] Q. Fang, J. Gao, and L. J. Guibas. Locating and Bypassing Routing Holes in Sensor Networks. In Proc. of  INFOCOM’04, 2004.

[13] A. Kroller, SA˛Eandor, P. Fekete, D. Pfisterer, and S. Fischer. Deterministic Boundary Recognition and Topology Extraction for Large Sensor Networks. In in Proc. of SODA’06, the seventeenth annual ACM-SIAM symposium on Discrete algorithm.

[14] Y. Wang, J. Gao, and J. S.B. Mitchell. Boundary Recognition in Sensor Networks by Topological Methods. In Proc. of MobiCom ’06, the 12th annual international conference on Mobile computing and networking.

[15] S. Lederer, Y. Wang, and J. Gao. Connectivity-based Localization of Large-scale Sensor Networks with Complex Shape. ACM Transactions on Sensor Networks (TOSN), 5, 2009.

[16] B. Karp and H. T. Kung. GPSR: Greedy Perimeter Stateless Routing for Wireless Networks. In Proc. of MOBICOM’00, pages 243–254, 2000.

[17] P. Bose, P. Morin, I. Stojmenovir, and J. Urrutia. Routing with guaranteed delivery in ad hoc wireless networks. In 5^th IEEE International Conference, pages 347–352, 2008.

[18] F. Kung, R. Wattenhofer, and A. Zollinger. Asymptotically Optimal Geometric Mobile Ad hoc Routing. In Dial-M, 2002.

[19] F. Kung, R. Wattenhofer, and A. Zollinger. Worst-Case Optimal and Average-Case Efficient Geometric Ad-hoc Routing. In Proc. of ACM MobiHoc, 2003.

[20] F. Kung et al. Geometric Ad-hoc Routing: Of Theory and Practice. In Proc. of ACM PODC, 2003.

[21] Y. Tian et al. Energy-Efficient Data Dissemination Protocol for Detouring Routing Holes in Wireless Sensor Networks. In Proc. of IEEE Intl. Conf. on Communications, ICC’08, pages 2322–2326, 2008.

[22] F. Yu et al. Efficient Hole Detour Scheme for Geographic Routing in Wireless Sensor  Networks. In Proc. of the 67^th IEEE Vehicular Technology Conference, VTC’08, pages 153–157, 2008.

[23] M. Choi and H. Choo. Bypassing Hole Scheme Using Observer Packets for Geographic Routing in WSNs. In Proc. of Intl. Conf. on Information Networking, ICOIN’11, pages 435–440, 2011.

[24] Y. Yu, R. Govindan, and D. Estrin. Geographical and Energy Aware Routing: A Recursive Data Dissemination Protocol for Wireless Sensor Networks. Technical report, 2001.

[25] K. Sha, J. Du, and W. Shi. Wear: A Balanced, Fault-tolerant, Energy-aware Routing Protocol in WSNs. IJSNet,1(3/4):156–168, 2006.

10.2. Trong nước (phân tích, đánh giá tình hình nghiên cứu thuộc lĩnh vực của đề tài ở Việt Nam, liệt kê danh mục các công trình nghiên cứu, tài liệu có liên quan đến đề tài được trích dẫn khi đánh giá tổng quan)

Tại Việt Nam, đã có nhiều công trình và đề tài nghiên cứu cũng các dự án phát triển và triển khai mạng cảm biến không dây cho ứng dụng thử nghiệm ở trong nước những năm vừa qua. Tuy nhiên, các tác giả của các công trình nghiên cứu ở trong nước mới chỉ quan tâm khai thác các công cụ có sẵn (mã nguồn mở hoặc thương mại) ở trên thế giới để phục vụ cho các công trình nghiên cứu mà chưa đề cập đến việc chủ động phát triển các công cụ hỗ trợ mô phỏng cho các cơ chế phức tạp và những giao thức nền tảng mạng cảm biến không dây, đặc biệt là bài toán định tuyến trong mạng đa bước (multi-hop) – một trong những vấn đề cơ bản của mạng cảm biến không dây.

Các tác giả trong [28], [33,34], [32], [30] đã tập trung nghiên cứu và phát triển kiến trúc tổng thể của mạng cảm biến không dây, trong đó hướng tới các kiến trúc mạng tiên tiến cho các ứng dụng cụ thể như trong nông nghiệp [32], trong giám sát môi trường [30]…  Trước những nhu cầu và tiềm năng to lớn về ứng dụng mạng cảm biến trong giám sát môi trường và cảnh báo thiên tai, gần đây, các tập đoàn lớn của Nhật Bản đã phối hợp với Bộ Thông tin và Truyền thông triển khai thử nghiệm hệ thống tích hợp mạng cảm biến không dây và công nghệ điện toán đám mây, ứng dụng cảnh báo phòng chống thiên tai tại một số địa phương của Việt Nam như tỉnh Cần Thơ, Đà Nẵng,…[36]. Tuy nhiên có thể thấy đây là công nghệ mạng cảm biến dựa trên trạm cơ sở với các công nghệ hoàn toàn do nước ngoài hỗ trợ, chi phí triển khai thử nghiệm là rất lớn nên khó có thể triển khai rộng rãi ở nước ta.

Về vấn đề định tuyến, các nhóm [29], [26] đã tiến hành nghiên cứu và có các công trình công bố tại các hội thảo quốc tế có uy tín được tổ chức ở Việt Nam. Trong đó, các tác giả đã đề cập đến bài toán định tuyến trong mạng cảm biến không dây sử dụng các thông tin bổ sung như mức năng lượng, thông tin vị trí địa lý,….Trong [29], nhóm tác giả sử dụng công cụ OMNET++ để mô phỏng và đánh giá giao thức định tuyến PEGASIS trong mạng cảm biến, trong đó chủ yếu sử dụng các module hỗ trợ mạng cảm biến có sẵn trong OMNET++. Trong [26], nhóm tác giả đã sử dụng công cụ mã nguồn mở NS-2 để tự xây dựng các giao thức định tuyến dựa trên thông tin địa lý. Việc tự xây dựng như vậy chiếm khá nhiều thời gian và công sức của nhóm nghiên cứu.

Ngoài vấn đề định tuyến, các công trình nghiên cứu còn tập trung một số vấn đề cơ bản khác của mạng cảm biến không dây như định tuyến hướng tới tiết kiệm năng lượng [35], [33,34]; Đánh giá hiệu quả các cơ chế của giao thức giao vận trong mạng cảm biến… [31]. Khả năng tiết kiệm năng lượng hiện là một tiêu chí cơ bản, không thể bỏ qua đối với mạng cảm biến không dây và cũng là vấn đề mà chúng tôi sẽ đề cập trong đề tài này.

Qua các khảo sát sơ bộ ở trên, có thể nhận thấy nhóm nghiên cứu ở trong nước hiện chưa tập trung đề cập đến các vấn đề mà đề tài này đang quan tâm hướng tới, đó là:

- Xây dựng các cơ chế, nguyên lý cơ bản phục vụ cho sự hoạt động của mạng định tuyến không dây trong các địa hình phức tạp, chẳng hạn các vùng trống xuất hiện trong mạng (hố mạng).

- Nghiên cứu và phát triển các công cụ phần mềm hỗ trợ mô phỏng các nguyên lý cơ bản trong mạng cảm biến không dây, đặc biệt là bài toán định tuyến.

Dựa trên các kết quả khảo sát nêu trên, gần đây nhóm nghiên cứu tại Viện CNTT&TT, ĐHBK Hà Nội đã bắt đầu quan tâm nghiên cứu vấn đề này và đã bước đầu công bố kết quả tại hội thảo khoa học quốc tế trong nước [27], trong đó nhóm đã tập trung giải quyết bài toán xấp xỉ biên hố trong mạng. Các vấn đề khác như việc sử dụng thông tin về hố mạng trong định tuyến, xây dựng công cụ hỗ trợ mô phỏng mạng sẽ được tiếp tục quan tâm trong đề tài này.

10.3. Danh mục các công trình đã công bố thuộc lĩnh vực của đề tài của chủ nhiệm và những thành viên tham gia nghiên cứu (họ và tên tác giả; bài báo; ấn phẩm; các yếu tố về xuất bản)

[1] Nguyen Phi Le, Nguyen Trung Hieu, Nguyen Khanh Van, “ELBAR: Efficient Load Balanced Routing Scheme for Wireless Sensor Networks with Holes”,  in Proc. of the 2012 Symposium on Information and Communication Technology, SoICT 2012, Halong, Viet Nam, August 23-24, 2012, ACM.

[2] Nguyen Phi Le, Bui Tien Quan, Nguyen Trung Hieu, Nguyen Khanh Van, “Efficient approximation of routing holes in wireless sensor networks”,  in Proc. of the 2011 Symposium on Information and Communication Technology, SoICT 2011, Hanoi, Viet Nam, October 13-14, 2011, ACM.

[3] Luan T. Bui and Van K. Nguyen, “GameGuard: A Windows-based Software Architecture for Protecting Online Games”, Symposium on Information and Communication Technology, SoICT 201, 1Hanoi, Vietnam, August 27-28, 2010

[4] Van Nguyen and Charles Martel, “Augmented Graph Models for Small-World Analysis with Geographic Factors”,  in Proc. of the Fifth ACM-SIAM Workshop on Analytic Algorithmics and Combinatorics (ANALCO), 2008

[5] Van Nguyen and Charles Martel “Designing Low Cost Networks with Short Routes and Low Congestion”, in Proc. of the 25th Annual IEEE Conference on Computer Communications (INFOCOM'06), 1-12, April, 2006

[6] Van Nguyen and Charles Martel,  “Analyzing and Characterizing Small-World Graphs”, in Proc. of the 16th ACM-SIAM Symposium on Discrete Algorithms, SODA'2005

[7] Charles Martel and Van Nguyen, “Analyzing Kleinberg's (and other) Small-World Models”, in Proc. of the 23rd ACM Symposium on Principles of Distributed Computing, PODC'2004

[8] N. P. Le, T. Morohashi, H. Imaizumi, and H. Morikawa, "A performance evaluation of energy efficient schemes for green office networks," in Proceedings of IEEE Green Technologies Conference, Texas, USA, pp. 1-9, April 2010.

11. TÍNH CẤP THIẾT CỦA ĐỀ TÀI

Trong nghiên cứu đề xuất thuật toán mới trong mạng máy tính, việc kiểm tra đánh giá bằng thực nghiệm thông qua mô phỏng là tối quan trọng. Vì chi phí thực nghiệm trực tiếp trong thực tế thường là rất cao, nên thực nghiệm mô phỏng là cách duy nhất để đảm bảo nghiên cứu có tính thực tiễn đáng tin cậy mà tránh được chi phí lớn. Hệ thống mô phỏng cần đảm bảo các yếu tố cơ bản sao cho sát thực nhất, tương tự như một thực tiễn với qui mô thu nhỏ. Để hỗ trợ cho mô phỏng các hệ thống mạng, trên thế giới, đã có nhiều nghiên cứu tập trung vào xây dựng công cụ hệ thống mô phỏng hệ thống mạng với các hệ công cụ nổi tiếng như NS2, OpNET, OmNET … 

Mô phỏng các thuật toán mạng không dây, đặc biệt là thuật toán định tuyến, là nhiệm vụ khó vì cần phải mô phỏng hoạt động song song của tâp hợp lớn các nút xử lý độc lập tham gia vào hệ thống mạng. Hệ công cụ NS2 là một trong số rất ít các nền tảng hàng đầu thế giới về mô phỏng mạng máy tính nhưng NS2 chưa có các hỗ trợ bậc cao thuận tiện cho mô phỏng giải thuật mạng không dây. Vì vậy, các nhóm nghiên cứu đề xuất giải thuật mới đều phải tự lực phát triển các mở rộng tích hợp trên nền NS2.  Lý do chọn NS2 là vì tính truyền thống, phổ biến của nó trong giới nghiên cứu học thuật và hoàn toàn miễn phí chứ không thương mại như OpNet, một hệ công cụ mô phỏng phổ biến khác. Việc sử dụng NS2 cũng là lợi điểm cho việc khai thác các kho thư viện phong phú đóng góp từ cộng đồng nghiên cứu rộng lớn.

So với mạng truyền thống, mạng cảm biến không dây có những mối quan tâm đặc thù về vấn đề tiết kiệm năng lượng và sự biến đổi thường xuyên của topo mạng. Nếu không đặc biệt chú ý về những hạn chế về năng lượng và khả năng tính toán của thiết bị cảm biến, các nút xử lý này sẽ nhanh chóng quá tải và “chết”, làm cho topo mạng thay đổi và tạo nên những “hố mạng” mới, hoặc làm phình to ra những hố có sẵn do địa hình tự nhiên phức tạp. Mô phỏng các mạng phức tạp này đặt ra những đòi hỏi nguồn lực nghiên cứu và chi phí tốn kém, tạo nên một thách thức lớn cho các nhóm nghiên cứu lĩnh vực này. 

12. MỤC TIÊU ĐỀ TÀI

Mục tiêu chính thứ nhất là phát triển mở rộng nền tảng NS2 để có được công cụ mô phỏng bậc cao cho thực nghiệm mô phỏng trong mạng không dây. Kết quả tốt theo mục tiêu này sẽ là đóng góp cho cộng đồng nghiên cứu, cả trong nước và thế giới, một giải pháp công cụ rất đắc lực cho vấn đề mô phỏng mạng không dây để phục vụ nghiên cứu các giải thuật phức tạp. Hiện nay mạng cảm biến không dây là một lĩnh vực nghiên cứu tương đối còn mới với ứng dụng thực tế rất đa dạng, được tập trung nghiên cứu mạnh, trong khi đó các công cụ mô phỏng bậc cao cho mạng cảm biến không dây còn chưa phát triển cao (cụ thể là chưa được hỗ trợ tốt trong NS2). Vì vậy chúng tôi sẽ tập trung nỗ lực để phát triển giải pháp công cụ mô phỏng bậc cao cho mạng cảm biến không dây. Cụ thể là, chúng tôi sẽ phát triển thêm các bộ thư viện mở rộng trên lõi hệ thống cung cấp chức năng mở rộng cho mạng không dây, và trên cơ sở đó, cung cấp phần mềm mô phỏng bậc cao chuyên dụng cho định tuyến trên mạng cảm biến không dây.

Một nhánh mở rộng của mục tiêu này là sự mở rộng của giải pháp để có thể cài đặt trên một nền tảng mô phỏng khác (ví dụ như OmNet). Ở đây mục tiêu không phải là tạo ra sản phẩm công cụ có tính hoàn thiện cao như với NS2 mà là những thư viện hỗ trợ cơ bản mà người sử dụng trực tiếp có thể tương đối dễ dàng mở rộng tùy biến để phù hợp với nhu cầu mô phỏng cụ thể.

Mục tiêu lớn thứ hai được xây dựng trên cơ sở triển khai bộ công cụ mạnh đã phát triển trong quá trình đầu. Ở đây, chúng tôi sẽ đề xuất và xây dựng các giải thuật định tuyến kiểu mới hiệu quả trong mạng cảm biến không dây trong môi trường phức tạp, địa hình xấu. Trước đây, các thuật toán định tuyến và xử lý tin theo tiếp cận truyền thống có thể sẽ vô tình tạo nên sự tập trung giao thông quá mức ở biên hố, làm cạn kiệt năng lượng các nút ở biên, khiến “hố” lan rộng ra. Chính vì vậy một tiếp cận mới, hợp lý hơn cần biết chú trọng đến các vấn đề tối ưu năng lượng và cân bằng tải, đặc biệt là trong môi trường địa hình xấu.

13. ĐỐI TƯỢNG, PHẠM VI NGHIÊN CỨU

13.1. Đối tượng nghiên cứu

Đối tượng thứ nhất là các nền tảng mô phỏng truyền thống như NS2 có kiến trúc hệ thống phức tạp, các modul đa dạng; bên cạnh đó là các phương pháp xây dựng công cụ mô phỏng mạng bậc cao trên cơ sở mở rộng nền tảng có sẵn. Đối tượng nghiên cứu thứ hai là các tiếp cận xây dựng thuật toán định tuyến trong mạng không dây, trong đó chúng tôi đặc biệt chú ý tới định tuyến địa lý hiệu quả trong mạng có môi trường địa hình phức tạp. 

13.2. Phạm vi nghiên cứu

Như tên và mục tiêu đề tài đã xác định rõ, trong khuôn khổ đề tài, chúng tôi sẽ khai thác và phát triển hệ thống môi trường mô phỏng mạng (NS2 là lựa chọn chính) và tập trung mở rộng theo hướng tạo công cụ mô phỏng bậc cao cho định tuyến trong mạng cảm biến không dây, có khả năng thực nghiệm các thuật toán định tuyến phức tạp. Bên cạnh đó là việc nghiên cứu đề xuất các thuật toán định tuyến thông minh có hiệu quả tiết kiệm năng lượng trong điều kiện môi trường địa hình phức tạp.

14. CÁCH TIẾP CẬN, PHƯƠNG PHÁP NGHIÊN CỨU

14.1. Cách tiếp cận

Chúng tôi đề xuất khảo sát rộng và sâu nền tảng mô phỏng NS2 đồng thời cũng khảo sát tương đối sâu các công cụ mô phỏng khác để hiểu rõ và so sánh đánh giá. Trên cơ sở hiểu biết sâu sắc về NS2 chúng tôi sẽ nắm bắt các tư tưởng kiến trúc cơ bản, cách thiết kế các tầng, lớp, modul  xuất phát từ phía trong lõi hệ thống ra đến khung giao diện ứng dụng bên ngoài. Từ đó sẽ phát hiện cách nối kết, để nhúng các lớp, modul mới phát triển thêm (của chúng tôi), thậm chí là ở phía trong lõi hệ thống.

Các môi trường hệ thống mô phỏng có nguyên tắc thiết kế hướng đối tượng tương đối giống nhau nên cách tiếp cận này cũng sẽ là tiếp cận chung để áp dụng với các hệ công cụ khác như OMNet++.

Ở góc độ nghiên cứu ứng dụng giải pháp công cụ của mình, chúng tôi tập trung nghiên cứu tìm cách khắc phục các hố mạng (thường sinh ra trong môi trường phức tạp) thông qua việc tìm hiểu các vấn đề như cơ chế nảy sinh và lan rộng, tắc ngẽn giao thông quanh hố và sự tiêu tốn năng lượng phát sinh không đáng có. Từ đó, cách tiếp cận có tính mới của chúng tôi là giải quyết hợp lý vấn đề giảm thiểu tiêu tốn năng lượng (đặc biệt khó khăn là trong môi trường địa hình xấu).

14.2. Phương pháp nghiên cứu

Chúng tôi đề xuất một hướng tiếp cận bằng định tuyến “thông minh” nhằm giải quyết các vấn đề liên quan đến định tuyến và tổ chức lưu trữ thông tin trong mạng không dây tại địa hình phức tạp.

Để thực hiện được hướng tiếp cận này, chúng tôi chú trọng sử dụng các tư tưởng thiết kế giải thuật định tuyến trên đồ thị với kích thước lớn, chỉ sử dụng tri thức địa phương. Về mặt phương pháp, chúng tôi thừa kế những nghiên cứu mang tính định hướng trước đây của chủ trì đề tài, TS. Nguyễn Khanh Văn, trong những nghiên cứu có tính chất nền móng, khai phá và ứng dụng mô hình mạng Thế giới Nhỏ (Smallwold Networks). Tư tưởng và kỹ thuật chính thừa kế từ đó là việc đảm bảo khai thác các thông tin topo địa phương một cách thông minh, do đó mặc dù hạn chế về tài nguyên vẫn đạt được hiệu quả định tuyến tương đối cao.

Công cụ mô phỏng của chúng tôi sẽ tạo điều kiện thử nghiệm mô phỏng các topo mạng phức tạp có bề mặt hố sinh một cách ngẫu nhiên và biến đổi dần, có kích thước lớn, phản ánh được tình huống phức tạp thường thấy trong thực tế.

15. NỘI DUNG NGHIÊN CỨU

Nội dung 1: Nghiên cứu khảo sát tổng thể các hệ thống môi trường mô phỏng mạng phổ biến

Nội dung 2: Xây dựng mô hình kiến trúc và đặc tả cho giải pháp phần mềm chuyên dụng cho mô phỏng định tuyến trên mạng không dây,  hướng tới nền NS2 và OmNET++

Nội dung 3: Xây dựng sản phẩm hệ phần mềm mở rộng trên nền NS2 tạo hỗ trợ bậc cao cho mô phỏng định tuyến mạng không dây

Nội dung 4: Nghiên cứu khảo sát thực trạng về định tuyến địa lý trong mạng không dây và các vấn đề đối phó hố mạng trong địa hình phức tạp.

Nội dung 5: Nghiên cứu đề xuất và thực nghiệm các thuật toán định tuyến khắc phục hố mạng có hiệu năng cao, tiết kiệm năng lượng

Nội dung 6: Ứng dụng mạng cảm biến để khảo sát xác định vùng bị thiên tai nặng thông qua việc nhanh chóng xác định hố mạng: nghiên cứu đề xuất thuật toán xác định nhanh hố kích thước lớn trong điều kiện địa hình liên tục biến động; đánh giá qua thực nghiệm mô phỏng. 

§ Bước đầu phát triển công cụ theo dõi trực quan hợp lý, hiệu quả