ระบบเซลลูล่าร์
ระบบเซลลูล่าร์คือระบบของโทรศัพท์เคลื่อนที่ ซึ่งใช้เทคโนโลยีการสื่อสารไร้สายเป็นหัวใจสำคัญ มีการจัดสรรช่วงความถี่เฉพาะสำหรับระบบและมีการประยุกต์ใช้ความถี่หลายซ้ำหลายๆชุด โดยจัดสรรลงบนพื้นที่ให้บริการต่างๆกัน ซึ่งพื้นที่ให้บริการดังล่าวจะถูกเรียกว่า เซลล์ (Cell) โดยขนาดของเซลล์นั้นจะขึ้นอยู่กับปริมาณความหนาแน่นของผู้ใช้บริการต่อพื้นที่ คือ ถ้าเป็นบริเวณเมืองหลวงก็จำเป็นต้องใช้เซลล์ที่มีขนาดเล็กหลายๆ เซลล์เพื่อเพิ่มจำนวนช่องสัญญาณให้กับระบบในขณะที่บริเวณต่างจังหวัดอาจมีผู้ใช้บริการน้อยการกำหนดขนาดของเซลล์ให้มีขนาดใหญ่จะคุ้มในการลงทุนมากกว่า ( เซลล์ขนาดเล็กนั้นมีความหนาแน่นมากกว่าเซลล์ขนาดใหญ่เมื่อพื้นที่การให้บริการเท่ากัน )
แสดงการใช้ความถี่ของระบบเซลลูล่าร์ในแต่ละเซลล์
เซลล์จะถูกให้บริการได้โดยสถานีฐาน (Base Station) ซึ่งสามารถติดต่อกับ ตัวเครื่องโมบายล์ (Mobile Station) ตัวเครื่องโมบายล์คืออุปกรณ์ต่างๆที่ใช้ในการติดต่อสื่อสารในระบบเซลลูล่าร์ การติดต่อระหว่างสถานีฐานกับตัวเครื่องโมบายล์จะใช้ช่องสัญญาณ 2 แบบ แบบ forward (downlink) กับ reverse (uplink) ช่องสัญญาณแบบ forward นั้นใช้ส่งข้อมูลจากสถานีฐานไปยังตัวเครื่องโมบายล์ ส่วนช่องสัญญาณแบบ reverse ใช้ส่งข้อมูลจากตัวเครื่องโมบายล์ไปยังสถานีฐาน โดยช่องสัญญาณทั้ง 2 แบบนั้นจะถูกแบ่งเป็นช่องสัญญาณสำหรับควบคุม (control channel) ใช้สำหรับติดตั้ง (setup) การเชื่อมต่อ และช่องสัญญาณเสียง (voice or data channel) ใช้สำหรับการส่งข้อมูล
แสดงช่องสัญญาณระหว่างสถานีฐานกับตัวเครื่องโมบายล์
การใช้สัญญาณที่ต่ำกับความถี่ค่าหนึ่งของเซลล์แรกในการพาสัญญาณเสียงพูด ทำให้ระบบโทรศัพท์เคลื่อนที่สามารถนำสัญญาณความถี่เดียวกันนี้ไปใช้กับช่องสัญญาณเสียงพูดของเซลล์อีกเซลล์หนึ่งที่อยู่ถัดออกไป แต่ไม่ติดกับเซลล์แรกได้โดยมีสัญญาณรบกวนระหว่างกันน้อยที่สุด เป็นหลักการใช้ความถี่ซ้ำหรือหลักการนำความถี่มาใช้ใหม่ (Frequency Reuse) ทำให้ใช้ความถี่ได้อย่างมีประสิทธิภาพมากขึ้นและเพิ่มความสามารถในการบริการลูกข่ายของระบบเซลลูล่าร์ให้มีมากขึ้นเมื่อเทียบกับระบบวิทยุสื่อสารทั่วไป
เมื่อพิจารณาขณะที่เครื่องลูกข่ายเริ่มใช้โทรศัพท์เคลื่อนที่จากเซลล์หนึ่ง ไปยังเซลล์ถัดไป ระบบเซลลูล่าร์จะสามารถทราบได้ว่าสัญญาณที่มีการติดต่อของโทรศัพท์เครื่องแรกมีระดับความแรงของสัญญาณอ่อนลงจนถึงค่าหนึ่ง ระบบจะทำการโอนถ่ายช่องสัญญาณการสนทนาของเครื่องลูกข่ายดังกล่าวไปยังเซลล์ถัดไปโดยอัตโนมัติตามทิศทางที่เครื่องลูกข่ายเดินทางไป โดยไม่มีการขัดจังหวะของสัญญาณ ซึ่งเป็นเทคนิคที่เรียกว่า แฮนด์ออฟ (Handoff) หรือ แฮนด์โอเวอร์ (Hand over) ในขณะสนทนาคู่สนทนาทั้งสองฝ่ายจะอยู่บนช่องสัญญาณเสียง ที่สถานีฐานกำหนดให้เมื่อเครื่องลูกข่ายเดินทางออกไปนอกบริเวณที่ให้บริการของสถานีแรก การรับส่งสัญญาณระหว่างตัวเครื่องกับสถานีจะอ่อนลงสถานีแรกก็จะทำการแฮนด์ออฟไปยังชุมสาย ถ้าในสถานีฐานถัดไปมีช่องสัญญาณ ระบบจะทำการสลับช่องสัญญาณเสียงไปยังสถานีใหม่ โดยไม่มีการขัดจังหวะการสนทนา
แสดงการเดินทางของโมบายล์
โครงสร้างพื้นฐานของระบบเซลลูล่าร์
ตัวเครื่องโมบายล์ (Mobile Station)
ตัวเครื่องโมบายล์คืออุปกรณ์ต่างๆที่ใช้ในการติดต่อสื่อสารในระบบเซลลูล่าร์ มีส่วนแตกต่างจากโทรศัพท์ทั่วไปตรงที่มี หน่วยควบคุม ตัวรับและส่งสัญญาณคลื่นวิทยุ (Transceiver) และระบบสายอากาศ (Antenna System) ตัวโมบายล์จะสามารถตรวจสอบระดับสัญญาณในบริเวณที่เครื่องอยู่ได้ มีอัลกอริทึมหรือโปรแกรมสำหรับติดต่อกับสถานีฐาน , ส่วนควบคุมสถานีฐานและชุมสายโทรศัพท์เคลื่อนที่
สายอากาศ (Antenna)
สายอากาศหากพิจารณาที่ตัวเครื่องโมบายล์ก็เป็นเพียงสายอากาศขนาดเล็ก แต่ผู้ผลิตตัวเครื่องก็พัฒนารูปแบบของสายอากาศสำหรับตัวเครื่องออกมาเป็นจำนวนหลายรูปแบบ แต่สายอากาศที่สำคัญก็คือสายอากาศที่ตั้งอยู่เหนือสถานีฐาน ซึ่งเชื่อมต่อสัญญาณรูปแบบของสายอากาศทิศทางการรับ/ส่งสัญญาณ
ส่วนประกอบเบื้องต้นของระบบเซลลูล่าร์
สถานีฐาน (Base Station or Base Transceiver Station)
สถานีฐานจะทำหน้าที่เชื่อมต่อสัญญาณระหว่างส่วนควบคุมสถานีฐานกับตัวโมบายล์ โดยจะมีหน่วยควบคุมเช่นกัน มีวงจรอิเล็กทรอนิกส์สำหรับประมวลผลสัญญาณคลื่นวิทยุ มีระบบสายอากาศซึ่งต่อออกมาจากส่วนควบคุมคลื่นวิทยุมีช่องต่อกับเทอร์มินัล เพื่อใช้ในการควบคุมและแก้ไขการติดตั้งอุปกรณ์แหล่งจ่ายไฟของสถานีฐานมีอยู่ 2 ระบบเป็นระบบจ่ายไฟฟ้าจากไฟฟ้าตามบ้านธรรมดาและระบบแบตเตอรี่ในยามฉุกเฉิน
สายส่งสัญญาณ (Transmission Link)
การติดต่อระหว่างสถานีฐานกับตัวโมบายล์กระทำการผ่านทางคลื่นแม่เหล็กไฟฟ้า แต่สำหรับการติดต่อสื่อสารระหว่างสถานีฐานกับชุมสายจะมีได้หลายรูปแบบเช่น ผ่านทางสัญญาณไมโครเวฟ ผ่านทางสายสัญญาณใยแก้วนำแสงหรืออาจจะผ่านดาวเทียมก็ได้ สายส่งสัญญาณดังกล่าวจะเป็นสายส่งที่มีความเร็วสูง ซึ่งภายในสายส่งหนึ่งลิงค์จะประกอบไปด้วยสัญญาณของคู่สนทนาจำนวนหลายช่องสัญญาณ ซึ่งถูกการมัลติเพล็กซ์ ( เสมือนเป็นการบีบข้อมูลให้เล็กลงก่อนส่งลงไปในสายสัญญาณ )
ส่วนควบคุมสถานีฐาน (Base Station Controller)
ส่วนควบคุมสถานีฐานจะมีการเชื่อมต่อกับสถานีฐาน ( BS) และ ชุมสายโทรศัพท์เคลื่อนที่ ( BSC and MSC) เพื่อทำหน้าที่ในการควบคุมสถานีฐาน โดยปกติส่วนควบคุมสถานีฐานสามารถที่จะรองรับ สถานีฐานได้ 10 ถึง 100 สถานี ทำหน้าที่จัดสรรช่องสัญญาณ , วัดระดับการเรียกเข้าของเครื่อง โมบายล์ และควบคุมการแฮนด์ออฟระหว่างสถานีฐานกับสถานีฐาน
ชุมสายโทรศัพท์เคลื่อนที่ (Mobile Switching Center or Mobile Telephone Switching Office)
ชุมสายโทรศัพท์เป็นศูนย์กลางควบคุมและประสานการทำงานของส่วนควบคุมสถานีฐาน มีตัวประมวลผลของระบบเซลลูล่าร์และสวิตช์สำหรับระบบเซลลูล่าร์ มีการเชื่อมต่อกับชุมสายโทรศัพท์อื่นๆรวมทั้งชุมสายโทรศัพท์สาธารณะด้วย ในบางระบบอาจมีฐานข้อมูลบันทึกข้อมูลของลูกข่ายไว้ในชุมสายด้วย และอาจมีระบบฐานข้อมูลเก็บข้อมูลของกลุ่มหมายเลขต่างๆใช้สำหรับอ้างอิงในการเรียกเข้าหาเครื่องโทรศัพท์หมายเลขที่ต้องการ กล่าวโดยรวมคือทำหน้าที่ควบคุมขั้นตอนการโทรศัพท์และเก็บข้อมูลการโทรศัพท์เพื่อที่จะนำไปเรียกเก็บค่าใช้จ่ายอีกทีหนึ่ง ชุมสายโทรศัพท์จะมีการเชื่อมต่อหลักๆ อยู่สองด้านด้วยกัน คือ ด้านแรกจะต่อเข้ากับส่วนควบคุมสถานีฐานเพื่อทำงานร่วมกันในการส่งผ่านข้อมูลหรือเสียงพูดของคู่สนทนา ด้านที่สองจะทำการเชื่อมต่อกับชุมสายอื่น ( ทั้งในระบบเซลลูล่าร์และระบบสาธารณะ ) เพื่อเป็นทางผ่านต่อไปยังคู่สนทนา
Genetic Algorithm
เจเนติกส์อัลกอริทึม (Genetic Algorithm) เป็นวิธีการทำให้มีประสิทธิภาพ (Optimization) ที่มีแนวคิดมาจากการวิวัฒนาการ ของสิ่งมีชีวิต โดยการนำค่าของตัวแปรต่างๆที่มีผลต่อค่าใช้จ่ายมาแปลงให้อยู่ในรูปของโครโมโซม (chromosome) ซึ่งอาจจะแสดงในรูปของ bit string หรือ real value string ก็ได้
ตัวอย่างเช่น กำหนดให้ตัวแปรที่มีผลต่อค่าใช้จ่ายมี 3 ตัวแปร คือ x, y, z โดยทั้งสามตัวแปรมีค่าเป็นเลขจำนวนเต็ม (integer) ในช่วง 0-127 ในกรณีที่ x = 16, y = 77, z = 15 จะสามารถแปลงเป็น โครโมโซม (chromosome) ในรูปแบบ bit string ได้โดย
x = 16 แปลงเป็น bit string ได้ 0010000
y = 77 แปลงเป็น bit string ได้ 1001101
z = 15 แปลงเป็น bit string ได้ 0001111
นำ Binary จาก x, y, และ z มาต่อกันจะได้โครโมโซม (chromosome) ดังนี้
Chromosome = [x, y, z] = [001000010011010001111]
ทั้งนี้ ในการแปลงค่าจากปัจจัยที่นำมาคิดเป็น Binary string นั้น สามารถกำหนดวิธีการแปลงค่าได้เอง ไม่จำเป็นต้องแปลงตามค่าตัวเลขทางคณิตศาสตร์ (numerical)
หรืออาจจะแปลงเป็นโครโมโซม (Chromosome) ในรูปแบบ real value string จะได้
Chromosome = [x, y, z] = [16|77|15]
ในการดำเนินการของเจเนติกส์อัลกอริทึม (Genetic Algorithm) จะเป็นการดำเนินการโดยมี โครโมโซมอยู่จำนวนหนึ่ง ซึ่งเรียกโครโมโซมกลุ่มนี้ว่า ประชากร
เจเนติกส์อัลกอริทึม (Genetic Algorithm) มีขั้นตอนการทำงาน ดังรูป
แสดงขั้นตอนการทำงานของเจเนติกส์อัลกอริทึม (Genetic Algorithm)
รายละเอียดของการทำงานในแต่ละขั้น มีดังต่อไปนี้
1. การกำหนดค่าตัวแปรและสมการค่าใช้จ่ายที่ใช้ในเจเนติกส์อัลกอริทึม (Selecting Variable and Cost Function)
กำหนดว่าในโจทย์ที่ต้องการ Optimize นั้น มีปัจจัยอะไรที่มีผลต่อค่าใช้จ่ายบ้าง และทำการสร้างฟังก์ชัน (Function) สำหรับคำนวณค่าค่าใช้จ่ายขึ้นมาเพื่อใช้ในขั้นต่อไป
2. สร้างประชากรต้นกำเนิด (Generate Initial Population)
ทำการสร้างประชากรชุดแรก เท่ากับจำนวนประชากรสูงสุดที่กำหนดไว้ ซึ่งอาจจะสร้างขึ้นมาโดยการสุ่ม หรือกำหนดขึ้นเอง
3. การคัดเลือกทางธรรมชาติ (Natural Selection)
เป็นการคัดเลือกโครโมโซม (Chromosome) ที่มีค่าใช้จ่ายมากที่สุดออก ตามอัตราส่วนที่กำหนดไว้ ทำให้เหลือโครโมโซม (Chromosome) อยู่จำนวนหนึ่งสำหรับทำการเลือกคู่ (mating)
4. การเลือกสรร (Selection)
ทำการจับคู่โครโมโซม (Chromosome) ที่เหลือเพื่อทำการเลือกคู่ (mating) โดยใช้วิธีการจับคู่ที่กำหนดขึ้น ซึ่งวิธีการเลือกคู่โครโมโซมขึ้นมา ทำการเลือกคู่ (mating) มีหลายวิธี ดังต่อไปนี้
• จับคู่โครโมโซม (Chromosome) ที่อยู่ติดกันจากบนลงล่าง
• จับคู่โดยการสุ่ม โดยความน่าจะเป็นที่โครโมโซม (Chromosome) แต่ละตัวจะถูกสุ่มขึ้นมานั้นมีเท่ากัน
• จับคู่โดยการสุ่มแบบถ่วงน้ำหนัก วิธีนี้ ความน่าจะเป็นที่โครโมโซม (Chromosome) แต่ละตัวจะถูกสุ่มขึ้นมานั้นมีไม่เท่ากัน โดยวิธีการถ่วงน้ำหนักมี 2 วิธี คือ
1. ถ่วงน้ำหนักโดยดูจากอันดับ วิธีนี้จะคิดความน่าจะเป็นที่โครโมโซม (Chromosome) แต่ละตัวจะถูกสุ่มขึ้นมา ตามลำดับที่เรียงจากโครโมโซมที่มี cost น้อยที่สุด ไปยังโครโมโซมที่มีค่าใช้จ่ายน้อยที่สุด โดยคำนวณความน่าจะเป็นของโครโมโซมแต่ละตัวจากสมการ
= จำนวนโครโมโซมที่เหลือจากขั้น Natural selection
= อันดับของ chromosome
2. ถ่วงน้ำหนักโดยดูจากค่าใช้จ่ายของโครโมโซม วิธีนี้จะคำนวณความน่าจะเป็นที่ โครโมโซมแต่ละตัวจะถูกสุ่มขึ้นมา จากค่าใช้จ่ายของโครโมโซม ตัวนั้นๆ โดยค่าใช้จ่าย ที่นำมาคำนวณนั้น ต้องทำการ normalize ก่อน ด้วยสมการ
= cost ของ chromosome ตัวที่ n
= cost ของ chromosome ที่มี cost ต่ำที่สุดที่ถูกคัดออกจากขั้น Natural Selection
จากนั้น คำนวณความน่าจะเป็นของ Chromosome แต่ละตัวด้วยสมการ
= cost ของ chromosome ตัวที่ n ที่ผ่านการ normalize แล้ว
= cost ของ chromosome ตัวที่ m ที่ผ่านการ normalize แล้ว
• การเลือกแบบ tournament วิธีนี้จะทำการสุ่มโครโมโซม ขึ้นมาจำนวนหนึ่ง ( 2 ถึง 3 โครโมโซม) ก่อน แล้วค่อยเลือกโครโมโซม ที่มีค่าใช้จ่ายน้อยที่สุดในกลุ่มออกมา
5. การจับคู่ (Mating)
เป็นการนำโครโมโซม คู่ที่ได้เลือกไว้จากขั้น Selection มาสร้างเป็นโครโมโซม ใหม่โดยการทำ crossover ระหว่างโครโมโซม ทั้งสอง ซึ่งวิธีการในการทำ crossover มีหลายวิธี ดังต่อไปนี้
Single crossover ทำการสุ่มตำแหน่ง crossover ขึ้นมาหนึ่งตำแหน่ง แล้วทำการแลกเปลี่ยนยีนส์ (gene) ที่อยู่ต่อจากตำแหน่ง crossover เพื่อสร้างเป็นโครโมโซม ใหม่ขึ้นมา 2 โครโมโซม
Multipoint crossover ทำการสุ่มตำแหน่ง crossover ขึ้นมาจำนวนหนึ่ง เรียงลำดับจากน้อยไปหามาก แล้วทำการแลกเปลี่ยนยีนส์ (gene) ที่อยู่ระหว่างตำแหน่ง crossover ที่อยู่ติดกันเพื่อสร้างเป็นโครโมโซม ใหม่ขึ้นมา 2 โครโมโซม
Uniform crossover สร้าง crossover mask ซึ่งเป็น bit string ซึ่งมีความยาวเท่ากับโครโมโซมขึ้นมา โดยที่ค่าของแต่ละบิต (bit) ได้มาจากการสุ่ม ซึ่งค่าของแต่ละ bit นี้จะเป็นการกำหนดว่าโครโมโซมที่สร้างขึ้นใหม่นั้น จะนำค่าของแต่ละยีนส์มาจาก โครโมโซมตัวใด (จาก โครโมโซม คู่ที่เลือกมาจากขั้น selection) และสร้างอีก โครโมโซมหนึ่งในลักษณะเดียวกันโดยใช้ inverse ของ crossover mask ที่ใช้ข้างต้น
Intermediate crossover ใช้สำหรับโครโมโซมที่เป็นแบบ real value string โดยที่ค่าของแต่ละยีนส์ในโครโมโซมใหม่จะคำนวณจาก
โดย เป็น Factor ที่ถูกสุ่มมาจากช่วงที่กำหนดขึ้นช่วงหนึ่ง ซึ่งจะทำการสุ่มใหม่ทุกครั้งที่เปลี่ยนคู่โครโมโซมและ P 1 , P 2 เป็นโครโมโซมจากขั้น selection
Line crossover มีลักษณะคล้ายกับ Intermediate crossover แต่ค่า ที่ใช้จะคงที่ตลอด
6. การกลายพันธุ์ (Mutation)
ทำการเปลี่ยนแปลงยีนโดยการสุ่มตำแหน่งของยีนที่จะเปลี่ยนแปลงขึ้นมาตามอัตราส่วนการเกิด Mutation ที่กำหนดไว้ โดยการเปลี่ยนแปลงคือการเปลี่ยนค่าของ bit จาก 0 เป็น 1 หรือ จาก 1 เป็น 0 ในกรณีที่เป็นแบบ bit string โดยจะยกเว้นไม่ให้เกิดการเปลี่ยนแปลงกับโครโมโซมที่มีค่าใช้จ่ายน้อยที่สุดในขณะนั้น และจะไม่มีการ Mutation ในการทำงานรอบสุดท้าย
7. ผลที่ได้เป็นไปตามเกณฑ์หรือไม่ (Termination Criteria)
เจเนติกส์ (Genetic Algorithm) จะทำงานแบบ Iterative (นับประชากรในแต่ละ iteration เป็น 1 generation) ซึ่งจะหยุดทำงานเมื่อคำตอบที่ได้มีค่าใช้จ่ายในระดับที่ต้องการ, ค่าใช้จ่ายที่ต่ำที่สุดในแต่ละรุ่น (generation) มีค่าเท่ากัน หรือทำงานครบตามจำนวนรอบที่กำหนดไว้
8. จบการทำงาน (Termination)
เลือกโครโมโซม ที่มีค่าใช้จ่ายน้อยที่สุดเป็นคำตอบของปัญหา
K-Mean algorithm
K-mean algorithm เป็นวิธีการที่ในการแบ่งข้อมูลออกเป็นกลุ่มๆ ตามจำนวนของกลุ่ม (cluster) ที่ต้องการ ซึ่งมีขั้นตอนการทำงาน ดังรูป
แสดงขั้นตอนการทำงานของ K-mean Algorithm
รายละเอียดของแต่ละขั้นตอนเป็นดังนี้
1. Number of cluster k
เป็นการที่กำหนดว่าเราต้องการแบ่งประชากรออกเป็นกี่กลุ่ม (Cluster)
2. Initial centroid to each cluster
ทำการกำหนดค่าของ centroid แต่ละกลุ่มโดย random มาจากประชากรที่มีอยู่
3. Assigned data to set that has nearest centroid until no data pending
ทำการนำประชากรที่มีอยู่จับเข้าแต่ละกลุ่มโดยที่ต้องใกล้กับ centroid ของกลุ่มนั้นมากที่สุด ในแต่ละครั้งที่มีการจับเข้ากลุ่ม ต้องคิดค่า centroid ของกลุ่มนั้นๆใหม่เสมอ โดยหาจากค่าเฉลี่ยของประชากรในกลุ่ม ทำไปจนกว่าจำนวนประชากรจะถูกจัดเข้าทุกกลุ่มจนครบ
4. Compute objective function
ทำการคำนวณสมการวัตถุประสงค์ตามสูตรนี้
เมื่อ J(objective function) คือ ผลรวมของผลต่างระหว่าง centroid ของข้อมูลในกลุ่มยกกำลังสอง
k คือ จำนวนกลุ่ม (cluster) ทั้งหมด
คือ เซตของข้อมูลกลุ่มที่ i เมื่อ i = 1, 2, 3, …, k
คือ ข้อมูลที่เป็นสมาชิกของเซต
คือ centroid หรือค่าเฉลี่ยของข้อมูลทุกตัวในกลุ่ม
5. Is this minimize objective function
ทำการตรวจสอบว่ากรณีที่ได้มานี้ผลของฟังก์ชันจุดประสงค์ (objective function) นั้นมีค่าต่ำสุด , แทบจะไม่เปลี่ยนแปลงค่า หรือวนครบจำนวนรอบที่กำหนดไว้ใช่หรือไม่
6. A set of k cluster that minimize the objective function
ได้ผลลัพธ์เป็นข้อมูลที่แบ่งเป็นกลุ่มๆทั้งหมด k กลุ่มและมีค่า objective function น้อยที่สุด
