Transcript Fixed telephone network planning

Fixed telephone network
planning
Group Member:
Afnan Salem – 0562374
Isra Yuosef – 0562391
Samar Faisal – 0562384
Nehal Mahmoud – 0562394
 Weam Minshawi - 0643184
Supervisor:
Dr-Lamia Fattouh
Agenda…
•
•
•
•
•
•
•
•
•
•
•
Introduction.
Problem definition.
Survey.
Needs of project
Solution.
About our program.
Result of output.
Test.
Limitations.
Conclusion.
Future work.
Introduction
•
•
•
With existing telephone networks nearing saturation and demand for
wire and wireless services continuing to grow, telecommunication
engineers are looking at technologies that will deliver sites and can
satisfy the required capacity and coverage constraints.
The city data is given as a map of streets, intersection nodes
coordinates, distribution of the subscribers’ loads within the city. The
available cable sizes.
The process of network planning is divided into two sub problems:
1. Determining the location of the exchanges.
2. Construction of subscriber network lines from exchange to
subscribers to satisfy optimization criteria and design constraints.
The Problem definition:
• In many developing countries, there is tremendous demand
for new business and residential telephone service.
• The continuous Increasing of number of subscribers make
congestion in MSAN and cause degradation in grade of
service and in sometimes impossible to add new
subscribers which lead to using the mobile tower.
• Also, the existing of the natural obstacle is affecting on
distribution the MSAN on the regions.
• The responsible operator is looking to rapidly provide
thousands of new subscribers with high-quality telephone
service and provide the right equipment, at the right place,
and at the right time to provide an acceptable grade of
service with minimum number of MSANs.
The survey
Telephone Network plan:
•
The main concept of this project is planning and drawing telephone
network in area that is doesn't has telephone service. It is achieving two
aims:
1.
the first one is determining the best place of the central depending on
specific criteria’s and conditions by using several of logical operations.
2. The second one is determining the shortest path to connect the
subscriber whit the central by using shortest path algorithms. All that
operation is depending on some information entered by the user.
Comparison with our project:
This program is different from our project because we are using the clustering
technique to create groups of objects based on their features in such a
way that the objects belonging to the same group’s that is after the user
entered some information about assigning area using the shortest path to
connect MSAN with subscribers. Finally it is planning the telephone
network and prints the report about the cost.
PlanAir:
•
•
1.
2.
•
•
•
•
It uses a two phase clustering algorithm for wireless local loop (WLL)
communication system planning that are introduced for cells
determination and the locating of base station sites.
The clustering process employs two well-known algorithms:
K-Means.
Agglomerative algorithms.
The data to be clustered is the distribution of the subscribers requesting
service in addition to the types of service they request (voice, ISDN, etc.).
The PlanAir software employs this algorithm in a planning subsystem
alongside a GIS subsystem to attain the required planning.
The system determines both the cell size and its RF planning through the
determination of its antenna height, power and type.
The RF planning is also obtained to maximize the number of subscribers
within the call. These are obtained under the constraints of coverage,
quality and capacity
Comparison with our project:
The main different which is distinguish our project than PlanAir project is
using the wire in specific fiber optics rather than wireless local loop
(WLL).fiber optics is a new technology which transferring data at speeds
from 622 Mbps to 2.5 Gbps per second to users and 155 Mbps to 622
Mbps to the network but WLL old technology which the
telecommunication company does not use it now. In other hand in our
project we use DBscan clustering algorithm we talked about it at section
2.9 but this project use k-mean algorithm which is a partition-based
algorithm that takes the number of the clusters as input parameter. The
algorithm organizes the objects into exactly k partitions where each
partition represents a cluster.
Efficient Network Planning Using CSPw-ClARANS Clustering Algorithm:
• This program use CSPw-ClARANS (Clustering with weighted Shortest PathCLARANS) Clustering Algorithm to solve the problem of network planning
and the construction of optimal cable network layouts where the weights
used are the subscriber loads.
Comparison with our project:
• The main different which is distinguish our clustering algorithm than their
clustering when applying CLARANS algorithm it clusters all regions even if
it is empty or does not have density but the DBScan interest in the density
by clustering it in groups.
The needs of project:
There are so many reasons to building our project:
•
The network planning engineers need for program that support
network planning to save the time and effort.
•
The mistakes from bad planning caused:
1.
Increasing the cost and budget of network and decreasing the
benefits.
2.
Degrade the services.
3.
the noise subscriber (in obstacle area) that may be on out of
coverage area of MSAN.
So we are going to computerize the network planning to make the planning
more efficient and provide the best service to subscribers.
Solution
•
1.
2.
3.
we use some of computer sciences to make our software more efficient
and suitable to plan the telephone network.
In our project we use a combination between different branches of
computer sciences:
IS (Information System): GIS (Graphical Information System)
AI (Artificial Intelligent): Data Mining Algorithms
Shortest Path Algorithm
•
1.
2.
The used tools in our program:
Database : SQL 2008
Prigramming language: Visualbasic.NET. 2008
•
GIS
• GIS is an information system to store map‘s information.
• A map made up of entities (points, lines, polygons) that have
geographic positions on the city as well as relationships to all
the other entities within the layer (topology).
1. The data point is the projection of streets’ squares on the
map. A single data point has: position (X, Y).
2. The line which represent the streets between two points with
its related information such as (street load and length).
3. The candidate MSANs positions represented by coordinates.
Each MSAN has the max and min capacity and limit of
coverage area.
4. The mobile tower position represented by coordinates.
5. Core point: A point that represent the best location for the
MSAN in that area(It is appear after clustering).
Data Mining Algorithms
•
Clustering is one of the data mining techniques that discover hidden
information in large amount of data. Clustering objects means to
categorize them based on their feature vectors.
•
We use two algorithms :
1.
Density-based algorithms :
DBScan (Density Based Spatial Clustering of Applications with Noise) is one of
Density-based algorithms clustering algorithm which is divide the
subscribers into clusters by detect arbitrary form of clusters and it can
filter out the noise.
2.
hierarchical algorithms:
Agglomerative clustering algorithm is a hierarchical algorithms which it
associates the points to appropriate cluster.
DBScan Algorithm
The reasons for choosing DBScan algorithm:
• It is a fundamental density-based clustering algorithm.
• It regards clusters as dense regions of objects in the data
space which are separated by regions of low density objects.
• It exploits the benefit of the natural approach clustering those
objects together that forms a dense region.
• It is efficient even for large spatial databases.
• It is able to quickly discover clusters of arbitrary size and
shape.
• It is significantly more effective in discovering clusters of
arbitrary shape than the well-known algorithm CLARANS and
it outperforms CLARANS by a factor of more than 100 in terms
of efficiency.
Agglomerative algorithm
• It is a bottom-up approach that starts with the points as
individual clusters.
• At each step, merge the closest pair of clusters until
only one cluster (or K-clusters) left.
Shortest Path Algorithm
• Dijkestra is the shortest path algorithm that calculate the distance from
one source to all destinations.
• Dijkstra's algorithm has a run time of O (n2) and it can quickly finds the
shortest path from a chosen source to a given destinations.
• So, we use it instead of Floyd's algorithm because it is an O(n3) algorithm
for finding all pairs of shortest paths.
Implementation
DBScan Algorithm:
• In network planning the cable length must be at maximum 2.5 km .So, we
make the value of EPS take the value of shortest path from core (MSAN) to
the most remote point (subscribers). The original DBSCAN Algorithm uses
Euclidian distance (that means the direct distance between the MSAN and
nodes); since in the real city the MSAN should be at the edge of the street
whether in a garden or any position specific for that purpose, the cable
should be connected directly from MSAN to nodes nearby and from node
to each other. In this case the shortest path algorithm is more accurate
than Euclidian distance i.e. if we depending on Euclidian distance in our
calculation the distance which usually small value) between a node and
one of the core (MSAN)this node may be appear as member of this cluster
although the exact distance out of the cluster border consequently
Euclidian distance give a wrong result .To apply shortest path we selected
Dikjstra algorithm.
The DBScan classes of node from our project point review are:
1.
2.
3.
4.
Core point which is a subset of candidate MSAN location.
Noise point it is a node that impossible link to the MSAN supposed
to follow it (because the load of the MSAN exceed maximum
capacity 1536). In real planning all subscribers must be served so
noise point is served using the mobile tower which can serve at
maximum 100 subscribers because that number is the maximum
subscriber who can be served by mobile tower and the engineers
taking in account growth the subscriber in the future. So we
conclude 100 is the optimum value of the minimum point.
Border point that belong to ascertain cluster.
Although minimum capacity of the core (MSAN) is 256 fixed phone
lines (the number of subscribers) we consider the minimum number
as 100 because the.
Agglomerative clustering technique:
• The agglomerative is hierarchal clustering technique .It starts with the
points as individual clusters and at each step merge the closest pair of
clusters depends on a notion of cluster proximity. In our project, after we
distribute the nodes into different clusters (each cluster has served by one
MSAN) and maybe there are two cores (MSANs) are close in distance (less
than 1.25 Km).So, we need to decrease the cost of constructing a new
MSAN if one of them can hold the loads (subscribers) of two MSANs.
Dijkstra algorithm:
• In the project, we used this algorithm to calculate shortest path from one
source to many destinations; in the DBSCAN we need to calculate the
shortest path from MSAN to all nodes (the reason is to determine the
suitable MSANs that serve at least 100 as a minimum number of
subscribers) and from one node to all MSANs (the reason is to determine
the nearest suitable MSAN that will serve this node). Based on shortest we
calculate the load of MSAN.
Pseudo code of our project
For (i=1 to candidate No.)
Calculate the shortest path from switch (i) to each node(also, the load will calculate through it).
If (shortest path < 2.5)
Then calculate the load = load +current load of node.
If (sum of load >= 256)
Then add switch to cores.
End for
For each node in the city select the best switch for it by calculating the shortest path between the nodes and
each switch (path < 2.5)
Calculate the load of each core
Agglomerative:
For each tow clusters
If the shortest path between the cores < 1.25
Then
If (sum of two clusters' load <1536)
Then
First assume that the first core is core of the two clusters
And apply the previous algorithm for each node in the tow clusters.
Second assume that the second core is core of the two clusters
And apply the previous algorithm for each node in the tow clusters.
If (the two cores are suitable to be a core for all nodes of tow clusters)
Then
Calculate the summation of (load X distance) for each core
And choose the appropriate core depend on minimum value.
Else let the suitable one the core for tow clusters.
About our Program
•
1.
2.
3.
4.
5.
6.
•
1.
2.
3.
4.
5.
6.
7.
Input of Program
The map.
Node (subscriber).
Candidate MSAN.
Streets and its information(load).
The real length of first street to compute the pixel measurement scale.
Mobile Tower.
Output of Program
Planned network that contain:
Suitable selected MSAN from the candidate one.
Mark the MSAN that has exceed its load and recommend to support it
with mobile tower.
The group of subscribers for each MSANs.
The number of clusters that network need.
Associate the noise node with nearest mobile tower.
In Some situation; merge two cluster into one
Result of O/P
• Here is the map and its GIS component before plan
Here is the map after apply cluster algorithm and Dijkestra with out
agglomerative
Here is the network after applying agglomerative algorithm
Another net work that have some MSAN with exceed load
Before
plan
After
plan
Testing
• After planning is completed, the expert is
commending on the result of applying the
algorithms from side of accuracy of planning
and the consumed time to accomplish this
process in relation of the time consumed by
using the manual way.
Limitation
• The most effected limitation on our project was the time, which it
prevents us to make many ideas and works that we want to do. The
limited time that we have is avoided us to expand our project to
manipulate a large region. Also, it is discourage us to experiment more
than one algorithm and comparing between the results of them then use
the effective one.
conclusion
• Clustering analysis is one of the major tasks in various
research areas. The clustering aims at identifying and
extracting significant groups in underlying data. Based on
certain clustering criteria the data are grouped so that data
points in a cluster are more similar to each other than points
in different clusters.
• In our project we studied the problem of Increasing the
number of subscribers make congestion in MSAN and cause
degradation in grade of service and in some time impossible
to add new subscribers which lead to using the mobile tower.
Also, the existing of the natural obstacle is affecting on
distribution the MSAN on the regions.
Future work
• In the future, we want to improve our system and
add some feature to it.
• We have some general idea about what we want to
do:
• 1- Comparing between clustering algorithms
practically and determine which supposed to give
more precise result.
• 2- Expand our project to manipulate much more
regions that clarify the efficient factor of the
algorithm.
Thank you