ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Vũ Anh Hải ĐIỀU KHIỂN TỐI ƯU CẤU HÌNH TRONG MẠNG VÔ TUYẾN AD HOC - SENSOR LUẬN VĂN THẠC SĨ Hà Nội - 2008 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Vũ Anh Hải Điều khiển tối ưu cấu hình mạng vơ tuyến Ad hoc - Sensor Ngành: Công nghệ Điện tử — Viễn thông Chuyên ngành: Kỹ thuật điện tử Mã số: 60 52 70 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC PGS TS Trần Hồng Quân Hà Nội - 2008 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com MỤC LỤC Danh mục chữ viết tắt Danh sách hình Danh sách bảng Mở đầu Chương Tổng quan mạng Ad hoc – Sensor 1.1 Tương lai truyền thông vô tuyến 1.1.1 Mạng ad hoc 1.1.2 Mạng cảm biến không dây 11 1.2 Những thách thức 13 1.2.1 Mạng ad hoc 13 1.2.2 Mạng cảm biến không dây 14 1.3 Kết luận 16 Chương Mơ hình mạng Ad hoc 17 2.1 Kênh vô tuyến 17 2.1.1 Mơ hình truyền dẫn khơng gian tự 18 2.1.2 Mơ hình hai – tia mặt đất (two-ray ground model) 19 2.1.3 Mơ hình logarit – khoảng cách (log-distance path) 20 2.1.4 Mơ hình biến thiên rộng (large – scale) biến thiên hẹp (small – scale) 21 2.2 Graph thông tin 22 2.3 Mô hình tiêu thụ lượng 25 2.3.1 Mạng Ad hoc 25 2.3.2 Mạng sensor 27 2.4 Mơ hình di động 28 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 2.4.1 Mơ hình điểm đích ngẫu nhiên (Random waypoint model) 29 2.4.2 Mơ hình hướng ngẫu nhiên (Random dierection model - RD) 30 2.4.3 Chuyển động Brownian-like (Brownian-like motion) 31 2.4.4 Chuyển động theo đồ (map-based mobility) 31 2.4.5 Chuyển động theo nhóm (Group-based mobility) 33 2.5 Asymptotic Notation (Ký hiệu tiệm cận) 34 2.6 Kết luận 35 Chương Điều khiển cấu hình 36 3.1 Điều khiển cấu hình biến đổi lượng 36 3.2 Điều khiển cấu hình dung lượng mạng 38 3.3 Taxonomy điều khiển cấu hình 41 3.4 Điều khiển cấu hình Protocol Stack 43 3.4.1 Điều khiển cấu hình định tuyến 44 3.4.2 Điều khiển cấu hình MAC 45 3.5 Kết luận 48 Chương Điều khiển tối ưu cấu hình 49 4.1 Xác định toán 50 4.2 Ấn định khoảng mạng chiều 51 4.3 Ấn định khoảng mạng hai chiều 54 4.4 Tính đối xứng 56 4.4.1 Tính đối xứng mạng chiều 58 4.4.2 Tính đối xứng mạng hai chiều 59 4.4.3 Các thuật toán xấp xỉ cho WSRA 64 4.5 Mục tiêu lượng 65 4.6 Unicast hiệu lượng 66 4.7 Broadcast hiệu lượng 72 4.8 Kết luận 75 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Kết luận 77 Tài liệu tham khảo 79 Chỉ mục 84 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com DANH MỤC CHỮ VIẾT TẮT ACK Acknowledgement BIP Broadcast Incremental Power CTR critical transmitting range CTS Clear to Send DSR Dynamic Source Routing DT Delaunay Triangulation GG Gabriel Graph GPS Global Positioning System MAC Medium Access Control NAV Network Allocation vector RA Range Assignment RD Random dierection RNG Relative Neighborhood Graph RTD Restricted Delaunay Triangulation RTS Request To Send RWP Random WayPoint SRA Symmetric Range Assignment WSN Wireless Sensor Network WSRA Weakly Symmetric Range Assignment YG Yao Graph LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com DANH SÁCH HÌNH Hình 2-1 Mơ hình hai – tia mặt đất 20 Hình 2-2 Vùng phủ sóng vơ tuyến 23 Hình 2-3 RWP chuyển động hướng ngẫu nhiên 33 Hình 2-4 Chuyển động map-based 34 Hình 3-1 Truyền thơng đa chặng 37 Hình 3-2 Mâu thuẫn truyền thông không dây 38 Hình 3-3 Truyền thơng đa chặng 40 Hình 3-4 Một taxanomy kỹ thuật điều khiển cấu hình 42 Hình 3-5 Điều khiển cấu hình Protocol Stack 44 Hình 3-6 Tương tác điều khiển cấu hình định tuyến 45 Hình 3-7 Mức độ quan trọng cài đặt phù hợp 46 Hình 3-8 Tương tác điều khiển cấu hình lớp MAC 47 Hình 4-1 Các cạnh ngược hướng tập cạnh E2,5 51 Hình 4-2 Thuật tốn tìm ấn định khoảng tối ưu mạng chiều 54 Hình 4-3 Cây tối thiểu T ấn định khoảng tương ứng 55 Hình 4-4 Các yêu cầu khác toán WSRA WRA 57 Hình 4-5: Một cải tiến (gadget) cạnh ܽ, ܾ 61 Hình 4-6 Ví dụ tốn ܴܿܵܿ‫ )݊(ߗ ∈ ܣ‬ 65 Hình 4-7 Graph công suất cực đại hệ số co giãn lượng 67 Hình 4-8 Thuật tốn xây dựng Graph GABRIEL 71 Hình 4-9 Điều kiện cạnh nằm graph 71 Hình 4-10 Thuật toán Broadcast Incremental Power 74 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com DANH SÁCH BẢNG Bảng 2-1: Giá trị ߙ môi trường khác 21 Bảng 2-2 Mức tiêu hao công suất card vô tuyến IEEE 802.11 26 Bảng 2-3 Công suất tiêu hao nút cảm biết Rockwell’s WINS 28 Bảng 4-1 Hệ số co giãn khoảng cách graph xấp xỉ khác 70 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com MỞ ĐẦU Đ ẦU Mạng vô tuyến ad hoc – sensor cách tổ chức mạng mới, nhà nghiên cứu nước ý năm gần Do đặc thù, mạng địi hỏi phải có tính linh hoạt hiệu sử dụng lượng mạng cao Chính lí đó, luận văn tập trung vào nghiên cứu số vấn đề tối ưu cấu hình mạng, tối ưu hiệu lượng – chủ đề nhiều người quan tâm mạng ad hoc – sensor Bản luận văn chia thành chương Chương – Tổng quan mạng Ad hoc – Sensor: Giới thiệu khái quát mạng ad hoc sensor, đưa tiềm mạng ad hoc sensor thách thức gặp phải Chương – Mô hình mạng Ad hoc: Giới thiệu mơ hình sử dụng để xây dựng giải tốn điều khiển cấu hình, tối ưu lượng mạng ad hoc –sensor Gồm mơ hình: Các mơ hình kênh vơ tuyến, mơ hình tiêu thụ lượng, mơ hình di động Chương – Điều khiển cấu hình: Giới thiệu vấn đề liên quan đến điều khiển cấu hình mạng ad hoc – sensor biến đổi lượng, dung lượng mạng, … Chương – Điều khiển tối ưu cấu hình: Xây dựng giải số toán điều khiển tối ưu cấu hình, tối ưu ấn định khoảng, tối ưu tính đối xứng mạng tối ưu hiệu lượng LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương TỔNG QUAN VỀ MẠNG AD HOC — SENSOR Chương giới thiệu ngắn gọn mạng vô tuyến ad hoc and sensor, mô tả số ứng dụng khả thi công nghệ tương lai gần Chương đề cập đến thách thức mặt công nghệ cần giải trước loại mạng thực triển khai diện rộng 1.1 Tương lai truyền thông vô tuyến Năng lực hạ tầng thông tin với thiết bị tính tốn thơng tin di động liên tục cải tiến thúc đẩy phát triển mạnh mẽ mạng vô tuyến di động, đồng thời điều kiện cho bùng nổ mạng cellular dựa kết hợp hai công nghệ: vô tuyến hữu tuyến Theo thống kê đến cuối năm 2005, số lượng người sử dụng mạng cellular lên đến tỷ Mặc dù nghiên cứu ứng dụng mạng không dây truyền thống sử dụng hạ tầng mạng cố định xu hướng tiếp tục phát triển, ngành công nghiệp thông tin bắt đầu chuyển sang nghiên cứu mạng vô tuyến di động mà nhóm thiết bị di động liên kết với mà không sử dụng hạ tầng mạng cố định, mạng gọi mạng ad hoc 1.1.1 Mạng ad hoc Mạng ad hoc phát triển cao thông tin vô tuyến, mạng nút (node) liên kết trực tiếp với thông qua thu phát không dây (wireless transceiver) mà không sử dụng hạ tầng mạng cố định Đây đặc tính riêng biệt mạng ad hoc so với mạng không dây LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 71 check whether v ∈ disk(u,w) if yes, then remove (u,w) from EGG(u) Termination after processing all incoming messages, EGG(u) contains all the edges of GG incident in u Hình 4-8 Thuật tốn xây dựng Graph GABRIEL Hình 4-9 Cạnh (u, v) nằm graph hình trịn có đường kính cạnh (u, v) không chứa nút Mặc dù GG tối ưu hệ số co dãn công suất, bậc cực đại nút n-1 Cách thực tương tự cho graph khác liệt kê Bảng 4-1 Với vài lý do, vài biến thể graph xấp xỉ đề xuất trên, với mục đích để cận bậc nút số Thật không may, khơng có graph hình học với bậc nút chặn số lại chứa đường công suất tối thiểu cho cặp nút [39] Hơn nữa, khơng có tối ưu cơng suất với bậc cực đại nút có chặn số Ngày nay, graph định tuyến với bậc cực đại nút có chặn số có hệ số co dãn công suất tốt graph OrdYaoGG, graph [37], graph có cách xây dựng graph YGc với c > 6, đỉnh GG Graph OrdYaoGG có hệ số co dãn cơng suất với ρ = ‫= ݔ‬ ଵ ഏ ଵି(ଶୱ୧୬ ೎ )ഀ bậc cực đại nút c + với LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 72 c > 6, tham số graph Yao Ví dụ đặt c = α = 2, ta có hệ số co dãn cơng suất 1.88 với cận bậc nút cực đại 14 Mặc dù OrdYaoGG xây dựng theo cách hồn tồn phân tán cục bộ, việc tính tốn địi hỏi trao đỏi lượng lớn tin nhắn (24 n trường hợp xấu nhất) Vì lý này, tác giả [37] kiến nghị graph SyYaoGG phiên đơn giản hố OrdYaoGG xây dựng mà phải trao đổi cực đại 3n tin nhắn Tỉ lệ co dãn lượng graph ߩ = √ଶഀ ഏ ଵି(ଶ√ଶ௦௜௡ ೎ )ഀ bậc nút cực đại c, với ܿ > tham số đồ thị Yao Cho ܿ = ߙ = trên, ta có tỉ lệ co dãn lượng 31.16 bậc nút cực đại 4.7 Broadcast hiệu lượng Một toán khác xem xét lĩnh vực xác định tô pô broadcast hiệu lượng Cho graph maxpower ‫ܩ‬, mục tiêu xác định graph thưa ‫ܩ‬′ thuộc ‫( ܩ‬graph quảng bá) cho việc quảng bá ‫ܩ‬′ có hiệu lượng quảng bá graph maxpower Ở đây, lợi sử dụng graph thưa graph maxpower làm tô pô quảng bá giảm tượng tiếng mang tên dội bom quảng bá Hiện tượng xảy nhiều nút lân cận gửi tin nhăn đồng thời, kết dư thừa mức, tranh dành băng thông, đụng độ Khái niệm nhân tố co dãn quảng bá: Hãy xét graph thông tin maxpower ‫ܩ‬ Bất kỳ đợt phát tin quảng bá sinh nút ‫ ݑ‬có thể xem mở rộng trực tiếp ܶ ‫ ܩ‬có gốc ‫ݑ‬, mà ta gọi quảng bá Chi phí lượng quảng bá ܶ định nghĩa sau Ký hiệu ‫)ݒ(ܶܿ݌‬ lượng mà nút lượng mà nút ‫ ݒ‬tiêu tốn để phát quảng bá tin nhắn ܶ, ta có ‫ = )ݒ( ܶܿ݌‬0 ‫ ݒ‬là ܶ, trường hợp khác ߙ ‫ݒ(ݔܽ݉ = )ݒ( ܶܿ݌‬,‫ ܶ∈)ݓ‬δ(‫ݑ‬, ‫ )ݒ‬ Tổng lượng cần thiết để phát tin quảng bá quảng bá ܶ ‫∑ = )ܶ(ܿ݌‬௩∈ே ‫)ݒ( ்ܿ݌‬ Ta gọi chi phí chi phí lượng ܶ Cây G có gốc ‫ ݑ‬với chi phí lượng thấp gọi quảng bá lượng cực tiểu ‫ݑ‬, ký hiệu ܶ݉݅݊,‫ܩ‬ ‫ݑ‬ Định nghĩa 4.7-1 (nhân tố co dãn quảng bá) Gọi ‫ܩ‬′ graph ngẫu nhiên graph maxpower ‫ܰ( = ܩ‬, ‫)ܧ‬ Nhân tố co dãn quảng bá ‫ܩ‬′ theo ‫ܩ‬, ký LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 73 hiệu bới ߚ‫ܩ‬′ giá trí cực đại tất nút quảng bá lượng cực tiểu thuộc ‫ܩ‬′ thuộc ‫ܩ‬ ߚ‫ܩ‬′ = ݉ܽ‫ܰ∈ݑݔ‬ ݉݅݊,‫ܩ‬′ ‫ݑܶ(ܿ݌‬ ) ݉݅݊,‫ܩ‬ ‫) ݑܶ(ܿ݌‬ Định nghĩa 4.7-2 (Khung quảng bá) Cho ‫ܰ( = ܩ‬, ‫ )ܧ‬là graph maxpower, với |ܰ| = ݊ Một graph ‫ܩ‬′ ‫ ܩ‬được gọi khung quảng bá ‫ ܩ‬nếu ߚ‫ܩ‬′ ∈ ܱ(1) Tương tự trường hợp unicast, mục đích tìm khung quảng bá thưa ‫ ܩ‬mà tính tốn theo cách phân tán cục Khơng may nhiệm vụ trở nên khó khăn so với trường hợp truyền thơng unicast Khó khăn nảy sinh từ thực tế tính tốn quảng bá lượng cực tiểu nút cho trước tốn có độ khó ܰܲ với giả thiết nút sử dụng tập mức lượng rời rạc ൛ܲ1 , ⋯ , ܲ݇ ൟ Do tính tốn trực tiếp nhân tố co dãn quảng bá cho graph cho trước ‫ܩ‬′ thuộc G khơng thể, điều đỏi hỏi phải giải tốn NP − khó Biết trước khó khăn này, vài tác giả đưa lời giải heuristic xấp xỉ giải pháp tối ưu cho toán quảng bá lượng cực tiểu Một lời giải phổ biến thế, mà ta trình bày phần sau, thuật tốn quảng bá với lượng tăng dần (BIP - Broadcast Incremental Power) cơng bố vào năm 2000 Thuật tốn BIP, trình bày Hình 4-10, biến thể thuật tốn Prim tiếng để tìmcây khung bé Thuật tốn bắt đầu cách tìm nút mà nút nguồn u đến với tới với lượng tối thiểu Nút thêm vào tập C nút đã duyệt, nghĩa là, nút nhận tin quảng bá Tại bước tổng quát ݅, BIP xem xét tất nút chưa duyệt, với nút ‫ ݒ‬như thế, tính toan phần chi phí phụ trội để thêm ‫ݒ‬ ഥ với chi phí phụ trội nhỏ thêm vào vào khung Nút ‫ݒ‬ tập nút duyệt, thuộc vào khung Quá trình lặp lặp lại tất nút duyệt Trong [38] tỉ lệ xấp xỉ BIP 13 12 Do vậy, khung quảng bá G xây dựng sau: với nút u thuộc G, áp LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 74 dụng thuật tốn BIP để xây dựng quảng bá Tu có gốc u Cho GBIP = ⋃u∈N Tu , nghĩa là, cạnh (‫ݑ‬, ‫ )ݒ‬thuộc vào GBIP thuộc vào quảng bá tính tốn bới BIP Biết BIP xấp xỉ lời giải tối ưu (được xây dựng dựa graph maxpower) tối đa 12 lần, điều suy ra, với ‫ܰ ∈ ݑ‬, GBIP chứa quảng bá có gốc u với chi phí cực đại ܱ(1) lần chi phí tối ưu; nghĩa là, GBIP khung quảng bá ‫ܩ‬ Không may GBIP nhìn chung khơng phải graph thưa Hơn nữa, BIP thuật tốn tập trung địi hỏi phải có tri thức tồn cục (nó địi hỏi phải biết tập ܰ nút mạng) Thuật toán Broadcast Incremental Power: u C T N is is is is the the the the source node set of currently covered nodes current spanning tree set of network nodes Initialization C = {u} T = {u} Repeat until C = N for each node v ∈ N − C, compute the incremental cost ic(v) of adding v to T let v be the node in N − C with minimal incremental cost C = C∪{v} add v in the current spanning tree T Termination when C = N, T is a broadcast spanning tree rooted at u Hình 4-10 Thuật tốn Broadcast Incremental Power Một graph khác sử dụng để xây dựng khung quảng bá khung bé nhất, xấp xỉ quảng bá lượng cực tiểu với sai số từ đến 12 lần Khơng may tính tốn khung bé địi hỏi tri thức tồn cục Để tránh vấn đề này, [27] đề nghị phiên thuật tốn cục hố, hồn tồn phân tán xây dựng xấp xỉ cục khung bé Thuật tốn có tên gọi ‫ ݇ܶܵܯܮ‬, đòi hỏi trao đổi ܱ(݊) tin nhắn (dù số ẩn lớn 225), xây dựng xấp xỉ quảng bá tối ưu với sai số ܱ(݊ఈିଵ ) Do vậy, ‫ ݇ܶܵܯܮ‬khơng thể sử dụng để tính khung quảng bá ‫ܩ‬ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 75 Tóm lại, tốn thiết kế thuật tốn phân tán cục sử dụng để xây dựng khung quảng bá ‫ ܩ‬và giữ nguyên tính mở Trước kết thúc phần này, muốn vạch tương tự toán gán miền thảo luận chương toán quảng bá hiệu mặt lượng Giả sử ‫ ܩ‬là graph maxpower tập đỉnh ܰ Trong toán ܴ‫ܣ‬, mục tiêu tìm phép gán miền tối ưu lượng sinh graph thông tin liên thông Giả thiết nút ‫ ܰ ∈ ݑ‬muốn phát tin quảng bá ݉, cho ܴ‫ ܣ‬là phép gán miền tối ưu Một lược đồ phát tin quảng bá đơn giả theo kiểu vết dầu loang: nút ‫ ݑ‬truyền ݉ tới khoảng cách ܴ‫)ݑ(ܣ‬, nút ‫ ݒ‬sau nhận ݉ lần đầu tiên, rẽ truyền lại tới khoảng cách ܴ‫)ݒ(ܣ‬ Có thể thấy sau tất nút thuộc ܰ truyền tin nhắn lần ݉ quảng bá tồn mạng Do vậy, chi phí lượng ܴ‫ ܣ‬là cận cho chi phí lượng quảng bá ‫ܩ‬ Chúng ta nhắc lại chi phí lượng thuật tốn gán miền tối ưu (và thuật toán gán miền đối xứng yếu tối ưu) khác với chi phí thuật tốn khung lớn nhiều lần Do thuật toán khung bé khung quảng bá G, điều suy graph thông tin sinh phép gán miền tối ưu (đối xứng yếu) khung quảng bá G Đáng tiếc điều khơng có ý nghĩa lắm, việc tính tốn cho graph mạng hay chiều có độ khó ܰܲ 4.8 Kết luận Việc sử dụng hiệu nguồn lượng quý sẵn có cho nút mạng ad hoc sensor nhiệm vụ người thiết kế mạng Bởi lẽ nút tiêu thụ lượng lượng đáng kể để phát/ nhận thông điệp (điều thật trường hợp mạng sensor), nên việc giảm lượng tiêu thụ truyền sóng vơ tuyến vấn đề quan trọng Phần giải số tốn tối ưu chi phí lượng ấn định khoảng mạng chiều, mạng hai chiều, tối ưu tính đối xứng giới thiệu thuật tốn xấp xỉ cho WSRA Ngồi ra, chương LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 76 đưa số thuật toán giải toán tối ưu lượng tiêu thụ số kiểu truyền thông truyền thống unicast broadcast LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 77 KẾT LUẬN Mạng vô tuyến ad hoc – sensor cách tổ chức mạng mới, nhà nghiên cứu nước ý năm gần Do đặc thù, mạng đòi hỏi phải có tính linh hoạt hiệu sử dụng lượng mạng cao Do mạng ad hoc – sensor, tối ưu cấu hình mạng, tối ưu hiệu lượng, tối ưu tốc độ kết nối, nâng cao độ tin cậy mạng …, chủ đề dành nhiều quan tâm Với định hướng trên, luận văn viết với mục đích nghiên cứu, tìm hiểu giải số tốn điều khiển tối ưu cấu hình mạng ad hoc sensor, cụ thể toán tối ưu chi phí lượng truyền tín hiệu thơng tin giảm mức tiêu hao lượng nút mạng Để đạt mục tiêu đề ra, luận văn cấu trúc thành chương, có nội dung sau đây: Sau giới thiệu giới thiệu ngắn gọn mạng ad hoc sensor, Chương trình bày ứng dụng khả thi mà loại mạng áp dụng tương lai gần Tuy nhiên để triển khai diện rộng, cịn nhiều khó khăn mặt công nghệ cần phải giải vấn đề tối ưu chi phí lượng, chất lượng truyền tín hiệu thấp, khả mở rộng kém, … Nhiệm vụ dành cho nhà nghiên cứu khoa học ứng dụng Trước vào tìm hiểu điều khiển cấu hình mạng ad hoc – sensor, cần phải mơ hình hóa loại mạng cho phù hợp dễ dàng nghiên cứu Do chúng thường mạng đa chặng, phức tạp nên mơ hình tổng thể cần phải xây dựng từ mơ hình Chương giới thiệu mơ hình nhất, thích hợp sử dụng để xây dựng giải tốn điều khiển cấu hình gồm mơ hình: Các mơ hình kênh vơ tuyến, mơ hình tiêu thụ lượng, mơ hình di động LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 78 Chương (Chương 3) đưa số khái niệm ban đầu điều khiển cấu hình Để làm rõ điều khiển cấu hình, số ví dụ cụ thể trình bày điều khiển cấu hình biến đổi lượng, điều khiển cấu hình quan điểm dung lượng mạng Qua ví dụ đó, ta thấy hiệu to lớn việc áp dụng kỹ thuật điều khiển cấu hình để tối ưu mạng ad hoc – sensor Trong chương giới thiệu nguyên tắc phân loại phương pháp tiếp cận tốn điều khiển cấu hình, cách thức tích hợp chế điều khiển cấu hình vào protocol stack Như trình bày, mạng ad hoc – sensor nhiều thách thức mặt công nghệ cần phải giải quyết, vấn đề quan trọng tối ưu lượng mạng Chương cuối luận văn chương trọng tâm (Chương 4) xây dựng giải số tốn tối ưu chi phí lượng ấn định khoảng mạng chiều, mạng hai chiều, tối ưu tính đối xứng giới thiệu thuật tốn xấp xỉ cho WSRA Ngoài ra, chương đưa số thuật toán giải toán tối ưu lượng tiêu thụ số kiểu truyền thông truyền thống unicast broadcast Hướng nghiên cứu − Nghiên cứu thuật tốn tối ưu tơ-pơ mạng để đạt mục tiêu kết nối nhanh, đạt hiệu lượng cao − Đánh giá độ tin cậy mạng LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 79 TÀI LIỆU THAM T HAM KHẢO [1] Althaus E, Calinescu G, Mandoiu I, Prasad S, Tchervenski N, Zelikovsky A, 2003 Power efficient range assignment in ad hoc wireless networks Proc IEEE WCNC 03, New Orleans, LA, pp 1889– 1894 [2] Bai F, Sadagopan N, Helmy A 2003 Important: a framework to systematically analyze the impact of mobility on performance of routing protocols for ad hoc networks Proc IEEE Infocom, San Francisco, CA, pp 825–835 [3] Bettstetter C 2001a Mobility modeling in wireless networks: categorization, smooth movement, and border effects ACM Mobile Computing and Communications Review 5(3), 55–67 [4] Bettstetter C 2001b Smooth is better than sharp: a random mobility model for simulation of wireless networks Proc ACM Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM), Rome, pp 19–27 [5] Bettstetter C and Krause O 2001 On border effects in modeling and simulation of wireless ad hoc networks Proc IEEE International Conference on Mobile and Wireless Communication Network (MWCN), Recife [6] Bettstetter C, Resta G and Santi P 2003 The node distribution of the random waypoint mobility model for wireless ad hoc networks IEEE Transactions on Mobile Computing 2(3), 257–269 [7] Blough D, Leoncini M, Resta G and Santi P 2002 On the symmetric range assignment problem in wireless ad hoc networks Proc IFIP Conference on Theoretical Computer Science, Montreal, pp 71–82 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 80 [8] Blough D, Resta G and Santi P 2004 A statistical analysis of the longrun node spatial distribution in mobile ad hoc networks Wireless Networks 10, 43–554 [9] Bluetooth 1999 Bluetooth specifications available at http://www.bluetooth.org [10] Bose P, Morin P, Stojmenovic I and Urrutia J 2001 Routing with guaranteed delivery in ad hoc wireless networks Wireless Networks 7(6), 609–616 [11] Camp T, Boleng J and Davies V 2002 Mobility models for ad hoc network simulations Wiley Wireless Communication & Mobile Computing (WCMC) 2(5), 483–502 [12] Clementi A, Penna P and Silvestri R 1999 Hardness results for the power range assignment problem in packet radio networks Proc 2nd International Combinatorial Workshop on Optimization Approximation Problems Algorithms for (RANDOM/APPROX’99), Berkeley, CA, pp 197–208 [13] Gao J, Guibas L, Hershberger J, Zhang L and Zhu A 2001 Geometric spanners for routing in mobile networks Proc ACM MobiHoc 01, Long Beach, CA, pp 45–55 [14] Garey M and Johnson D 1977 The rectilinear steiner tree problem is np-complete SIAM Journal of Applied Mathematics 32, 826–834 [15] Goodman J and O’Rourke J 1997 Handbook of Discrete and Computational Geometry CRC Press, New York [16] Gupta P and Kumar P 2000 The capacity of wireless networks IEEE Transactions Information Theory 46(2), 388–404 [17] Haas Z and Pearlman M 1998 The performance of query control schemes for the zone routing protocol Proc ACM Sigcomm, Vancouver, pp 167–177 [18] Hong X, Gerla M, Pei G and Chiang C 1999 A group mobility model for ad hoc wireless networks Proc ACM MSWiM, Seattle, WA, pp 53–60 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 81 [19] IEEE 1999 Ansi/IEEE Standard 802.11: Medium Access Control and Physical Specifications Sect 15 [20] Jardosh A, Belding-Royer E, Almeroth K and Suri S 2003 Towards realistic mobility models for mobile ad hoc networks Proc ACM Mobicom, pp 217–229 [21] Johnson D and Maltz D 1996 Dynamic source routing in ad hoc wireless networks Mobile Computing Kluwer Academic Publishers, pp 153–181 [22] Jung A and Vaidya N 2002 A power control mac protocol for ad hoc networks Proc ACM Mobicom, Atlanta, GA, pp 36–47 [23] Karp B and Kung H 2000 Gpsr: greedy perimeter stateless routing for wireless networks Proc ACM Mobicom, Boston, MA, pp 243–254 [24] Khun F, Wattenhofer R and Zollinger A 2003 Worst-case optimal and average-case efficient geometric ad hoc routing Proc ACM MobiHoc, Annapolis, MD, pp 267–278 [25] Kirousis L, Kranakis E, Krizanc D and Pelc A 2000 Power consumption in packet radio networks Theoretical Computer Science 243, 289–305 [26] Li X, Wan P, Wang Y and Frieder O 2002 Sparse power efficient topology for wireless networks Proc IEEE Hawaii International Conference on System Sciences (HICSS), Big Island, HI [27] Li X, Wang Y and Song W 2004 Applications of k-local mst for topology control and broadcasting in wireless ad hoc networks IEEE Transactions on Parallel and Distributed Systems 15(12), 1057–1069 [28] Ns2 2002 The network simulator - ns-2 http://www.isi.edu/nsnam/ns/ [29] Pearlman M, Haas Z, Sholander P and Tabrizi S 2000b On the impact of alternate path routing for load balancing in mobile ad hoc networks Proc ACM MobiHoc, Boston, MA, pp 3–10 [30] Pister K 2001 The smart dust project http://robotics.eecs.berkeley.edu/∼pister/SmartDust/ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 82 [31] Polastre J, Szewczyk R, Sharp C and Culler D 2004 The mote revolution: low power wireless sensor network devices Proc Hot Chips 16: A Symposium on High Performance Chips, Stanford, CA [32] Raghunathan V, Schurgers C, Park S and Srivastava M 2002 Energyaware wireless microsensor networks IEEE Signal Processing Magazine 19(2), 40–50 [33] Rappaport T 2002 Wireless Communications: Principles and Practice, Second Edition Prentice Hall, Upper Saddle River, NJ [34] RockwellScienceCenter 2004 The wins project available at http://wins.rsc.rockwell.com [35] Royer E, Melliar-Smith P and Moser L 2001 An analysis of the optimum node density for ad hoc mobile networks Proc IEEE International Conference on Communications, Helsinki, pp 857–861 [36] Santi P and Blough D 2003 The critical transmitting range for connectivity in sparse wireless ad hoc networks IEEE Transactions on Mobile Computing 2(1), 25–39 [37] Song W, Wang Y, Li X and Frieder O 2004 Localized algorithms for energy efficient topology in wireless ad hoc networks Proc ACM MobiHoc, Tokyo, pp 98–108 [38] Wan P, Calinescu G, Li X and Frieder O 2002 Minimum energy broadcasting in static ad hoc wireless networks ACM/Kluwer Wireless Networks 8(6), 607–617 [39] Wang K and Li B 2002 Group mobility and partition prediction in wireless ad hoc networks Proc IEEE International Conference on Communications, New York, pp 1017–1021 [40] Wang Y, Li X and Frieder O 2002 Distributed spanners with bounded degree for wireless ad hoc networks International Journal of Foundations of Computer Science, 14(2), pp 183–200 [41] Yoon J, Liu M and Noble B 2003 Random waypoint considered harmful Proc IEEE Infocom, San Francisco, CA, pp 1312–1321 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 83 [42] Zeng X, Bagrodia R and Gerla M 1998 Glomosim: a library for parallel simulation of large-scale wireless networks Workshop on Parallel and Distributed Simulations (PADS), Banff, Alberta LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 84 CHỈ MỤC A G ACK, 46 Asymptotic Notation, 34 avalanche prediction, 13 B Gabriel Graph, 69 GloMoSim, 29 GPS, 10 group-based mobility, 33 H bidirectional, 24 BIP, 73 Broadcast Incremental Power, 73 broadcast power, 43 Brownian-like, 31 C Clear to Send, 45 close-in distance, 19 communication graph, 24 connecting, 24 connecting at time t, 24 critical transmitting range, 41 CTS, 45 CTR, 41 D deffraction, 18 Delaunay Triangulation, 69 deployment region, 31 drunkardlike, 31 DSR, 29 DT, 69 E Energy conservation, 13 heterogeneous network, 10 highways, 10 Holder, 40 homogeneous, 24 hostile enviroment, 15 I instrution detection, 12 interference range, 39 interference region, 39 Interoperability, 14 L large-scale models, 21 location-aware information, 11 low-quality conmmunication, 13 M MAC, 45 Manhattan, 32 map-based mobility, 31 maximum transmitting range, 23 maxpower graph, 24 maxpower range assignment, 24 Medium Access Control, 45 MINWEIGHTEDVERTEXCOVER, 59 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 85 mobility, 10 multipath fading, 22 N RTS, 45 RWP, 29 S NAV, 46 neighbor, 24 Network Allocation vector, 46 NP-hard, 64 O Scalability, 14 scattering, 18 sensitivity threshold, 17 simple fading, 22 small-scale models, 22 smart sensor, 11 SRA, 57 Stationary, 12 symmetric, 24 symmetric neighbors, 24 Symmetric Range Assignment, 57 SyYaoGG, 72 T OPTIMAL1DRA, 53 OrdYaoGG, 71 P patterns, 28 path loss, 17 path loss exponent, 21 Protocol Stack, 43 Q quasistationary, 12 R r- homogeneous, 24 range assignement, 23 Range Assignment Problem, 49 RD, 30 reflection, 18 Relative Neighborhood Graph, 69 relatively dispersed network, 10 Request to Send, 45 resemble real-life movements, 28 resource-constrained computation, 14, 15 Restricted Delaunay Triangulation, 70 RNG, 69 RTD, 70 Taxonomy, 41 time-varying, 13 transmitting range, 23 U Ubiquitous Internet Access, 10 Untructured, 13 urban area, 10 W Weakly Symmetric Range Assignment, 58 weather forecast, 12 WSN, 11 WSRA, 58 Y Yao Graph, 69 YCc, 69 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com ... đến điều khiển cấu hình mạng ad hoc – sensor biến đổi lượng, dung lượng mạng, … Chương – Điều khiển tối ưu cấu hình: Xây dựng giải số tốn điều khiển tối ưu cấu hình, tối ưu ấn định khoảng, tối ưu. .. Điều khiển cấu hình Protocol Stack 43 3.4.1 Điều khiển cấu hình định tuyến 44 3.4.2 Điều khiển cấu hình MAC 45 3.5 Kết luận 48 Chương Điều khiển tối ưu cấu hình. .. download : add luanvanchat@agmail.com 35 2.6 Kết luận Trước giải tốn điều khiển tối ưu cấu hình, cần phải đưa mơ hình phù hợp để mơ hình hóa mạng ad hoc – sensor Một mạng ad hoc – sensor phức tạp mạng