Nghiên cứu giải thuật định tuyến cân bằng tải nhằm nâng cao tuổi thọ cho mạng cảm biến không dây

Nội dung text: Nghiên cứu giải thuật định tuyến cân bằng tải nhằm nâng cao tuổi thọ cho mạng cảm biến không dây

1. NGHIÊN CỨU GIẢI THUẬT ĐỊNH TUYẾN CÂN BẰNG TẢI NHẰM NÂNG CAO TUỔI THỌ CHO MẠNG CẢM BIẾN KHÔNG DÂY RESEARCH LOAD BALANCING ROUTING ALGORITHM TO IMPROVE LIFETIME FOR WIRELESS SENSOR NETWORKS Nguyễn Thị Thu Trang Trường đại học sư phạm kỹ thuật TP. HCM TÓM TẮT Các điều kiện về môi trường, năng lượng, băng thông, bộ nhớ và khả năng xử lý trong mạng cảm biến không dây làm cho nó luôn là thách thức của những nhà nghiên cứu. Trong đó làm thế nào để duy trì tối đa tuổi thọ mạng là vấn đề cấn thiết. Bài báo này tập trung vào mô hình cân bằng tải với mức tiêu thụ năng lượng của các nút cảm biến của toàn mạng được phân bố đồng đều từ đó kéo dài tuổi thọ cho mạng cảm biến không dây. Qua các số liệu mô phỏng trên Matlab như sự phân bố năng lượng còn lại của các nút cảm biến khi có một nút cảm biến cạn kiệt năng lượng, sự thay đổi về bán kính phạm vi liên lạc hay số nút cảm biến trong một diện tích không đổi cũng như sử dụng mô phỏng Monte Carlo đã chứng minh được hiệu quả của phương án định tuyến cân bằng tải. Giải pháp được đề xuất là bổ sung thêm vào giải thuật định tuyến đường đi ngắn nhất với trọng số là tỉ lệ nghịch của năng lượng còn lại của mỗi nút cảm biến. Như vậy, việc một nút được lựa chọn là nút trung gian không chỉ dựa vào khoảng cách từ nút nguồn đến trạm gốc mà còn phụ thuộc vào năng lượng còn lại của nút đó. Từ khóa: Mạng cảm biến không dây, định tuyến cân bằng tải, định tuyến đường đi ngắn nhất. ABSTRACT Conditions of environment, energy, bandwidth, memory and processing capability in wireless sensor networks make it always a challenge of researchers. In particular, how to maintain the network's maximum lifetime is a necessary issue. This paper is focusing on load balancer models with energy consumption of sensor nodes are uniformly distributed to extend the life of wireless sensor network. Through the Matlab simulation data such as the distribution of the remaining energy of sensor nodes when a sensor node was energy depletion, the change in radius communication range or number of sensor nodes in a constant area, as well as using Monte Carlo simulations have demonstrated the effectiveness of the alternative load balancing routing. The proposed solution is added to the algorithm shortest path routing with weights that are inversely proportional to the residual energy of each sensor node. Thus, the selection of intermediate node is not only based on the distance from the source node to the base station but also depends on the remaining energy of the node. Keywords: wireless sensor network, load balancing routing, shortest path routing. I. GIỚI THIỆU thường xuyên dẫn đến sự cạn kiệt năng Có nhiều giao thức định tuyến nhận thức lượng của các nút cảm biến dọc theo những năng lượng được đưa ra trong [1], [2]. Một tuyến đường và dẫn đến phân vùng mạng. trong những giao thức nhận thức năng lượng Giao thức định tuyến đường đi ngắn nhất phổ biến nhất là định tuyến nhận thức năng SPR [3], [4] là giao thức cung cấp một lượng EAR đã được đề xuất trong [2]. Giao phương pháp đơn giản trong quá trình lựa thức định tuyến nhận thức năng lượng là chọn nút chuyển tiếp bằng cách liên kết giao thức tìm định tuyến có chi phí năng ngay lập tức với các nút lân cận có khoảng lượng thấp và sử dụng định tuyến đó cho tất cách ngắn nhất trong phạm vi liên lạc của cả quá trình truyền dẫn. Tuy nhiên, đây chúng. Đường định tuyến là đường ngắn không phải là phương án giải quyết tối ưu để nhất để các nút cảm biến chuyển các gói dữ tăng thời gian sống của mạng bởi vì việc sử liệu về trạm gốc và tránh được các vòng lặp. dụng định tuyến có chi phí năng lượng thấp Định tuyến đường đi ngắn nhất cũng giúp
2. cho các nút cảm biến tiết kiệm được năng Phương pháp định tuyến theo đường lượng trong quá trình chuyển gói dữ liệu. ngắn nhất xác định tuyến r nối nút n đến ni i Tuy nhiên, phương pháp này cũng không nút n sao cho Jr là cực tiểu thực sự tối ưu cho việc tối đa thời gian sống 1 dn i của mạng do định tuyến đường ngắn nhất r arg min J r 2 chỉ phù hợp với cấu trúc mạng tĩnh, cấu trúc nii d n  mạng động hoặc hỗn hợp thì hiệu quả sử dụng thấp. Quá trình định tuyến liên tục sử Để giải quyết bài toán ta có thể sử dụng các đường định tuyến ngắn nhất dẫn dụng giải thuật Floyd – Warshall [16]. đến các nút cảm biến dọc theo đường định Do không tính đến năng lượng ở các nút tuyến, đặc biệt là các nút gần trạm gốc được nên trong phương pháp này mạng có thời nhiều nút lựa chọn sẽ nhanh chóng cạn kiệt gian sống ngắn vì một nút cảm biến cạn kiệt năng lượng làm cho mạng có thể phân vùng năng lượng do tham gia quá nhiều vào quá hoặc đột ngột dừng hoạt động. trình định tuyến. Để khắc phục sự cố này, đề tài nghiên cứu giải thuật định tuyến cân bằng tải nhằm 2. Phƣơng pháp định tuyến cân bằng tải nâng cao tuổi thọ cho mạng cảm biến không Đây là phương pháp mà các tuyến đường dây được đề xuất. Các tuyến đường sử dụng được xác định theo đường ngắn nhất kết hợp năng lượng gần mức tối ưu kết hợp với với trọng số là nghịch đảo mức năng lượng khoảng cách ngắn nhất từ nút nguồn đến còn lại tại các nút. trạm gốc nhằm đảm bảo sự cân bằng năng lượng cho mạng. Năng lượng của mạng sẽ Để có thể tính đến mức năng lượng của tiêu hao đồng đều trên các nút cảm biến nhờ các nút cảm biến, giải pháp đề xuất của luận đó mà kéo dài được thời gian sống của toàn văn là bổ sung vào phương trình 1 các trọng mạng. số là tỉ lệ nghịch với mức năng lượng còn lại II. PHƢƠNG PHÁP ĐỊNH TUYẾN của mỗi nút tại thời điểm được xét như 1. Phƣơng pháp định tuyến đƣờng đi phương trình 3 . ngắn nhất ddn n n n dd Trạm gốc i j j k nk n l n l n1 Jrde n 3 n i e e e e (BS) nj n k n l n1 1dn ln1 nl Định tuyến nối nút đến nút được dnknl xác định sao cho Jrđạt cực tiểu de ni n dn n r arg min J r kj k nii de n  nj ddn n n n ddn n n n dninj arg min i j j k k l l 1 4 r e e e e ni nj n k n l n1 n i Trong đó en là năng lượng còn lại của nút Hình 1: Mô hình xác định định tuyến n t ại thời điểm đang xét. Ví dụ với tuyến đường 1 Trong phương trình (4), là trọng số rn n i,,,, n j n k n l n1như trên Hình 1. e i nk của tuyến . Nếu nút còn ít năng Hàm mục tiêu của phương pháp định nnjk nk tuyến theo đường ngắn nhất được xác định lượng ( e nhỏ) thì trọng số trên tuyến nk bởi: sẽ lớn và nút sẽ ít có cơ hội được chọn là J r d d d d nút chuyển tiếp. d ni n i n j n j n k n k n l n l n1 Để giải quyết phương trình 4.5 ta có thể ni,,,, n j n k n l n1 r n i 1 sử dụng giải thuật Floyd – Warshall [16].  dR Trong đó: d là khoảng cách từ nút phát đến nút thu
3. III. CÁC THÔNG SỐ MÔ PHỎNG Bảng 1: Các thông số mô phỏng Mô phỏng được thực hiện dựa trên Thông số Ký hiệu Giá trị Matlab với 100 nút cảm biến được triển khai 2 trong trường cảm biến 500x500m . Các nút Kích thước mạng fieldX*Y 500x500 m2 cảm biến được đánh số thứ tự từ 1 đến 100. Số lượng nút numNodes 100 Mỗi nút có một phạm vi truyền dẫn (R) cảm biến nhất định [15] và sử dụng tốc độ phát sinh Bán kính phạm và chuyển tiếp gói dữ liệu cố định. Các nút R 100 cảm biến tạo ra các gói dữ liệu có kích thước vi liên lạc như nhau. Tất cả các nút cảm biến bắt đầu Năng lượng ban Energy 1 đvnl với năng lượng ban đầu như nhau là 1 đơn đầu vị năng lượng. Tỉ lệ các gói dữ liệu được chuyển đến trạm gốc và mức năng lượng cần Năng lượng phát EnergyPhat 0.0005 đvnl thiết của các nút cảm biến chuyển tiếp luôn được trạm gốc theo dõi. Khi một nút cảm Năng lượng thu EnergyThu 0.0001 đvnl biến có mức năng lượng còn lại nhỏ hơn 0.1 Số vòng mô đơn vị năng lượng thì coi như nút đó đã chết numSim 100 phỏng và không tham gia vào quá trình thu phát các gói điều khiển hay dữ liệu nào. IV. KẾT QUẢ MÔ PHỎNG VÀ PHÂN Trong nghiên cứu này, mạng cảm biến TÍCH gồm các nút cảm biến có thể được thực hiện 1. Trƣờng hợp phân bố đều các nút cảm với các nhiệm vụ khác nhau: cảm biến, biến 500 chuyển tiếp và tổng hợp. Mô phỏng cho lần 91 92 93 94 95 96 97 98 99 100 450 lượt từ nút cảm biến phát dữ liệu về cho 81 82 83 84 85 86 87 88 89 90 400 trạm gốc. Trong 100 lần mô phỏng, mô 71 72 73 74 75 76 77 78 79 80 350 phỏng sẽ dừng lại khi xuất hiện một nút cảm 61 62 63 64 65 66 67 68 69 70 300 biến trong mạng cạn kiệt năng lượng và 51 52 53 54 55 56 57 58 59 60 250 không còn khả năng tham gia vào quá trình 41 42 43 44 45 46 47 48 49 50 200 31 32 33 34 35 36 37 38 39 40 thu phát hoặc chuyển tiếp gói dữ liệu về 150 21 22 23 24 25 26 27 28 29 30 trạm gốc. Giả sử thời gian phát giữa 2 nút 100 11 12 13 14 15 16 17 18 19 20 cảm biến liên tiếp là như nhau. Thời gian 50 1 2 3 4 5 6 7 8 9 10 0 sống của toàn mạng bằng thời gian giữa 2 0 50 100 150 200 250 300 350 400 450 500 nút phát liên tiếp nhân cho tổng số gói dữ Hình 2: Sơ đồ mô phỏng với 100 nút cảm liệu nhận được tại trạm gốc. Vậy thời gian biến phân bố đều sống của toàn mạng tỉ lệ thuận với tổng số gói dữ liệu nhận được tại BS. 1.1. Sự tổng hợp và chuyển tiếp các gói dữ liệu tại các nút cảm biến phân bố đều T T. SogoidulieutaiBS (5) ToanMang  Trong mô phỏng này các nút cảm biến Trong đó: T là thời gian giữa hai nút lần lượt phát gói dữ liệu theo tuyến đường phát liên tiếp đã được chọn về trạm gốc (ID = 56). Tổng số gói dữ liệu chuyển tiếp qua mỗi nút phụ Môi trường mô phỏng là dạng lan truyền thuộc vào vị trí của các nút trong mạng. Chú trong không gian tự do. Các thông số đầu ý rằng mô phỏng dừng lại khi một nút cảm vào cho quá trình mô phỏng được xác định biến cạn kiệt năng lượng. theo Bảng 4.1 Từ Hình 3 cho biết tổng số gói dữ liệu do mỗi nút thu phát trong phương pháp định tuyến cân bằng tải. Với điều kiện lựa chọn nút cảm biến là nút chuyển tiếp dựa vào khoảng cách và năng lượng còn lại của nút đó làm cho các nút chuyển tiếp thay đổi linh hoạt, tránh được sự lạm dụng những nút quan trọng. Qua 100 vòng định tuyến, tổng
4. số gói tin thu được tại BS là 1000 gói dữ biến với một phân bố đều. Xem xét Hình liệu, không có nút cảm biến nào tổng hợp và 4.5, ta thấy mức năng lượng còn lại của các chuyển tiếp nhiều hơn 2000 gói dữ liệu. Các nút cảm biến sử dụng phương pháp LBR nút gần trạm gốc có vai trò như nút cổng. đồng đều hơn mức năng lượng còn lại của Nút 45, 46, 47, 55, 57, 65, 66 và 67 tổng các nút cảm biến sử dụng phương pháp SPR, hợp và chuyển tiếp nhiều gói dữ liệu hơn khi mô phỏng chạy hết 100 vòng vẫn chưa các nút còn lại nằm xa trạm gốc. có một nút cảm biến nào bị cạn kiệt năng 10000 lượng. Trong khi đó, với Hình 6 năng lượng 9000 còn lại của các nút cảm biến không đồng 8000 đều, khi số vòng mô phỏng là 100 thì mạng 7000 chỉ chạy được 61 vòng thì ngừng hoạt động 6000 [-] [-] do nút 45 cạn kiệt năng lượng vì nó được 5000 nhiều nút khác chọn làm nút chuyển tiếp 4000 Number of messages messages of Number 3000 trên đường đi ngắn nhất đến trạm gốc hay do 2000 tổng hợp quá nhiều gói dữ liệu trong quá 1000 trình hoạt động trong khi còn rất nhiều nút 0 0 10 20 30 40 50 60 70 80 90 100 cảm biến còn nhiều năng lượng còn lại. Như node ID [-] vậy, định tuyến cân bằng tải đã phân bổ Hình 3: Tổng số gói dữ liệu tại các nút cảm đồng đều tải làm việc trên các nút cảm biến biến phân bố đều (LBR) làm cho mức năng lượng còn lại của các nút Từ hình 4 cho biết tổng số gói dữ liệu do được cân bằng, từ đó kéo dài thời gian sống mỗi nút phát hoặc chuyển tiếp trong phương của các nút dẫn đến tối đa thời gian sống của pháp định tuyến đường ngắn nhất. Do các toàn mạng. nút được lựa chọn là nút chuyển tiếp chỉ dựa 1 vào khoảng cách nên các nút trên các tuyến 0.9 đường là cố định, các nút quan trọng bị lạm 0.8 dụng một cách đáng kể nên trạm gốc chỉ thu 0.7 0.6 được 6000 gói dữ liệu thì mô phỏng dừng lại [-] 0.5 do nút 45 cạn kiệt năng lượng. Các nút gần Nang luong con lai lai con luong Nang 0.4 trạm gốc có vai trò như nút cổng tổng hợp 0.3 và chuyển tiếp nhiều hơn hẳn so với các nút 0.2 còn lại. Đặc biệt là nút 45: Tại vòng 61 thì 0.1 0 nút 45 đã tổng hợp và chuyển tiếp xấp xỉ 0 10 20 30 40 50 60 70 80 90 100 node ID [-] 3000 gói dữ liệu. Do bị sử dụng quá nhiều Hình 5: Năng lượng còn lại của các nút cảm nên nút 45 đã cạn kiệt năng lượng tại vòng biến phân bố đều (LBR) 61 và không còn khả năng tổng hợp hay chuyển tiếp thêm bất kỳ gói dữ liệu nào nữa. 1 0.9 6000 0.8 0.7 5000 0.6 [-] [-] 0.5 4000 Nang luong con lai lai con luong Nang 0.4 [-] [-] 3000 0.3 Number of messages messages of Number 0.2 2000 0.1 0 0 10 20 30 40 50 60 70 80 90 100 1000 node ID [-] 0 0 10 20 30 40 50 60 70 80 90 100 Hình 6: Năng lượng còn lại của các nút cảm node ID [-] biến phân bố đều (SPR) Hình 4: Tổng số gói dữ liệu tại các nút cảm biến phân bố đều (SPR) 1.2. Phân bố năng lƣợng còn lại tại các nút cảm biến phân bố đều Hình 5 và Hình 6 trình bày sự phân bố các mức năng lượng còn lại tại các nút cảm
5. 2. Trƣờng hợp phân bố ngẫu nhiên các gói dữ liệu nhận được tại BS là 6000. Tổng nút cảm biến số gói dữ liệu tổng hợp và chuyển tiếp tại 500 67 30 75 84 93 13 các nút cảm biến là không đồng đều nhau. 3 74 11 71 38 450 31 96 85 44 Các nút gần trạm gốc có vai trò như nút 59 54 62 32 400 37 41 72 cổng tổng hợp và chuyển tiếp nhiều hơn hẳn 35 23 76 17 49 350 51 34 78 82 36 57 28 65 so với các nút còn lại. Đặc biệt là nút 70: Tại 43 300 90 24 5 45 81 4 26 77 2 20 56 vòng 61 thì nút 70 đã tổng hợp và chuyển 250 5042 25 58 10 66 87 73 64 63 15 tiếp xấp xỉ 3000 gói dữ liệu. Do bị sử dụng 200 61 29 83 86 1 70 94 39 19 6 99 150 91 quá nhiều nên nút 70 đã cạn kiệt năng lượng 21 33 16 92 97 46 7 27 89 69 40 100 12 8 100 9 48 80 tại vòng 61 và không còn khả năng tổng hợp 55 60 79 18 14 88 68 53 95 50 52 hay chuyển tiếp thêm bất kỳ gói dữ liệu nào 98 22 47 0 0 50 100 150 200 250 300 350 400 450 500 nữa. 6000 Hình 7: Sơ đồ mô phỏng với 100 nút cảm biến phân bố ngẫu nhiên 5000 2.1. Sự tổng hợp và chuyển tiếp các gói dữ 4000 liệu tại các nút cảm biến phân bố ngẫu [-] 3000 nhiên Number of messages messages of Number Trong mô phỏng này các nút cảm biến 2000 lần lượt phát gói dữ liệu theo tuyến đường 1000 đã được chọn về trạm gốc (ID = 1). Tổng số 0 0 10 20 30 40 50 60 70 80 90 100 gói dữ liệu chuyển tiếp qua mỗi nút phụ node ID [-] thuộc vào vị trí của các nút trong mạng. Chú Hình 9: Số gói dữ liệu tại các nút cảm biến ý rằng mô phỏng dừng lại khi một nút cảm phân bố ngẫu nhiên (SPR) biến cạn kiệt năng lượng. 2.2. Phân bố năng lƣợng còn lại tại các Hình 8 cho biết tổng số gói dữ liệu do nút cảm biến phân bố ngẫu nhiên mỗi nút thu phát trong phương pháp định tuyến cân bằng tải. Tổng số gói dữ liệu nhận Hình 10 và Hình 11 trình bày sự phân tại BS là 10000 gói. Tổng số gói dữ liệu thu bố các mức năng lượng còn lại tại các nút phát tại các nút cảm biến đồng đều, tức là sự cảm biến. Xem xét Hình 10, ta thấy mức tham gia vào quá trình định tuyến của các năng lượng còn lại của các nút cảm biến sử nút cảm biến đồng đều. Trong 100 vòng dụng phương pháp LBR đồng đều hơn mức định tuyến, không có nút cảm biến nào tổng năng lượng còn lại của các nút cảm biến sử hợp và chuyển tiếp nhiều hơn 2000 gói dữ dụng phương pháp SPR, khi mô phỏng chạy liệu. Các nút gần trạm gốc có vai trò như nút hết 100 vòng vẫn chưa có một nút cảm biến cổng. Nút 42, 50, 70, 76, 77 và 99 tổng hợp nào bị cạn kiệt năng lượng. Trong khi đó, và chuyển tiếp nhiều gói dữ liệu hơn các nút với Hình 11 năng lượng còn lại của các nút còn lại nằm xa trạm gốc. cảm biến không đồng đều, khi số vòng mô phỏng là 100, mạng cảm biến sử dụng 10000 phương pháp SPR chỉ chạy được 61 vòng thì 9000 8000 ngừng hoạt động do nút 70 cạn kiệt năng 7000 lượng vì nó được nhiều nút khác chọn làm 6000 [-] [-] nút chuyển tiếp trên đường đi ngắn nhất đến 5000 trạm gốc hay do tổng hợp quá nhiều gói dữ 4000 Number of messages messages of Number liệu trong quá trình hoạt động trong khi còn 3000 rất nhiều nút cảm biến còn nhiều năng lượng 2000 còn lại. Như vậy, định tuyến cân bằng tải đã 1000 0 phân bổ đồng đều tải làm việc trên các nút 0 10 20 30 40 50 60 70 80 90 100 node ID [-] cảm biến làm cho mức năng lượng còn lại Hình 8: Tổng số gói dữ liệu tại các nút cảm của các nút được cân bằng, từ đó kéo dài biến phân bố ngẫu nhiên (LBR) thời gian sống của các nút dẫn đến tối đa Hình 9 cho biết tổng số gói dữ liệu do thời gian sống của toàn mạng. mỗi nút phát hoặc chuyển tiếp trong phương pháp định tuyến đường ngắn nhất. Tổng số
6. 1 Dinh tuyen can bang tai 260 0.9 N = 80 240 N = 100 0.8 0.7 220 0.6 200 [-] [-] 0.5 180 Nang luong con lai lai con luong Nang 0.4 160 0.3 So goi tin 140 0.2 120 0.1 0 100 0 10 20 30 40 50 60 70 80 90 100 node ID [-] 80 Hình 10: Năng lượng còn lại tại các nút cảm 60 80 85 90 95 100 105 110 115 120 biến phân bố ngẫu nhiên (LBR) R 1 Hình 13: Định tuyến cân bằng tải theo N và 0.9 R 0.8 0.7 Theo Hình 12 và Hình 13, phương pháp 0.6 [-] [-] LBR có số lượng gói dữ liệu thu tại BS tỉ lệ 0.5 thuận với số lượng và bán kính phạm vi liên Nang luong con lai lai con luong Nang 0.4 lạc của nút cảm biến, còn với phương pháp 0.3 0.2 SPR tỉ lệ gói thu được thay đổi không đều 0.1 khi tăng giá trị của R và N. Ngoài ra, tổng số 0 0 10 20 30 40 50 60 70 80 90 100 gói dữ liệu thu được tại trạm gốc BS với bán node ID [-] kính phạm vi liên lạc và số lượng nút cảm Hình 11: Năng lượng còn lại tại các nút cảm biến nhất định thì phương pháp LBR luôn biến phân bố ngẫu nhiên (SPR) cao hơn phương pháp SPR. Điều này chứng 2.3. Ảnh hƣởng của số lƣợng nút cảm tỏ hiệu suất làm việc của phương pháp định biến N và bán kính phạm vi liên lạc R tuyến cân bằng tải cao hơn so với định tuyến trong phân bố ngẫu nhiên đường đi ngắn nhất, từ đó mà cải thiện được thời gian sống của toàn mạng. Để khảo sát sự ảnh hưởng của số nút cảm biến N trong trường cảm biến và bán 3. Mô phỏng Monte Carlo kính phạm vi liên lạc R của nút cảm biến, Để khảo sát các đặc trưng thống kê của các mô phỏng đã được thực hiện với các giá hai phương pháp LBR và SPR, mô phỏng trị N và R khác nhau (R = 80, 90, 100, 110, Monte Carlo được thực hiện theo các thông 120 và N = 80, 100). Các nút cảm biến lần số như Bảng 2. Các nút cảm biến được phân lượt phát các gói dữ liệu về cho trạm gốc. bố 50 sơ đồ mô phỏng ngẫu nhiên. Với mỗi Mô phỏng dừng lại khi một nút cảm biến bị sơ đồ mô phỏng, các nút cảm biến lần lượt cạn kiệt năng lượng và tổng số gói dữ liệu phát các gói dữ liệu thông qua các tuyến nhận được tại trạm gốc được ghi nhận (phụ đường đến trạm gốc BS. Khi một nút cảm lục 2). Trong mô phỏng, mức năng lượng biến cạn kiệt năng lượng, mô phỏng dừng lại phát của các nút bằng 0.05/gói và mức năng và tổng số gói dữ liệu nhận được tại trạm lượng thu của các nút bằng 0.01/gói dữ liệu. gốc BS lúc đó được ghi nhận. Dinh tuyen duong di ngan nhat 130 N = 80 120 N = 100 110 100 90 80 So goi tin 70 60 50 40 30 80 85 90 95 100 105 110 115 120 R Hình 12: Định tuyến đường đi ngắn nhất theo N và R
7. Bảng 2: Thông số mô phỏng Monte Carlo Bảng 3: Kỳ vọng toán học và phương sai Thông số Ký hiệu Giá trị Phƣơng pháp E(s) Var(s) Bán kính phạm vi R 120 m SPR 50 21 liên lạc Năng lượng phát EnergyPhat 0.05 đvnl LBR 138 42 Năng lượng thu EnergyThu 0.01 đvnl Kết quả mô phỏng Monte Carlo cho thấy phương pháp định tuyến cân bằng tải tổng Số lần mô phỏng numMC 50 hợp gấp 2.76 lần số gói dữ liệu so với phương pháp định tuyến đường đi ngắn 2 Kích thướt mạng fieldX*Y 500x500 m nhất. Tuy nhiên phương sai của phương pháp LBR lại cao gấp 2 lần so với phương Trạm gốc receive 1 sai của phương pháp SPR nên độ biến thiên 1.5 quanh giá trị trung bình của nó còn khá cao. 1 V. KẾT LUẬN 0.5 Đề tài Nghiên cứu giải thuật định tuyến Ham phan phoi phan Ham cân bằng tải nhằm nâng cao tuổi thọ cho 0 0 50 100 150 200 250 300 So goi tin mạng cảm biến không dây thực hiện cân SPR 0.8 LBR bằng tải, cân bằng sự tham gia vào quá trình 0.6 định tuyến của các nút cảm biến. Trong đề 0.4 án này, giải pháp LBR đã được đề xuất bằng 0.2 cách bổ sung vào phương pháp định tuyến Ham matHam xacdo suat 0 đường đi ngắn nhất các trọng số là nghịch 0 50 100 150 200 250 300 So goi tin đảo của mức năng lượng còn lại của các nút Hình 14: Hàm phân phối và hàm mật độ xác cảm biến. Các kết quả mô phỏng cho thấy suất giải pháp đề xuất có hiệu quả hơn so với định tuyến đường đi ngắn nhất, cụ thể là: Số Hình 14 thể hiện hàm phân phối và lượng gói dữ liệu thu phát tại các nút cảm hàm mật độ xác suất của tổng số gói dữ liệu biến đồng đều; Phân bố năng lượng tương thu được tại trạm gốc BS ứng với hai đối đồng đều; Tỉ lệ thuận với bán kính phạm phương pháp SPR và LBR. Với phương vi liên lạc và số lượng nút cảm biến; Tổng pháp SPR số gói tin cao nhất thu được tại số gói dữ liệu trung bình nhận được tại BS BS là 130 gói tin trong 50 lần mô phỏng, cao gấp 2.76 lần; Thời gian sống của toàn trong khi đó phương pháp LBR số gói tin mạng lâu hơn 2.76 lần. thu được tại BS cao nhất là 251 gói tin, cao gấp 1.93 lần so với phương pháp định tuyến Tuy nhiên, định tuyến cân bằng tải còn đường đi ngắn nhất. Từ hàm mật độ xác suất một số hạn chế như: Độ lệch quanh giá trị ta thấy, xác suất để gởi thành công 30 gói tin trung bình tổng số gói dữ liệu nhận tại BS với phương pháp định tuyến đường đi ngắn còn cao; Trọng số là nghịch đảo năng lượng nhất là 40%, trong khi đó xác suất ứng với còn lại của các nút cảm biến có thể chưa là phương pháp được đề xuất gởi thành công tối ưu để tối đa hóa thời gian sống cho mạng 141.8 gói tin là 48%, cao gấp 1.2 lần so với cảm biến không dây. phương pháp định tuyến đường đi ngắn Với trọng số là nghịch đảo năng lượng nhất. Giá trị ước lượng của kỳ vọng toán học còn lại của các nút cảm biến có thể chưa tối và phương sai của tổng số gói dữ liệu nhận ưu để tối đa thời gian sống cho mạng cảm được tại trạm gốc theo Bảng 3. biến không dây. Từ luận văn có thể thay đổi trọng số là một hàm nào đó của thời gian sống của mạng sao cho thời gian sống của mạng là dài nhất hoặc tổng số gói tin mà trạm gốc nhận được là nhiều nhất.
8. TÀI LIỆU THAM KHẢO Sensor Systems (SenSys’09), Berkeley, California, USA, pp. 23-33, 2009. [1] M. Bhardwaj, T. Garnett, A.P. Chandrakasan. Upper Bounds on The Lifetime of Sensor Networks. [15] Milan Simek, Patrik Moravek. Modeling of in Proc. Of the IEEE International Conference on Energy Consumption of Zigbee Devices in Matlab Communication, (ICC’01), vol.3, 2001. Tool. Elektrorevue, ISSN 1213 – 1539, vol.2, No.3, pp 41-46, 2011. [2] R. Shah, J. Rabaey. Energy Aware Routing for Low Energy Ad Hoc Sensor Networks. in Proc. Of [16] Leiserson, Cormen and Rivest. Introduction of IEEE WCNC’02, Orlando, FL, pp. 350-355, 2002. algorithm. Edition 2, MIT Press, United States, pp. 558 – 562, 2004. [3] Ambreen, Haque Nawaz. Wireless Sensor Network Through Shortest Path Route. International Thông tin liên hệ: Journal of Emerging Technology and Advanced Engineering, vol.3, pp 158-161, 2013. Họ tên: Nguyễn Thị Thu Trang [4] Basil Etefia. Routing Protocol for Wireless Đơn vị: Trường Trung cấp nghề Việt – Hàn Sonsor Networks. Summer Undergraduate Program in Engineering at Berkeley [Online]. Bình Dương Available: Điện thoại: 0168 210 1157 /2004/BasilEtefia FinalPaper.pdf, 2004. [5] Nguyễn Thị Khánh Chi. Đa thâm nhập môi Email: nguyentrang039@gmail.com trường trong mạng WSN. Trường Đại học Dân lập Hải Phòng, 2009. [6] H. Zhang, A. Arora, Y. Choi and M. Gouda. Xác nhận của giảng viên hƣớng dẫn Reliable bursty convergecast in wireless sensor networks. Computer Communications, 30(13):2560– 2576, Dec. 2007. [7] L. Zhou, S. Zhou, Y. Yao. Multipath Rayleigh Fading Channels in the Low SNR Regime. in Proc. of the IEEE International Conference (ICC’06), Volume PGS.TS Dương Hoài Nghĩa 3, p.p. 1404 – 1409, 2006. [8] J. Hui and D. Culler. Ip is dead, long live ip for wireless sensor networks. in Proc. 6th ACM Conference of Embedded Networked Sensor Systems (SenSys’08), ACM Press, New York, USA, pp. 15– 28, 2008. [9] J. Polastre, J. Hill, and D. Culler. Versatile Low- Power Media Access for Wireless Sensor Networks. in Proc. of the Second ACM Conference on Embedded Networked Sensor Systems (SenSys’04), Baltimore, MD, USA, pp. 95–107, 2004. [10] K. Scott, N. Bambos. Routing and channel assignment for low power transmission in PCS. in Proc. International Conference on Universal Personal Communications, Cambridge, MA, pp. 469–502, 1996. [11] B. Krishnamachari, D. Estrin, and S. Wicker. The impact of data aggregation in wireless sensor networks. in Proc. of the Workshops of 22nd International Conference on Distributed Computing Systems, IEEE Computer Society, Vienna, Austria,pp. 575–578, 2002. [12] J. Al-Karaki, A. KamalRouting. Techniques in Wireless Sensor Networks: A Survey. IEEE Wireless Communication, pp. 6-28, 2004. [13] Zhang and J. Gao. Load balanced short path routing in wireless networks. in Proc. of IEEE INFOCOM’04, China, 2004. [14] O. Gnawali, R. Fonseca, K. Jamieson, D. Moss, and P. Levis. Collection Tree Protocol. in Proc. of the 7th ACM Conference on Embedded Networked
9. BÀI BÁO KHOA HỌC THỰC HIỆN CÔNG BỐ THEO QUY CHẾ ĐÀO TẠO THẠC SỸ Bài báo khoa học của học viên có xác nhận và đề xuất cho đăng của Giảng viên hướng dẫn Bản tiếng Việt ©, TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT TP. HỒ CHÍ MINH và TÁC GIẢ Bản quyền tác phẩm đã được bảo hộ bởi Luật xuất bản và Luật Sở hữu trí tuệ Việt Nam. Nghiêm cấm mọi hình thức xuất bản, sao chụp, phát tán nội dung khi chưa có sự đồng ý của tác giả và Trường Đại học Sư phạm Kỹ thuật TP. Hồ Chí Minh. ĐỂ CÓ BÀI BÁO KHOA HỌC TỐT, CẦN CHUNG TAY BẢO VỆ TÁC QUYỀN! Thực hiện theo MTCL & KHTHMTCL Năm học 2016-2017 của Thư viện Trường Đại học Sư phạm Kỹ thuật Tp. Hồ Chí Minh.