Giải thuật heuristic và di truyền giải bài toán định tuyến đa điểm trên mạng cảm biến không dây nhiệm vụ tuần hoàn

nhiều so với năng lượng nhận tin, nên không mất tính tổng quát ta lấy es = 100
và er = 15 (đơn vị năng lượng). Chu kỳ của mỗi nút có K = 20 khe thời gian, trong đó mỗi
nút sẽ chọn ngẫu nhiên một vài khe thời gian hoạt động. Tỉ lệ số khe thời gian hoạt động và
số các nút terminal thay đổi theo từng bộ dữ liệu.
Bộ dữ liệu 1, 2, 3 với lần lượt |V | = 100, 200, 300 nút. Số lượng khe thời gian hoạt động
trong một chu kỳ làm việc của mỗi nút trên ba bộ dữ liệu này là cố định, chiếm 25% trên
tổng số K = 20 khe thời gian. Số lượng các nút terminal trên tổng số các nút thay đổi trong
khoảng 5-100% (với bước nhảy 5%), ứng với 20 test trên mỗi bộ dữ liệu. Ứng với mỗi test dữ
liệu, sau khi xác định được số lượng (dựa theo tỉ lệ phần trăm), các nút terminal sẽ được lựa
chọn ngẫu nhiên từ tập đỉnh V. Bộ dữ liệu 4 với |V | = 200 nút. Số lượng các nút terminal là
cố định, chiếm 50% tổng số nút toàn mạng. Số các khe thời gian hoạt động trên tổng số K
= 20 khe thời gian trong mỗi chu kỳ làm việc của mỗi nút thay đổi trong khoảng 5-60% (với
bước nhảy 5%), ứng với 12 test dữ liệu.
5.2. Các tham số và cấu hình thử nghiệm
Giải thuật heuristic HMEM được kết hợp với phương pháp tìm kiếm địa phương đã nêu
để đưa ra lời giải cho bài toán. Giải thuật di truyền GAMEM sử dụng 200 thế hệ quần thể,
mỗi quần thể bao gồm 200 cá thể và sử dụng các tham số xác suất: Pc = 0.2; Pm = 0.05;
Ps = 0.3. Trong mỗi test thử nghiệm, giải thuật di truyền do có tính chất ngẫu nhiên nên
được tiến hành chạy 50 lần và lấy kết quả trung bình.
5.3. Kết quả thử nghiệm
Các giải thuật được đánh giá theo các tiêu chuẩn: tổng năng lượng tiêu tốn trong một
phiên multicast, độ trễ truyền tin và thời gian chạy chương trình2. Hình 3(a)-(d) cho biết tổng
năng lượng tiêu tốn trong mỗi phiên multicast của các giải thuật TCS, HMEM và tổng năng
lượng tiêu tốn tính trung bình trong 50 lượt chạy của giải thuật GAMEM, cùng với khoảng
tin cậy 95%. Các giá trị trong hình (theo trục tung) được tính dựa theo công thức tính tổng
năng lượng tiêu tốn trong mỗi phiên multicast đã được trình bày ở phần 2.2. Với mục đích
2Trong bài viết [3], các tác giả đã coi năng lượng nhận tin là không đáng kể nên chỉ xét đến tổng số lượt
truyền tin của các nút trong một phiên multicast. Tuy nhiên, để giữ cho bài toán tổng quát chúng tôi xét cả
năng lượng nhận tin.
262 NGUYỄN THÁI DƯƠNG, HUỲNH THỊ THANH BÌNH, NGÔ HỒNG SƠN
chỉ so sánh tương quan về độ tốt của các giải thuật, chúng tôi không sử dụng đến đơn vị tính
năng lượng cụ thể. Mỗi giá trị trên trục hoành–ứng với mỗi test dữ liệu của hình 3(a)-(c) cho
biết tỉ lệ phần trăm các nút terminal so với tổng số |V| nút và của hình 3(d) cho biết tỉ lệ
phần trăm các khe thời gian hoạt động so với K khe thời gian của mỗi nút. Dựa vào các hình
3(a)-(d) có thể thấy rằng, giải thuật GAMEM và giải thuật HMEM có hiệu quả tốt hơn so
với giải thuật TCS về mặt tối ưu năng lượng, đặc biệt là giải thuật GAMEM cho lời giải có
năng lượng tiêu tốn nhỏ nhất trên hầu hết các test của bộ dữ liệu 1-4.
GIẢI THUẬT HEURISTIC VÀ DI TRUYỀN GIẢI BÀI TOÁN ĐỊNH TUYẾN ĐA ĐIỂM 11 
còn thấp so với các th ật toán đề xuất. Giải thuật HMEM trực tiếp đưa ra cây lời giải cho bài toán sau 
quá trình tìm đường đi ngắn nhất trên đồ thị G’. Đồ thị này được xây dựng dự trê cấu trúc đồ thị 
mạng ban đầu và điều kiện ràng buộc về các khe thời gian hoạt động các nút. Ngoài ra, HMEM 
được nâng cao chất lượng lời giải bằng phương pháp tìm kiếm địa phương đề xuất nên cho kết quả 
tốt. Giải thuật GAMEM có các phép toán di truyền hiệu quả, trong số đó có phép toán lai ghép (cụ thể 
là lai ghép heuristic) và phép toán đột biến đ c áp dụng giải thuật HMEM trong quá trình xây dựng. 
Lý do này khiến cho giải thuật GAMEM có kết quả tốt hơn giải thuật HMEM về mặt tối ưu năng 
lượng trong hầu hết các test dữ liệu. 
Hình 3. Năng lượng multicast của các giải thuật trên bốn bộ dữ liệu. (a) Bộ dữ liệu 1, |V| = 100. (b) Bộ dữ liệu 
2, |V| = 200. (c) Bộ dữ liệu 3, |V| = 300. (d) Bộ dữ liệu 4, |V| = 200. 
 Hình 3(a)-(c) còn cho thấy khi số lượng các terminal tăng thì năng lượng multicast của các giải 
thuật cũng tăng. Điều này là hiển nhiên vì khi đó số lượng nút trong cây lời giải cũng tăng theo, dẫn 
tới năng lượng dùng để truyền và nhận tin trên cây này cũng tăng. Hình 3(d) cho thấy, trong bộ dữ 
liệu 4 giải thuật TCS kém hiệu quả đối với các test có tỉ lệ số khe thời gian hoạt động thấp (dưới 
30%). Bên cạnh đó, khi tỉ lệ số khe thời gian hoạt động tăng thì năng lượng multicast của các giải 
thuật giảm. Điều đó là do khi tỉ lệ số khe thời gian hoạt động của các nút tăng lên thì khả năng nhiều 
nút có chung khe thời gian hoạt động cũng tăng, dẫn tới việc các nút chuyển tiếp của cây multicast lời 
giải chỉ cần truyền tin tại một số ít khe thời gian là đã có thể truyền tin được tới tất cả các nút con của 
nó, dẫn tới năng lượng multicast có xu hướng giảm xuống. 
 So sánh các giải thuật về độ trễ. Độ trễ truyền tin được định nghĩa là khoảng thời gian tính từ khi 
nút gốc s bắt đầu gửi gói tin đến khi mọi nút terminal đều nhận được gói tin đó (tính theo đơn vị số 
khe thời gian). Để tính được độ trễ cho một phiên multicast ta phải áp dụng một lịch truyền không có 
xung đột nhằm tránh trường hợp xung đột có thể xảy ra giữa các lượt truyền tại cùng một thời điểm. 
Thực tế, bài toán cực tiểu hóa độ trễ multicast trên mạng cảm biến không dây là bài toán NP-khó, 
Hình 3: Năng lượng multicast của các giải thuật trên bốn bộ dữ liệu. (a) Bộ dữ liệu 1,
|V | = 100. (b) Bộ dữ liệu 2, |V | = 200. (c) Bộ dữ liệu 3, |V | = 300. (d) Bộ dữ liệu 4,
|V | = 200.
Kết quả thử nghiệm của các giải thuật được giải thích như sau. Giải thuật TCS không
tiến hành tìm lời giải trực tiếp trên đồ thị gốc mà dựa trên đồ thị mở rộng [3]. Đồ thị này có
cấu trúc đặc biệt, các đỉnh của nó bao gồm các đỉnh gốc trên đồ thị G cùng với các đỉnh vệ
tinh được tạo thêm. Trong đó, mỗi đỉnh vệ tinh biểu diễn tương ứng một lượt truyền trong
một khe thời gian nào đó của một đỉnh trên đồ thị gốc. Sau khi xây dựng đồ thị mở rộng,
giải thuật TCS tiến hành lựa chọn một tập các nút vệ tinh C (bằng một giải thuật tham lam)
sao cho mỗi đỉnh terminal đều kề với ít nhất một đỉnh trong C. Sau đó giải thuật tiến hành
tìm một cây Steiner nhỏ nhất bao phủ các nút của C và từ cây Steiner này ánh xạ ra lời giải
cho bài toán. Vì vậy độ tốt của TCS phụ thuộc nhi vào bước lựa chọn các đỉn cho tập C
và độ tốt của giải thuật tìm cây Steiner được áp dụng (giải thuật trong [4]). Việc lựa chọn
tập C (theo tiêu chí lựa chọn của phương pháp tham lam có trong [3]) được tiến hành riêng
HEURISTIC AND GENETIC ALGORITHMS FOR SOLVING MINIMUM-ENERGY 263
rẽ và cố định từ trước sau đó mới tìm cây Steiner dẫn tới việc cây Steiner thu được có trọng
số lớn trong nhiều trường hợp. Kết quả thử nghiệm cho thấy chất lượng lời giải xét về mặt
tối ưu năng lượng của TCS còn thấp so với các thuật toán đề xuất. Giải thuật HMEM trực
tiếp đưa ra cây lời giải cho bài toán sau quá trình tìm đường đi ngắn nhất trên đồ thị G’. Đồ
thị này được xây dựng dựa trên cấu trúc đồ thị mạng ban đầu và điều kiện ràng buộc về các
khe thời gian hoạt động của các nút. Ngoài ra, HMEM được nâng cao chất lượng lời giải bằng
phương pháp tìm kiếm địa phương đề xuất nên cho kết quả tốt. Giải thuật GAMEM có các
phép toán di truyền hiệu quả, trong số đó có phép toán lai ghép (cụ thể là lai ghép heuristic)
và phép toán đột biến được áp dụng giải thuật HMEM trong quá trình xây dựng. Lý do này
khiến cho giải thuật GAMEM có kết quả tốt hơn giải thuật HMEM về mặt tối ưu năng lượng
trong hầu hết các test dữ liệu.
Hình 3(a)-(c) còn cho thấy khi số lượng các terminal tăng thì năng lượng multicast của
các giải thuật cũng tăng. Điều này là hiển nhiên vì khi đó số lượng nút trong cây lời giải cũng
tăng theo, dẫn tới năng lượng dùng để truyền và nhận tin trên cây này cũng tăng. Hình 3(d)
cho thấy, trong bộ dữ liệu 4 giải thuật TCS kém hiệu quả đối với các test có tỉ lệ số khe thời
gian hoạt động thấp (dưới 30%). Bên cạnh đó, khi tỉ lệ số khe thời gian hoạt động tăng thì
năng lượng multicast của các giải thuật giảm. Điều đó là do khi tỉ lệ số khe thời gian hoạt
động của các nút tăng lên thì khả năng nhiều nút có chung khe thời gian hoạt động cũng
tăng, dẫn tới việc các nút chuyển tiếp của cây multicast lời giải chỉ cần truyền tin tại một số
ít khe thời gian là đã có thể truyền tin được tới tất cả các nút con của nó, dẫn tới năng lượng
multicast có xu hướng giảm xuống.12 NGUYỄN THÁI DƯƠNG, HUỲNH THỊ THANH BÌNH, NGÔ HỒNG SƠN 
thậm chí đối với mạng cảm biến không dây mà 
các nút luôn hoạt động. Trong nghiên cứu này, 
chúng tôi áp dụng mô hình lịch truyền collision-
free trong [3] để tính độ trễ truyền tin và so sánh 
các giải thuật. Hình 4 đưa ra độ trễ truyền tin 
trên cây multicast của các giải thuật trên các test 
dữ liệu. Các test dữ liệu được đánh chỉ số từ 1-
72 (lần lượt theo các bộ dữ liệu 1-4). Giá trị trên 
trục hoành cho biết chỉ số của các test dữ liệu. 
Giá trị theo trục tung được tính theo đơn vị số 
khe thời gian. Đối với giải thuật GAMEM, trên 
mỗi test dữ liệu, độ trễ truyền tin được tính 
trung bình trên 50 cây lời giải (của 50 lượt chạy) 
cùng với khoảng tin cậy 95%. Thấy rằng, giải 
thuật HMEM từng bước thực hiện quá trình tìm đường đi ngắn nhất trên đồ thị G’ để tạo ra cây 
multicast. Trong khi đó, giải thuật TCS xây dựng cây multicast bằng cách sử dụng cây Steiner tìm 
được trên đồ thị mở rộng, vì thể khoảng cách từ nút gốc s đến các nút terminal trên cây multicast của 
HMEM thường nhỏ hơn so với TCS. Điều này dẫn tới độ trễ truyền tin của HMEM nhỏ hơn TCS. 
Giải thuật GAMEM có sử dụng phương pháp tìm đường đi ngắn nhất của giải thuật HMEM trong một 
số phép toán di truyền, nên hai giải thuật này có độ trễ truyền tin gần như tương đương. 
Hình 4. Độ trễ truyền tin trên cây multicast của các giải thuật (tính theo đơn vị số khe thời gian). 
 Bảng 1 cho biết thời gian chạy trung bình trên mỗi test của các bộ dữ liệu 1-4 của các giải thuật. 
Dễ thấy thời gian tính toán của các giải thuật phụ thuộc vào kích thước mạng (số lượng nút). Giải 
thuật TCS tiến hành tìm lời giải dựa trên đồ thị mở rộng, đồ thị này có số đỉnh lớn hơn nhiều so với 
đồ thị gốc ban đầu nên có thời gian tính lớn hơn giải thuật HMEM. Giải thuật GAMEM có thời gian 
tính lớn nhất trong ba giải thuật do đặc điểm của giải 
thuật di truyền cần phải thực hiện các phép toán di 
truyền trên nhiều nhiễm sắc thể và qua nhiều thế hệ 
quần thể, tuy nhiên thời gian tính này vẫn ở mức chấp 
nhận được (trung bình cỡ 35s đối với bộ dữ liệu có số 
lượng đỉnh lớn nhất). 
5.4 Nhận xét về khả năng triển khai 
Giải thuật GAMEM đòi hỏi thông tin toàn cục và tính toán tập trung nên phù hợp với những phiên 
multicast diễn ra thường xuyên với tập terminal và nút nguồn xác định trước. Khi đó cần có một nút 
tập trung (thường là trạm gốc) để thu thập thông tin trong mạng, tính toán ra cây multicast và lịch 
truyền trước rồi truyền thông tin này cho các nút cảm biến để áp dụng cho những phiên truyền 
multicast này. 
 Với cách tiếp cận phân tán cho những yêu cầu multicast đến ngẫu nhiên, giải thuật TCS có độ 
phức tạp tính toán là O(|D|.|V|) với D là đường kính của đồ thị mạng cảm biến, độ phức tạp về số 
lượng gói tin trao đổi là O(|M|.|V|) [3]. Độ phức tạp của giải thuật HMEM chủ yếu phụ thuộc vào quá 
trình tìm |M| đường đi ngắn nhất trên đồ thị G’ (dòng 2-9 của Algorithm 1). Giả sử sử dụng giải thuật 
Bảng 1. Thời gian tính trung bình của các giải 
thuật trên mỗi test của bốn bộ dữ liệu (đơn vị 
millisecond). 
Bộ dữ liệu TCS HMEM GAMEM 
1 108.95 59.15 2662.92 
2 422.25 271.05 13459.57 
3 868.25 526.55 35211.17 
4 394.08 179.50 11109.78 
Hình 4: Độ trễ truyền tin trên cây multicast
của các giải thuật (tính theo đơn vị số khe thời
gian).
So sánh các giải thuật về độ trễ .
Độ trễ truyền tin được định nghĩa là khoảng
thời gian tính từ khi nút gốc s bắt đầu gửi
gói tin đến khi mọi nút terminal đều nhận
được gói tin đó (tính theo đơn vị số khe thời
gian). Để tính được độ trễ cho một phiên
multicast ta phải áp dụng một lịch truyền
không có xung đột nhằm tránh trường hợp
xung đột có thể xảy ra giữa các lượt truyền
tại cùng một thời điểm. Thực tế, bài toán
cực tiểu hóa độ trễ multicast trên mạng cảm
biến không dây là bài toán NP-khó, thậm chí
đối với mạng cảm biến không dây mà các nút
luôn hoạt động. Trong nghiên cứu này, chúng
ôi áp dụng mô hình lị h truyền collision-free
trong [3] để tí h độ trễ truyền tin và so sánh
các giải thuật. Hình 4 đưa ra độ trễ truyền
tin trên cây multicast của các giải thuật trên các est dữ liệu. Các test dữ liệu được đá h chỉ
số từ 1-72 (lần lượt theo các bộ dữ liệu 1-4). Giá trị trên trục hoành cho biết chỉ số của các
test dữ liệu. Giá trị theo trục tung được tính theo đơn vị số khe thời gian. Đối với giải thuật
GAMEM, trên mỗi test dữ liệu, độ trễ truyền tin được tính trung bình trên 50 cây lời giải
(của 50 lượt chạy) cùng với khoảng tin cậy 95%. Thấy rằng, giải thuật HMEM từng bước thực
hiện quá trình tìm đường đi ngắn nhất trên đồ thị G’ để tạo ra cây multicast. Trong khi đó,
giải thuật TCS xây dựng cây multicast bằng cách sử dụng cây Steiner tìm được trên đồ thị
264 NGUYỄN THÁI DƯƠNG, HUỲNH THỊ THANH BÌNH, NGÔ HỒNG SƠN
mở rộng, vì thể khoảng cách từ nút gốc s đến các nút terminal trên cây multicast của HMEM
thường nhỏ hơn so với TCS. Điều này dẫn tới độ trễ truyền tin của HMEM nhỏ hơn TCS.
Giải thuật GAMEM có sử dụng phương pháp tìm đường đi ngắn nhất của giải thuật HMEM
trong một số phép toán di truyền, nên hai giải thuật này có độ trễ truyền tin gần như tương
đương.
Bộ dữ liệu TCS HMEM GAMEM
1 108.95 59.15 2662.92
2 422.25 271.05 13459.57
3 868.25 526.55 35211.17
4 394.08 179.50 11109.78
Bảng 1: Thời gian tính trung bình của các
giải thuật trên mỗi test của bốn bộ dữ liệu
(đơn vị millisecond).
Bảng 1 cho biết thời gian chạy trung bình
trên mỗi test của các bộ dữ liệu 1-4 của các
giải thuật. Dễ thấy thời gian tính toán của các
giải thuật phụ thuộc vào kích thước mạng (số
lượng nút). Giải thuật TCS tiến hành tìm lời
giải dựa trên đồ thị mở rộng, đồ thị này có số
đỉnh lớn hơn nhiều so với đồ thị gốc ban đầu
nên có thời gian tính lớn hơn giải thuật HMEM.
Giải thuật GAMEM có thời gian tính lớn nhất
trong ba giải thuật do đặc điểm của giải thuật
di truyền cần phải thực hiện các phép toán di
truyền trên nhiều nhiễm sắc thể và qua nhiều thế hệ quần thể, tuy nhiên thời gian tính này
vẫn ở mức chấp nhận được (trung bình cỡ 35 s đối với bộ dữ liệu có số lượng đỉnh lớn nhất).
5.4. Nhận xét về khả năng triển khai
Giải thuật GAMEM đòi hỏi thông tin toàn cục và tính toán tập trung nên phù hợp với
những phiên multicast diễn ra thường xuyên với tập terminal và nút nguồn xác định trước.
Khi đó cần có một nút tập trung (thường là trạm gốc) để thu thập thông tin trong mạng,
tính toán ra cây multicast và lịch truyền trước rồi truyền thông tin này cho các nút cảm biến
để áp dụng cho những phiên truyền multicast này.
Với cách tiếp cận phân tán cho những yêu cầu multicast đến ngẫu nhiên, giải thuật TCS có
độ phức tạp tính toán là O(|D| · |V |) với D là đường kính của đồ thị mạng cảm biến, độ phức
tạp về số lượng gói tin trao đổi là O(|M |.|V |) [3]. Độ phức tạp của giải thuật HMEM chủ yếu
phụ thuộc vào quá trình tìm |M | đường đi ngắn nhất trên đồ thị G′ (dòng 2-9 của Algorithm
1). Giả sử sử dụng giải thuật phân tán trong [19] để tìm đường đi ngắn nhất và giả sử phạm
vi truyền tin của các nút là hằng số thì HMEM sẽ có độ phức tạp tính toán là O(|M |.|V |1+ε)
và độ phức tạp về số lượng gói tin trao đổi là O(|M |.|E|1+ε), trong đó ε = O(1)
/
4
√
log |V |.
6. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
Bài báo này đề xuất một giải thuật heuristic (HMEM) và một giải thuật di truyền (GA-
MEM) nhằm giải quyết bài toán định tuyến đa điểm trên mạng cảm biến không dây nhiệm
vụ tuần hoàn với mục tiêu tiết kiệm năng lượng truyền và nhận dữ liệu. Các giải thuật đề
xuất được đánh giá trên bốn bộ dữ liệu và được so sánh kết quả với giải thuật TCS. Kết quả
thử nghiệm cho thấy hai giải thuật đề xuất mang lại lời giải tốt hơn giải thuật TCS về mặt
tối ưu năng lượng và độ trễ truyền tin. Trong thời gian tới, chúng tôi sẽ phát triển thêm các
giải pháp cho bài toán này trong việc tối thiểu hóa độ trễ với các ràng buộc tránh xung đột.
Ngoài ra, chúng tôi sẽ mở rộng mô hình để giải quyết bài toán multicast với độ tin cậy cao
cho các trường hợp các nút cảm biến hoạt động thiếu ổn định.
HEURISTIC AND GENETIC ALGORITHMS FOR SOLVING MINIMUM-ENERGY 265
LỜI CÁM ƠN
Đề tài nghị định thư hợp tác với Nhật Bản – Nghiên cứu, phát triển mạng quang đô thị
bền vững - mã số 12/2012/HĐ-NĐT, đã hỗ trợ nhóm tác giả để hoàn thành bài báo này.
TÀI LIỆU THAM KHẢO
[1] F. Wang, and J. Liu, “Duty-cycle-aware broadcast in wireless sensor networks", in Proc.
IEEE INFOCOM, pp. 468–476, 2009.
[2] S. Xiong, J. Li, M. Li, J. Wang, and Y. Liu, “Multiple task scheduling for low-duty-cycled
wireless sensor networks”, in Proc. IEEE INFOCOM, pp. 1323–1331, 2011.
[3] K. Han, Y. Liu, and J. Luo, “Duty-Cycle-Aware Minimum-Energy Multicasting in Wire-
less Sensor Networks,” IEEE/ACM Transactions on Networking, vol. 21, no. 3, pp.
910–923, 2013.
[4] L. Kou, G. Markowsky, and L. Berman, “A fast algorithm for Steiner trees”, Acta Infor-
matica, vol. 15, no. 2, pp. 141–145, 1981.
[5] D. S. Johnson, “Approximation algorithms for combinatorial problems”, in Proc. ACM
STOC, pp. 38–49, 1973.
[6] L. Su, B. Ding, Y. Yang, T. F. Abdelzaher, G. Cao, and J. C. Hou, “ocast: Optimal
multicast routing protocol for wireless sensor networks”, in Proc. IEEE ICNP, pp. 151–
160, 2009.
[7] M. R. Garey, and D. S. Johnson, Computers and Intractability: A Guide to the Theory
of NP-Completeness, W. H. Freeman, New York, 1979.
[8] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms,
Third edition, The MIT Press, Cambridge, 2009.
[9] S. Guo, Y. Gu, B. Jiang, and T. He, “Opportunistic flooding in low-duty-cycle wireless
sensor networks with unreliable links,” in Proc. ACM MobiCom, pp. 133–144, 2009.
[10] G. Anastasi, M. Conti, M. D. Francesco, and A. Passarella, “Energy conservation in
wireless sensor networks: A survey,” Ad Hoc Networks, vol. 7, no. 3, pp. 537–568, 2009.
[11] C. Gui, and P. Mohapatra, “Power conservation and quality of surveil-lance in target
tracking sensor networks", in Proc. ACM MobiCom, pp. 129–143, 2004.
[12] T. He, P. Vicaire, T. Yan, Q. Cao, G. Zhou, L. Gu, L. Luo, R. Stoleru, J. A. Stankovic,
and T. F. Abdelzaher, “Achieving long-term surveillance in vigilnet,” in Proc. IEEE
INFOCOM, pp. 1–12, 2006.
[13] L. Mo, Y. He, Y. Liu, J. Zhao, S. Tang, X.-Y. Li, and G. Dai, “Canopy closure estimates
with greenorbs: sustainable sensing in the forest”, in Proc. ACM SenSys, pp. 99–112,
2009.
266 NGUYỄN THÁI DƯƠNG, HUỲNH THỊ THANH BÌNH, NGÔ HỒNG SƠN
[14] J. Wieselthier, G. Nguyen, and A. Ephremides, “On the construction of energy-efficient
broadcast and multicast trees in wireless networks”, in Proc. IEEE INFOCOM, pp.
585–594, 2000.
[15] P.-J. Wan, G. Calinescu, and C.-W. Yi, “Minimum-power multicast routing in static ad
hoc wireless networks”, IEEE/ACM Trans. Netw., vol. 12, no. 3, pp. 507–514, 2004.
[16] W. Liang, “Approximate minimum-energy multicasting in wireless ad hoc networks,”
IEEE Trans. Mobile Comput., vol. 5, no. 4, pp. 377–387, 2006.
[17] D. Li, Q. Liu, X. Hu, and X. Jia, “Energy efficient multicast routing in ad hoc wireless
networks”, Computer Communications, vol. 30, no. 18, pp. 3746–3756, 2007.
[18] G. Ausiello, A. D’Atri, and M. Protasi, “Structure preserving reductions among convex
optimization problems,” Journal of Computer and System Sciences, vol. 21, no. 1, pp.
136–153, 1980.
[19] B. Awerbuch, “Distributed Shortest Paths Algorithms (Extended Abstract)”, in Proc.
ACM STOC, pp. 490–500, 1989.
Ngày nhận bài 26 – 9 – 2013
Nhận lại sau sửa 26 – 7 – 2014